December 2006 - Haskell-Cafe

how unsafe is this?
by Ben Clifford 30 Dec '06

30 Dec '06

I've defined a helper function to let me do regexps in functional style: > sed exp str = unsafePerformIO $ do > regexp <- regcomp exp 0 > regexec regexp str Is this always safe? or where is it not? (I'm using any one regexp more than once so it doesn't bother me that it compiles each time) --

2 1

Efficient way to break up a lazy bytestring
by Ranjan Bagchi 30 Dec '06

30 Dec '06

Hi -- I'm loading a big file (~2G), again, with 72-byte C structs. I've done pretty well [thanks to everyone] interpreting the fields, but I'm finding the traversal of the file to be pretty inefficient. I do the following: breakUp s | L.null s = [] | otherwise = h:(breakUp r) where (h,r) = L.splitAt 72 s Running this on the 2G file blows up the stack pretty quickly, taking the first 1 million records (there are 20M of them) with a big stack parameter gives about 25% productivity, with GC taking the other 75%. My understanding is that while this looks tail recursive, it isn't really because of laziness. I've tried throwing seq operators around, but they don't seem to do much to help the efficiency. Any help's appreciated. Ranjan

6 6

Newbie question
by Pieter Laeremans 29 Dec '06

29 Dec '06

Hi, I'm reading the Haskell school of expression by Paul Hudok. Great book. However I would like some feedback about a solution to an exercise The problem is quite simple : define f1 and f2 (using higher order functions ) such that f1 (f2 (*) [1..4]) 5 => [5,10,15,20] I have come up with the following solution : f2 :: (a->b)->[a] -> [b] f2 f xs = map f xs f1 fs a = map (applyOp a) fs applyOp b f = f b But I guess there must be some more elegant way. f2 isn't at all original. And the applyOp sounds silly. Any comments or suggestions are welcome. thanks, Pieter

2 1

constant functions
by michael rice 29 Dec '06

29 Dec '06

I'm trying to learn Haskell and translating some Lisp functions as exercises. How would I write a Haskell function named ALWAYS that behaves like this: one = always 1 bozo = always "clown" > map one [2,3,4,5,6] [1,1,1,1,1] > one 62 1 > map bozo [2,3,4,5,6] ["clown","clown" ,"clown", "clown"," clown"] > bozo 62 "clown" i.e. ALWAYS returns a function with a single parameter that is ignored, returning instead the value given to ALWAYS when the function was created. This is what I've been trying: always :: (a -> a) -> a -> a always x = (\y -> x) one = always 1 Michael __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

8 13

Combine list of sorted lists
by Quan Ta 29 Dec '06

29 Dec '06

Hi all, I have this function which combines (zip) list of sorted lists into a sorted list (sorted by sum). The function works with infinite list and seems to give correct result. But after I see the code for the Hamming sequence from the Wiki, I wonder if it can be written better, or more clearly, or succint? import Data.List comb [] = [] comb (a:as) = foldl f2 (f1 a) as where f1 :: [Int] -> [[Int]] f1 [] = [] f1 (a:as) = [a] : f1 as f2 :: [[Int]] -> [Int] -> [[Int]] f2 la [] = [] f2 [] lb = [] f2 la@(a:as) lb@(b:bs) = (a ++ [b]) : (f3 (f2 [a] bs) (f2 as lb)) f3 :: [[Int]] -> [[Int]] -> [[Int]] f3 [] lb = lb f3 la [] = la f3 la lb = let a = head la b = head lb in if sum a <= sum b then a : f3 (tail la) lb else b : f3 la (tail lb) t1 = take 500 (comb [[1,2..],[1,23..],[1,5..],[1,9..]]) t2 = take 500 (sortBy (\x y -> compare (sum x) (sum y)) [[a,b,c,d] | a<-[1,2..80],b<-[1,23..80], c<-[1,5..80],d<-[1,9..80]]) --t3 = take 500 (sortBy (\x y -> compare (sum x) (sum y)) -- [[a,b,c,d] | a<-[1,2..],b<-[1,23..], -- c<-[1,5..],d<-[1,9..]]) main = print (show ((map sum t1) == (map sum t2))) -- thanks for looking, -- Quan

4 6

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