April 2011 - Haskell-Cafe

Parsing binary 'hierachical' objects for lazy developers
by John Obbele 30 Apr '11

30 Apr '11

Hi Haskellers, I'm currently serializing / unserializing a bunch of bytestrings which are somehow related to each others and I'm wondering if there was a way in Haskell to ease my pain. The first thing I'm looking for, is to be able to automatically derive "Serializable" objects, for example: --------------------------------------------------------------- import Data.Serialize -- using cereal as an example data MyFlag = One | Two | Three instance Serialize [MyFlag] where put = putWord16le . marshalFlags get = unmarshal `fmap` getWord16le data ObjectA = ObjectA { attribute0 :: Word8 , attribute1 :: Word16le , attribute2 :: [MyFlag] } deriving (Serialize) -- magic goes here! --------------------------------------------------------------- Unfortunately ghci complains that 'Serialize' is not a derivable class. Yet, deriving the Serialize instance for ObjectA should be simple, since all the three attributes are already serializable themselves... Second issue, I would like to find a way to dispatch parsers. I'm not very good at expressing my problem in english, so I will use another code example: --------------------------------------------------------------- -- let's say we have two objects with almost the same structure: data ObjectA = ObjectA { objLength :: Int , objType :: TypeId , attribute2a :: [MyFlag] } data ObjectB = ObjectB { objLength :: Int , objType :: TypeId , attribute2b :: Word32le } --------------------------------------------------------------- When we begin to deserialize theses objects, we don't know their final type, we just know how to read their length and their typeId. Only then can we determine if what we are parsing is an ObjectA or an ObjectB. Once we now the object type, we can resume the parsing and return either an ObjectA or ObjectB. Oki, so I may have read too much of Peter Seibel's chapter on binary-data parsing in Common Lisp or spent too much time working on object-oriented code, but currently, I have no idea on how to write this 'simply' in Haskell :( any help would be welcome /john

4 6

Re: [Haskell-cafe] Iteratee: manyToOne
by John Lato 29 Apr '11

29 Apr '11

> > From: Felipe Almeida Lessa <felipe.lessa(a)gmail.com> > > On Thu, Apr 28, 2011 at 1:10 PM, Felipe Almeida Lessa > <felipe.lessa(a)gmail.com> wrote: > > On Thu, Apr 28, 2011 at 12:09 PM, Felipe Almeida Lessa > > <felipe.lessa(a)gmail.com> wrote: > >> I foresee one problem: what is the leftover of 'manyToOne xs' if each > >> x in xs needs different lengths of input? > >> > >> One possible untested-but-compiling solution: > > [snip] > > > > Like I said, that manyToOne implementation isn't very predictable > > about leftovers. ?But I guess that if all your iteratees consume the > > same input OR if you don't care about leftovers, then it should be > > okay. > > Sorry for replying to myself again. =) > > I think you can actually give predictable semantics to manyToOne: > namely, the leftovers from the last iteratee are returned. This new > implementation should be better: > If you do this, the user needs to take care to order the iteratees so that the last iteratee has small leftovers. Consider: manyToOne [consumeALot, return ()] In this case, the entire stream consumed by the first iteratee will need to be retained and passed on by manyToOne. In many cases, the user may not know how much each iteratee will consume, which can make these semantics problematic. Iteratee has 'enumPair', (renamed 'zip' in HEAD) which returns the leftovers from whichever iteratee consumes more. This avoids the problem of retaining extra data, and seems simpler to reason about. Although if you really need to consume a predictable amount of data, the safest is probably to run the whole thing in a 'take'. John Lato

3 3

Why not Darcs?
by Andrew Coppin 29 Apr '11

29 Apr '11

I'm sure this must be a VFAQ, but... There seems to be universal agreement that Darcs is a nice idea, but is unsuitable for "real" projects. Even GHC keeps talking about getting rid of Darcs. Can anybody tell me what the "problems" with Darcs actually are?

29 52

Inputs to classic FRP: unsafeInterleaveIO/unsafePerformIO
by Edward Amsden 29 Apr '11

29 Apr '11

As far as I can tell, with classic FRP implementations (those which use behaviors as a first-class abstraction), the only way to create a behavior or event based on some external input (for instance keypresses or microphone input) is to do something with unsafePerformIO or unsafeInterleaveIO. A behavior is a value, which when evaluated at a specific time would have to either block its evaluation until input could be read, or check the input at that particular time. Is there any other way of implementing external behaviors besides that? -- Edward Amsden Student Computer Science Rochester Institute of Technology www.edwardamsden.com

3 7

Python is lazier than Haskell
by Henning Thielemann 29 Apr '11

29 Apr '11

I like to apply for the quote of the week. :-) "If Haskell is great because of its laziness, then Python must be even greater, since it is lazy at the type level." Dynamically typed languages only check types if they have to, that is if expressions are actually computed. Does this prove that laziness at type level as in Python is a great thing or does this prove that laziness at the value level as in Haskell is a bad thing or does this prove nothing? Hope for controversial discussion ...

22 26

Iteratee: manyToOne
by Dmitry Olshansky 29 Apr '11

29 Apr '11

Hello, does somewhere exist function with type like this - manyToOne :: [Iteratee a m b] -> Iteratee a m [b] ? I.e. I need to process one input through many Iteratees indepentently in constant space and collect results. It is similar by type with sequenceM but as far as I understand sequenceM won't use the same input for all Iteratees. Dima

3 5

-- Extension for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell -- Extension for "Pearls of Functional Algorithm Design" by Richard Bird, -- 2010, page 25 #Haskell -- This version assumes 3 disjoint ordered sets represented as sorted arrays.ts.
by caseyh＠istar.ca 28 Apr '11

28 Apr '11

-- Extension for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell -- O(log|X|+log|Y|+log|Z|) performance -- Question: is there a way to get the type signature as the following: -- smallest :: (Ord a) => Int -> [Array Int a] -> a module SelectionProblem where import Data.Array import Data.List -- Works on 2 finite ordered disjoint sets represented as sorted arrays. smallest :: (Ord a) => Int -> (Array Int a, Array Int a) -> a smallest k (xa,ya) = ~~~~search k (xa,ya) (0,m+1) (0,n+1) ~~~~~~~~where ~~~~~~~~(0,m) = bounds xa ~~~~~~~~(0,n) = bounds ya -- Removed some of the "indexitis" at the cost of calling another function. search :: (Ord a) => Int -> (Array Int a, Array Int a) -> (Int,Int) -> (Int,Int) -> a search k (xa,ya) (lx,rx) (ly,ry) ~~~~| lx == rx = ya ! (k+ly) ~~~~| ly == ry = xa ! (k+lx) ~~~~| otherwise = case (xa ! mx < ya ! my) of ~~~~~~~~~~~~~~~~~~~~~~(True) -> smallest2h k (xa,ya) ((lx,mx,rx),(ly,my,ry)) ~~~~~~~~~~~~~~~~~~~~~~(False) -> smallest2h k (ya,xa) ((ly,my,ry),(lx,mx,rx)) ~~~~~~~~~~~~~~~~~~where ~~~~~~~~~~~~~~~~~~~~~~mx = (lx+rx) `div` 2 ~~~~~~~~~~~~~~~~~~~~~~my = (ly+ry) `div` 2 -- Here the sorted arrays are in order by their middle elements. -- Only cutting the leading or trailing array by half. -- Here xa is the first array and ya the second array by their middle elements. smallest2h :: (Ord a) => Int -> (Array Int a, Array Int a) -> ((Int,Int,Int),(Int,Int,Int)) -> a smallest2h k (xa,ya) ((lx,mx,rx),(ly,my,ry)) = ~~~~case (k<=mx-lx+my-ly) of ~~~~~~(True) -> search k (xa,ya) (lx,rx) (ly,my) ~~~~~~(False) -> search (k-(mx-lx)-1) (xa,ya) (mx+1,rx) (ly,ry) ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- Works on 3 finite ordered disjoint sets represented as sorted arrays. smallest3 :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> a smallest3 k (xa,ya,za) = ~~~~-- On each recursive call the order of the arrays can switch. ~~~~search3 k (xa,ya,za) (0,bx+1) (0,by+1) (0,bz+1) ~~~~~~~~where ~~~~~~~~(0,bx) = bounds xa ~~~~~~~~(0,by) = bounds ya ~~~~~~~~(0,bz) = bounds za -- Removed some of the "indexitis" at the cost of calling another function. search3 :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> ~~~~~~~~~~~~(Int,Int) -> (Int,Int) -> (Int,Int) -> a search3 k (xa,ya,za) (lx,rx) (ly,ry) (lz,rz) ~~~~| lx == rx && ly == ry = za ! (k+lz) ~~~~| ly == ry && lz == rz = xa ! (k+lx) ~~~~| lx == rx && lz == rz = ya ! (k+ly) ~~~~| lx == rx = search k (ya,za) (ly,ry) (lz,rz) ~~~~| ly == ry = search k (xa,za) (lx,rx) (lz,rz) ~~~~| lz == rz = search k (xa,ya) (lx,rx) (ly,ry) ~~~~| otherwise = case (xa ! mx < ya ! my, xa ! mx < za ! mz, ya ! my < za ! mz) of ~~~~~~~~~~~~~~~~~~~~~~(True, True, True) -> smallest3h k (xa,ya,za) ((lx,mx,rx),(ly,my,ry),(lz,mz,rz)) -- a<b<c ~~~~~~~~~~~~~~~~~~~~~~(True, True, False) -> smallest3h k (xa,za,ya) ((lx,mx,rx),(lz,mz,rz),(ly,my,ry)) -- a<c<b ~~~~~~~~~~~~~~~~~~~~~~(False, True, True) -> smallest3h k (ya,xa,za) ((ly,my,ry),(lx,mx,rx),(lz,mz,rz)) -- b<a<c ~~~~~~~~~~~~~~~~~~~~~~(False, False, True) -> smallest3h k (ya,za,xa) ((ly,my,ry),(lz,mz,rz),(lx,mx,rx)) -- b<c<a ~~~~~~~~~~~~~~~~~~~~~~(True, False, False) -> smallest3h k (za,xa,ya) ((lz,mz,rz),(lx,mx,rx),(ly,my,ry)) -- c<a<b ~~~~~~~~~~~~~~~~~~~~~~(False, False, False) -> smallest3h k (za,ya,xa) ((lz,mz,rz),(ly,my,ry),(lx,mx,rx)) -- c<b<a ~~~~~~~~~~~~~~~~~~where ~~~~~~~~~~~~~~~~~~~~~~mx = (lx+rx) `div` 2 ~~~~~~~~~~~~~~~~~~~~~~my = (ly+ry) `div` 2 ~~~~~~~~~~~~~~~~~~~~~~mz = (lz+rz) `div` 2 -- Here the sorted arrays are in order by their middle elements. -- Only cutting the leading or trailing array by half. -- Here xa is the first array, ya the second array, and za the third array by their middle elements. smallest3h :: (Ord a) => Int -> (Array Int a, Array Int a, Array Int a) -> ~~~~~~~~((Int,Int,Int),(Int,Int,Int),(Int,Int,Int)) -> a smallest3h k (xa,ya,za) ((lx,mx,rx),(ly,my,ry),(lz,mz,rz)) = ~~~~case (k<=mx-lx+my-ly+mz-lz) of ~~~~~~(True) -> search3 k (xa,ya,za) (lx,rx) (ly,ry) (lz,mz) ~~~~~~(False) -> search3 (k-(mx-lx)-1) (xa,ya,za) (mx+1,rx) (ly,ry) (lz,rz) ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- To convert a list into an array indexed from 0. xa = listArray (0, length xs - 1) xs ya = listArray (0, length ys - 1) ys za = listArray (0, length zs - 1) zs xs = [0,17..90] ys = [1,13..69] zs = [7,24..91] ua = listArray (0, length us - 1) us va = listArray (0, length vs - 1) vs wa = listArray (0, length ws - 1) ws us = [0,17..100] vs = [101,121..200] ws = [201,221..300] -- *SelectionProblem> sort (xs++ys++zs) -- [0,1,7,13,17,24,25,34,37,41,49,51,58,61,68,75,85]

1 0

Trouble installing FileManipCompat
by Tony Miller 28 Apr '11

28 Apr '11

Hi, I'm trying to install FileManipCompat(well, really HStringTemplateHelpers, but the error is from FileManipCompat) and I'm getting this error: [1 of 1] Compiling System.FilePath.FindCompat ( System/FilePath/FindCompat.hs, dist/build/System/FilePath/FindCompat.o ) System/FilePath/FindCompat.hs:175:20: Not in scope: data constructor `State' I've attached the complete output of `cabal --verbose install HStringTemplateHelpers`.

3 4

ANNOUNCE: cereal-0.3.3.0
by Trevor Elliott 28 Apr '11

28 Apr '11

Hot on the heels of the last release, cereal-0.3.3.0 [1] adds support for parsing and rendering lazy ByteStrings. Most running functions in Data.Serialize.Get and Data.Serialize.Put now have lazy analogues, and Data.Serialize has gained encodeLazy and decodeLazy. This new functionality was made possible by the incremental parsing support added in cereal-0.3.1.0 by Lemmih. [1] http://hackage.haskell.org/package/cereal-0.3.3.0

2 2

Re: [Haskell-cafe] [Haskell] ANNOUNCE: zeno-0.2
by Benedict Eastaugh 28 Apr '11

28 Apr '11

Hi Will, I attended your presentation on Zeno at AngloHaskell last year and was really intrigued; it's great to see you've got a release up on Hackage, and I look forward to trying it out. Are you planning on making your source code repository publicly available on GitHub or somewhere similar? If nothing else it would be interesting to follow further developments between releases. All the best, Benedict.

2 1