- Haskell-Cafe - Haskell.org

flatten a nested list
by pphetra 29 Dec '06

29 Dec '06

I would like to write a program that can do something like this. ;; lisp syntax * (my-flatten '(1 (2 (3 4) 5))) (1 2 3 4 5) I end up like this. data Store a = E a | S [Store a] deriving (Show) flat :: [Store a] -> [a] flat [] = [] flat ((E x):xs) = [x] ++ flat xs flat ((S x):xs) = flat x ++ flat xs so *Main> flat [E 1, S[E 2, S[E 3, E 4], E 5]] [1,2,3,4,5] Compare to a Lisp solution, It 's not looking good. Any suggestion. Thanks, PPhetra -- View this message in context: http://www.nabble.com/flatten-a-nested-list-tf2893713.html#a8084726 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

6 6

Coverage Condition?
by lists＠qseep.net 29 Dec '06

29 Dec '06

Hi folks, I'm working on a program that I've been dabbling with for years. For the first time, I tried to compile it with GHC 6.6, and got an error, explaining that I was violating the Coverage Condition in my instance declaration. The instance declaration looks like this: instance MonadReader r m => MonadReader r (CPST o m) where ... The MonadReader class definition, which doesn't appear to have changed since 6.4.2, looks like this: class Monad m => MonadReader r m | m -> r where ... Apparently, the Coverage Condition disallows my instance declaration, because the variable 'r' is not mentioned in the '(CPST o m)' term. Now this would make sense to me if I didn't have the assertion 'MonadReader r m'. Because of that assertion, m -> r, so '(CPST o m)' shouldn't need to explicitly mention 'r'. I will try using -fallow-undecidable-instances, and see if the message goes away. But can someone explain to me why this is wrong, and what would be the preferred way to write it? I've attached the two relevant source files. (Try compiling both files.) Thanks, Lyle

3 3

Is there a printable copy of the (GHC) library references anywhere?
by Paul Moore 28 Dec '06

28 Dec '06

I'd like to print out a copy of the GHC manuals, for reference. I've got the Haskell 98 report, and the GHC user guide, but the only documentation I've found for the hierarchical libraries is in HTML format (generated from Haddock). Is there a printable (preferably PDF) form of the library documentation? Either all of it, or alternatively reasonably large subsets? Thanks, Paul.

7 13

SYB and/or HList for XML, deserialization and collections
by S. Alexander Jacobson 28 Dec '06

28 Dec '06

Having just done a major refactor of the HAppS HTTP API to make it much much easier to use, I am now thinking about simplifying the current boilerplate associated with XML serialization and state deserialization. In the case of XML, Currently the developer must manually write ToElement for every type he/she wants to output. HAppS provides functions that makes doing this a lot easier if the types are Haskell records with field labels of the form: data Animal = Animal {key::Int, name:: String, breed::Breed, price::Float} Looking at the XML example from the SYB site, a shift to SYB means shifting from Record types with field labels to identifying fields by their types so e.g. data Animal = Animal Key Name Breed Price type Key = Int type Name = String type Species = Cow | Sheep type Price = Float This model seems ok, but adds some verbosity. It also entails a learning curve because either you also have field labels or you end up with non-standard extra code to access fields. In this context, HList provides good record functionality and a little template haskell makes it easy to code so we end up with e.g. $(hList_labels "Animal" "key name breed price") type Breed = Cow | Sheep This seems superior from a programming perspective because we have good record functionality (and implicitly support for XML namespaces!), but we lose something on the XML side. In particular, we end up with two new problems: 1. We no longer have type names, so we can't automatically generate an XML element name from an default HList record. The solution may be to define something like this: typeName name item = typeLabel .=. name .*. item animal = typeName "animal" myAnimal = animal .*. breed .=. Cow And since update and extension are different functions, if we hide "typeLabel" from the apps then this gets very safe (or we expose it and get a form of typesafe coerce). 2. We don't know how to deal with non-atomic field values e.g. <animal><breed>Cow></breed></animal> makes sense, but we probably don't want read/show for product types. Perhaps it is possible to use overlapping instances to do something like: instance ToElement HCons a b where ... instance ToElement a where toElement = show But perhaps we can use SYB to allow us to distinguish between atomic and non-atomic types and handle appropriately. I have to say I don't think I undersand the SYB papers well enough to give an example. Note: I can't find an actual example of generating XML from HLists in any of the HList docs so it may be that it is not actually as easy as it looks. All of this may be an open issue in theory as well as practice. == Deserialization == HAppS periodically checkpoints application state to disk. Developers may want to add or remove fields from their state types for from data types used by their state types. The current solution is to have the developer assign a version number to state. If state changes then the developer provides dispatch to a deserialization function based on that version number. It is not at all clear from either the SYB or the HList papers how to deserialize generally. That being said, the HList library provides a way to call functions with optional keyword arguments that looks like it would also generalize to schema transitions. Anyone who has some experience with this issue in the context of HList or SYB? == Haskell Collections == Currently HAppS developers use e.g. Data.Set or Data.Map as collection types for their application. If we push devlopers to use HList for eveything then they are going to need a way of handling collections of Hlist items. My sense is that HList style data structures can't be stored by Data.Map or Data.Set because they are not heterogenous collection types (and will break simply from varying the order of field names). If we use HList as the assumed record type, then I think we need to recode Data.Map and Data.Set for them. Has anyone implemented more interesting collection types for HList objects? -Alex- PS Obviously people can continue to use regular haskell types and implement stuff manually. My goal here is to support people who want more automation and are willing to learn HList or SYB in order to get it.

4 3

Red-black trees as a nested datatype
by Jim Apple 28 Dec '06

28 Dec '06

-- Inspired by Chris Okasaki's reference to Ross Patterson's AVL -- trees as a nested datatype, here are (I think) red-black trees -- as a nested datatype. -- ref: http://www.haskell.org/pipermail/haskell/2003-April/011693.html module RedBlackTree where {- Red-black trees satisfy the following conditions, according to Wikipedia: 1. A node is either red or black. 2. The root is black. 3. All leaves are black. 4. Both children of every red node are black. 5. Every simple path from a node to a descendant leaf contains the same number of black nodes. -} data Node a n = Node n a n {- a is the carrier type: the type of the values contained in the nodes. r0 and b0 are red and black trees with one more level of black nodes than r1 and b1. -} data Tree a r0 b0 r1 b1 = Zero b1 -- The top node of a tree is black -- We recurse by adding one to the number of levels of black nodes | Succ (Tree a {- Red trees have black children and reduce the count of black nodes to the descendent leaves by 0 -} (Node a b0) {- Black trees have children of either color and reduce the count of black nodes to the descendent leaves by 1 -} (Node a (Either r1 b1)) r0 b0) -- The type for black-rooted trees with two levels of black nodes. type Black2 a = Node a (Maybe a) type RedBlackTree a = Tree a -- A red tree with two levels of black nodes is just a red node on -- top of two black nodes. (Node (Black2 a) a) (Black2 a) a () -- Jim Apple

1 1

Re[2]: [Haskell-cafe] Dealing with incoherent instances
by Bulat Ziganshin 28 Dec '06

28 Dec '06

Hello Vyacheslav, (returning to cafe) Wednesday, December 27, 2006, 6:10:30 PM, you wrote: > Ah, so the moment something is passed through a polymorphic function > its type information is lost... This seems like a bug in the > specification/implementation, no? This is most certainly not the > desired behavior. It seems like the compiler has all the information > it needs but still can't select the right instance. sorry, but i think that it is how type class system should work in this case. look at the page for details > Are there ways to get around this problem? existential types, for example. we need exact specification of your problem. "show me the code" >> are you seen http://haskell.org/haskellwiki/OOP_vs_type_classes ? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

2 1

Re: [Haskell] state of HaXml?
by dons＠cse.unsw.edu.au 27 Dec '06

27 Dec '06

nr: > I have some XML things to take care of, and I had hoped to use > a nice functional language with combinators. But I'm having > trouble getting HaXml to do anything useful. Here is a program > that I wrote just to read in the XML and prettyprint it. > But it fails with an error message. The 'expat' tool 'xmlwf' > claims the XML is well formed, and the XML was generated from > gpsbabel, a tool I trust to behave properly. And yet: > > : nr@curlycoat 10429 ; xmlwf 2006-12-27-backup.gpx > : nr@curlycoat 10430 ; $AWD/Main 2006-12-27-backup.gpx > Main: Parse error: unexpected EOF > > Here is Main.hs: > > module Main where > import qualified Text.XML.HaXml as X > import qualified Text.XML.HaXml.Parse as XP > import qualified Text.XML.HaXml.Pretty as XPP > import qualified IO > import qualified System > > load :: String -> IO X.Document > load fn = do handle <- IO.openFile fn IO.ReadMode > contents <- IO.hGetContents handle > IO.hClose handle > return $ XP.xmlParse fn contents > > main = do [xml] <- System.getArgs > d <- load xml > IO.putStrLn $ show $ XPP.document $ d > > > I'm using HaXml version 1.13.2-5 as distributed by Debian, > with GHC 6.6. > > Does anyone have thoughts or suggestions? Is there software I should > prefer to HaXml? (I notice that HaXml does not understand XML Schema, > which I seem to be stuck with...) You might also want to have a peek at HXT, the XML toolbox. That's been used to good effect recently, for a little RSS aggregator: http://cale.yi.org/index.php/HRSS -- Don P.S. Redirected to the -cafe

1 0

Dealing with incoherent instances
by Vyacheslav Akhmechet 27 Dec '06

27 Dec '06

I'm looking at GHC's overlapping instances docs here: http://web.mit.edu/ghc/www/users_guide/type-extensions.html#instance-decls and I've ran into the incoherent instances problem. Basically, I have a "catch all" instance that handles all types in a generic manner using SYB introspection, and then I have type specific instances that specialize behavior for certain types. This works with overlapping instances extension but whenever I take advantage of this functionality from polymorphic functions I run into the incoherent instances. If I enable incoherent instances GHC always picks the general case which seems like the wrong thing to do. What I want it to do is delay comitting to an instance until it's processing a specific invocation of a polymorphic function. All the information is available at compile time but I found no way to do this. Is there a way to get around this problem? Thanks, - Slava.

2 2

hiii
by omit singh rathore 27 Dec '06

27 Dec '06

Send free SMS to your Friends on Mobile from your Yahoo! Messenger. Download Now! http://messenger.yahoo.com/download.php

1 0

Lambda Revolution tee shirts
by Paul Johnson 25 Dec '06

25 Dec '06

I was inspired by Don Stewart's Blog posting "The Lambda Revolution" to create a tee shirt design on this theme. Samples are available from CafePress at http://www.cafepress.com/l_revolution , but the designs are freely available. If anyone wants to send them to a more local tee-shirt printer than CafePress then let me know and I will email the SVG files. Paul.

2 1