April 2008 - Haskell-Cafe

Cannot understand liftM2
by Nicola Paolucci 13 Feb '12

13 Feb '12

Hi All, I'm loving learning Haskell quite a bit. It is stretching my brain but in a delightfull way. I've googled, I've hoogled but I haven't found a clear explanation for what exactly liftM2 does in the context below. Using the cool lambdabot "pointless" utility I found out that: > \x -> snd(x) - fst(x) is the same as: > liftM2 (-) snd fst I like the elegance of this but I cannot reconcile it with its type. I can't understand it. I check the signature of liftM2 and I get: Prelude> :t liftM2 Prelude> liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r Can someone help me understand what's happening here ? What does a Monad have to do with a simple subtraction ? What is actually the "m" of my example ? I am sure if I get this I'll be another step closer to illumination ... Thanks, Nick

15 18

Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)
by Dave Bayer 28 Dec '09

28 Dec '09

Here is another prime sieve. It is about half the length of the fastest contributed code (ONeillPrimes) and nearly as fast until it blows up on garbage collection: > % cat ONeillPrimes.hs | grep -v "^--" | wc > 185 1105 6306 > % cat BayerPrimes.hs | grep -v "^--" | wc > 85 566 2418 > > [Integer] -O 1*10^6 2*10^6 3*10^6 4*10^6 5*10^6 > --------------------------------------------------------- > ONeillPrimes | 3.555 | 7.798 | 12.622 | 18.927 | 23.529 > BayerPrimes | 3.999 | 8.895 | 18.003 | 22.977 | 38.053 I wrote this as an experiment in coding data structures in Haskell's lazy evaluation model, rather than as explicit data. The majority of the work done by this code is done by "merge"; the multiples of each prime percolate up through a tournament consisting of a balanced tree of suspended "merge" function calls. In order to create an infinite lazy balanced tree of lists, the datatype > data List a = A a (List a) | B [a] is used as scaffolding. One thinks of the root of the infinite tree as starting at the leftmost child, and crawling up the left spine as necessary. What I'm calling a "venturi" > venturi :: Ord a => [[a]] -> [a] merges an infinite list of infinite lists into one list, under the assumption that each list, and the heads of the lists, are in increasing order. This could be a generally useful function. If one can think of a better way to write "venturi", swapping in your code would in particular yield a faster prime sieve. I found that a tertiary merge tree was faster than a binary merge tree, because this leads to fewer suspensions. One can speed this code up a bit by interleaving strict and lazy calls, but I prefer to leave the code short and readable. It is bizarre that > trim p = let f m x = mod x m /= 0 in filter (f p) lurks in the prime sieve code, but it is only used with primes of size up to the square root of the largest output prime. I tried more thoughtful alternatives, and they all slowed down the sieve. Sometimes dumb is beautiful. Thanks to apfelmus for various helpful remarks that lead me to think of this approach. Here is the code: > module BayerPrimes (venturi,primes) where > > -- Code for venturi :: Ord a => [[a]] -> [a] > > merge :: Ord a => [a] -> [a] -> [a] -> [a] > merge xs@(x:xt) ys@(y:yt) zs@(z:zt) > | x <= y = if x <= z > then x : (merge xt ys zs) > else z : (merge xs ys zt) > | otherwise = if y <= z > then y : (merge xs yt zs) > else z : (merge xs ys zt) > merge _ _ _ = undefined > > data List a = A a (List a) | B [a] > > mergeA :: Ord a => List a -> List a -> List a -> List a > mergeA (A x xt) ys zs = A x (mergeA xt ys zs) > mergeA (B xs) ys zs = mergeB xs ys zs > > mergeB :: Ord a => [a] -> List a -> List a -> List a > mergeB xs@(x:xt) ys@(A y yt) zs = case compare x y of > LT -> A x (mergeB xt ys zs) > EQ -> A x (mergeB xt yt zs) > GT -> A y (mergeB xs yt zs) > mergeB xs (B ys) zs = mergeC xs ys zs > mergeB _ _ _ = undefined > > mergeC :: Ord a => [a] -> [a] -> List a -> List a > mergeC xs@(x:xt) ys@(y:yt) zs@(A z zt) > | x < y = if x < z > then A x (mergeC xt ys zs) > else A z (mergeC xs ys zt) > | otherwise = if y < z > then A y (mergeC xs yt zs) > else A z (mergeC xs ys zt) > mergeC xs ys (B zs) = B $ merge xs ys zs > mergeC _ _ _ = undefined > > root :: Ord a => List a -> [List a] -> [a] > root (A x xt) yss = x : (root xt yss) > root (B xs) (ys:zs:yst) = root (mergeB xs ys zs) yst > root _ _ = undefined > > wrap :: [a] -> List a > wrap [] = B [] > wrap (x:xt) = A x $ B xt > > triple :: Ord a => [List a] -> [List a] > triple (x:y:z:xs) = mergeA x y z : (triple xs) > triple _ = undefined > > group :: Ord a => [List a] -> [List a] > group (x:y:xt) = x : y : (group $ triple xt) > group _ = undefined > > venturi :: Ord a => [[a]] -> [a] > venturi (x:xt) = root (wrap x) $ group $ map wrap xt > venturi _ = undefined > > -- Code for primes :: Integral a => [a] > > diff :: Ord a => [a] -> [a] -> [a] > diff xs@(x:xt) ys@(y:yt) = case compare x y of > LT -> x : (diff xt ys) > EQ -> (diff xt yt) > GT -> (diff xs yt) > diff _ _ = undefined > > trim :: Integral a => a -> [a] -> [a] > trim p = let f m x = mod x m /= 0 in filter (f p) > > seed :: Integral a => [a] > seed = [2,3,5,7,11,13,17] > > wheel :: Integral a => [a] > wheel = drop 1 [ m*j + k | j <- [0..], k <- ws ] > where m = foldr1 (*) seed > ws = foldr trim [1..m] seed > > multiples :: Integral a => [a] -> [[a]] > multiples ws = map fst $ tail $ iterate g ([], ws) > where g (_,ps@(p:pt)) = ([ m*p | m <- ps ], trim p pt) > g _ = undefined > > primes :: Integral a => [a] > primes = seed ++ (diff wheel $ venturi $ multiples wheel)

6 8

I love purity, but it's killing me.
by Tom Hawkins 09 Jun '09

09 Jun '09

I've been programming with Haskell for a few years and love it. One of my favorite applications of Haskell is using for domain specific languages. However, after designing a handful of DSLs, I continue to hit what appears to be a fundamental hurdle -- or at least I have yet to find an adequate solution. My DSLs invariably define a datatype to capture expressions; something like this: data Expression = Add Expression Expression | Sub Expression Expression | Variable String | Constant Int deriving Eq Using the datatype Expression, it is easy to mass a collections of functions to help assemble complex expressions, which leads to very concise programs in the DSL. The problem comes when I want to generate efficient code from an Expression (ie. to C or some other target language). The method I use invovles converting the tree of subexpressions into an acyclic graphic to eliminate common subexpressions. The nodes are then topologically ordered and assigned an instruction, or statement for each node. For example: let a = Add (Constant 10) (Variable "i1") b = Sub (Variable "i2") (Constant 2) c = Add a b would compile to a C program that may look like this: a = 10 + i1; b = i2 - 2; c = a + b; The process of converting an expression tree to a graph uses either Eq or Ord (either derived or a custom instance) to search and build a set of unique nodes to be ordered for execution. In this case "a", then "b", then "c". The problem is expressions often have shared, equivalent subnodes, which dramatically grows the size of the tree. For example: let d = Add c c e = Add d d -- "e" now as 16 leaf nodes. As these trees grow in size, the equality comparison in graph construction quickly becomes the bottleneck for DSL compilation. What's worse, the phase transition from tractable to intractable is very sharp. In one of my DSL programs, I made a seemingly small change, and compilation time went from milliseconds to not-in-a-million-years. Prior to Haskell, I wrote a few DSLs in OCaml. I didn't have this problem in OCaml because each "let" expression was mutable, and I could use the physical equality operator to perform fast comparisons. Unfortunately, I have grown to love Haskell's type system and its lack of side effects, and could never go back. Is there anything that can be done to dramatically speed up comparisons, or is there a better approach I can take to extract common subexpressions? I should point out I have an opportunity to get Haskell on a real industrial application. But if I can't solve this problem, I may have to resort to far less eloquent languages. :-( Thanks for any and all help. -Tom

17 36

HDBC or HSQL
by George Moschovitis 19 Oct '08

19 Oct '08

Dear devs, I am a Haskell newbie and I would like to hear your suggestions regarding a Database conectivity library: HSQL or HDBC ? which one is better / more actively supported? thanks in advance, -g. -- http://phidz.com http://blog.gmosx.com http://cull.gr http://www.joy.gr http://nitroproject.org

15 25

External Sort and unsafeInterleaveIO
by Ben 11 Oct '08

11 Oct '08

hi folks -- a haskell newbie here, searching for comments and wisdom on my code. i had a project to try to implement "external sort" in haskell as a learning exercise. (external sort is sorting a list that is too large to fit in main memory, by sorting in chunks, spooling to disk, and then merging. more properly there probably should be multiple stages, but for simplicity i'm doing a one-stage external sort.) the trick is the number of files can quickly grow very large, so it is best to use one large file and seek inside it around. however as one can imagine the order-of-IO-operations becomes a bit tricky, if you're seeking file handles around underneath Data.ByteString.Lazy's nose. but late this night after not thinking about it for a while i had a brainstorm: rewrite hGetContents to keep the handle position in the right place! it's all about judicious use of unsafeInterleaveIO..... it seems to be rather fast, strangely faster than the usual "sort" at times. it also seems to have nice memory characteristics, though not perfect. it's hard to test because the normal "sort" function takes too much RAM on large lists, making my computer swap like mad. i'd appreciate any testing, comments and suggestions from the haskell gods out there. my thanks to the Data.ByteString.Lazy, Data.Binary, and Data.Edison people, who made this rather easy, once I grokked unsafeInterleaveIO. thanks and take care, B > module ExternalSort where Sort a list of Ords "offline." We're doing this to be able to sort things without taking up too much memory (for example sorting lists too large to fit in RAM.) Laziness is imperative, as is the order-of-operations. > import Control.Monad > import Data.List > import qualified Data.Binary as Bin > import qualified Data.ByteString.Lazy as B > import qualified Data.ByteString as P (hGetNonBlocking, null) > import Data.ByteString.Base (LazyByteString(LPS)) > import Foreign.Storable (sizeOf) > import System.IO (openFile, hClose, hSeek, hTell, hIsEOF, hWaitForInput, > Handle, IOMode(ReadMode, WriteMode), > SeekMode(AbsoluteSeek)) > import System.IO.Unsafe (unsafeInterleaveIO) > > import qualified Data.Edison.Seq.ListSeq as LS > import qualified Data.Edison.Coll.SplayHeap as Splay Conceptually, we sort a list in blocks, spool blocks to disk, then merge back. However for IO performance it is better to read off chunks of elements off the sorted blocks from disk instead of elements-at-a-time. It would be better if these were in KBytes instead of # of elements. > blocksize :: Int > blocksize = 10000 Turn a list into a list of chunks. > slice :: Int -> [a] -> [[a]] > slice _ [] = [] > slice size l = (take size l) : (slice size $ drop size l) Turn a list into a list of blocks, each of which is sorted. > blockify :: (Ord a) => Int -> [a] -> [[a]] > blockify bsize l = map sort $ slice bsize l Serialize a block, returning the (absolute) position of the start. > dumpBlock :: (Ord a, Bin.Binary a) => Handle -> [a] -> IO Integer > dumpBlock h b = do > start <- hTell h > B.hPut h $ Bin.encode b > return start The actual sorting function. We blockify the list, turning it into a list of sorted blocks, and spool to disk, keeping track of offsets. We then read back the blocks (lazily!), and merge them. > externalSort [] = do return [] > externalSort l = do > h <- openFile "ExternalSort.bin" WriteMode > idx <- mapM (\x -> dumpBlock h x) (blockify blocksize l) > hClose h > h <- openFile "ExternalSort.bin" ReadMode > blocks <- mapM (\x -> do {bs <- hGetContentsWithCursor h x; > return $ Bin.decode bs}) idx > return (kMerge $ blocks) Merging chunks. K-way merge (and in fact external sort in general) is detailed in Knuth, where he recommends tournament trees. The easiest thing is to probably use one of Okasaki's heaps. I'll use splay heaps, because I don't know any better. It would be better if I changed Ord for blocks to only check the first element. > kMerge :: (Ord a) => [[a]] -> [a] > kMerge [] = [] > kMerge l = > let h = Splay.fromSeq l in > kM (Splay.minElem h) (Splay.deleteMin h) > where > kM :: (Ord a) => [a] -> Splay.Heap [a] -> [a] > kM l h > | h == Splay.empty = l > | otherwise = > let next = Splay.minElem h > (f, b) = span (\x -> x <= head next) l > in > f ++ (kM next (if null b then Splay.deleteMin h > else (Splay.insert b $ Splay.deleteMin h))) > > kMergeSort :: (Ord a) => [a] -> [a] > kMergeSort l = kMerge $ blockify blocksize l This is a version of hGetContents which resets its handle position between reads, so is safe to use with interleaved handle seeking. > hGetContentsWithCursor :: Handle -> Integer -> IO B.ByteString > hGetContentsWithCursor = hGetContentsWithCursorN defaultChunkSize > > hGetContentsWithCursorN :: Int -> Handle -> Integer -> IO B.ByteString > hGetContentsWithCursorN k h start = (lazyRead start) >>= return . LPS > where > lazyRead start = unsafeInterleaveIO $ loop start > > loop start = do > hSeek h AbsoluteSeek start > ps <- P.hGetNonBlocking h k > --TODO: I think this should distinguish EOF from no data available > -- the otherlying POSIX call makes this distincion, returning either > -- 0 or EAGAIN > if P.null ps > then do eof <- hIsEOF h > if eof then return [] > else hWaitForInput h (-1) > >> (loop start) > else do > pos <- hTell h > pss <- lazyRead pos > return (ps : pss) > > defaultChunkSize :: Int > defaultChunkSize = 32 * k - overhead > where k = 1024 > overhead = 2 * sizeOf (undefined :: Int)

5 6

SYB with class: Bug in Derive.hs module
by Alexey Rodriguez Yakushev 16 Sep '08

16 Sep '08

Hi people (and Ralf and Alex), I found a bug in the SYB with class library when trying to implement generic equality. I am hoping that someone in the Cafe (maybe Ralf) can confirm it is a bug, or maybe show me that I am doing something wrong. I am using the "Scrap your boilerplate with class" library (http:// homepages.cwi.nl/~ralf/syb3/). More precisely, I am using the library distributed by the HAppS project, because it works with GHC 6.8 . You can get the repository as follows: darcs get http://happs.org/HAppS/syb-with-class However, the offending module (Derive.hs) produces broken instances in both distributions. The bug: ---------- Generic equality needs type safe casting when implemented in SYB3, I have tried both the gzipwith variant and using Pack datatypes (geq*.hs in the first distribution). However, both functions loop when applied to a tree value. This loop occurs when the functions try to cast one of the arguments. I have managed to reduce the error to a smaller source file that I send attached. It does the following: > main = print typeReps > > tree = (Bin (Leaf 1) (Leaf 2))::BinTree Int > > data Pack = forall x. Typeable x => Pack x > > packedChildren = gmapQ geqCtx Pack tree > > typeOfPack (Pack x) = typeOf x > > typeReps = map typeOfPack packedChildren Basically the tree is transformed into a list of Pack-ed values and then to a list of type representations. This program loops at "typeOf" when you call "main". The Data instance that Derive generates is as follows: > instance (Data ctx a, > Data ctx (BinTree a), > Sat (ctx (BinTree a))) => > Data ctx (BinTree a) where Note the recursive |Data ctx (BinTree a)| in the context. If I get rid of it (a correct manual instance is also included in the attachment) the example works. I thought of removing this from the context in the Derive source. But maybe I might break some other use cases. So I am asking for help! Should Derive be fixed? How? Cheers, Alexey

3 2

Arrow without `>>>'
by Valery V. Vorotyntsev 03 Sep '08

03 Sep '08

Hi, friends, I've built GHC from darcs, and... Could anybody tell me, what's the purpose of Arrow[1] not having `>>>' method? 1. http://darcs.haskell.org/packages/base/Control/Arrow.hs $ ghci GHCi, version 6.9.20080104: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude> :m + Control.Arrow Prelude Control.Arrow> :i Arrow class (Control.Category.Category a) => Arrow a where arr :: (b -> c) -> a b c pure :: (b -> c) -> a b c first :: a b c -> a (b, d) (c, d) second :: a b c -> a (d, b) (d, c) (***) :: a b c -> a b' c' -> a (b, b') (c, c') (&&&) :: a b c -> a b c' -> a b (c, c') -- Defined in Control.Arrow instance Arrow (->) -- Defined in Control.Arrow instance (Monad m) => Arrow (Kleisli m) -- Defined in Control.Arrow Prelude Control.Arrow> Leaving GHCi. I can't build[2] arrows-0.3 package without `>>>' in Arrow. 2. vvv@fun:~/src/arrows$ darcs w { hunk ./Control/Arrow/Operations.hs 36 +import Control.Category ((>>>)) hunk ./Control/Arrow/Transformer/CoState.hs 23 +import Control.Category ((>>>)) } vvv@fun:~/src/arrows$ runhaskell Setup build Preprocessing library arrows-0.3... Building arrows-0.3... [ 3 of 12] Compiling Control.Arrow.Transformer.CoState ( Control/Arrow/Transformer/CoState.hs, dist/build/Control/Arrow/Transformer/CoState.o ) Control/Arrow/Transformer/CoState.hs:29:7: `>>>' is not a (visible) method of class `Arrow' The question arises "should I?", but this is one of lambdabot's[3] depencies. 3. http://code.haskell.org/lambdabot/ Thanks a lot! -- vvv

3 3

CouchDB module in Yhc source tree: clarification, and small problems with other packages
by Dimitry Golubovsky 21 Aug '08

21 Aug '08

Hi, Don asked: > Are we likely to see the couchdb bindings released as a standalone > library for the wider community? Let me explain a little bit why the CouchDB module appears in the Yhc repo. As the next stage of the Yhc/Javascript project, I am trying to set up a web service where people might upload some Haskell code (or reference to such code, these details haven't been clarified yet), and get it compiled by background Yhc/ycr2js batch job, returning a HTML page with Javascript in response. CouchDB was picked* as intermediate storage for this project. Therefore an interface module was needed, so I wrote one. This module, `Database.CouchDB' is not 100% finished; it was coded up to satisfy the needs of the first utility I wrote, `cdbup' which is currently capable of uploading a text (utf-8 expected) or a binary file as a document attachment to CouchDB. So some functionality hasn't been coded yet, although it will definitely be, as the project develops. Regarding packaging, I hope I will eventually put it on Hackage, but there are some problems with another packages which I'll try to explain here, so maybe those packages' developers suggest something. 1. Text.JSON. This module was picked from Jun Mukai's haskellnet package (http://darcs.haskell.org/SoC/haskellnet/) One problem with this package, it needs too many dependencies (while JSON module relies only on Packrat parser). I had to extract the JSON module into Yhc tree; can the haskellnet package be split somehow into orthogonal sub-packages, and maybe one toplevel package which would pull all parts together if used? 2. Text.JSON again. I had to change the pNumber function (parser for numeric nodes) replacing the '1'..'9' digits range with '0' .. '9'. Otherwise it did not handle JSON-encoded numbers equal to zero. I am not sure I was 100% right, so perhaps some JSON experts here might correct me. 3. Packrat parser does not seem to be packaged anywhere else, does it? 4. The dataenc package (http://code.haskell.org/dataenc/devo/) from which I pulled the Codec.Binary.Base64 module. The package may need some adjustment to GHC 6.8.x packages structure as only "base" listed in build-depends does not seem to be enough: when building it, Cabal complains for hidden packages such as collections (which I had to add manually to the cabal file), etc. Is it some problem with my GHC setup, or does just the dataenc.cabal need to be updated? So, in order to get things done quicker, I pulled the said pieces from their packages into Yhc tree. For packaging the CouchDB interface, definitely these duplicates need to be removed. Other packages that CouchDB relies upon, are**: base, network, HTTP, filepath, base64-string, utf8-string Thanks for the interest in CouchDB interface, and feel free to ask any questions. --- * before support form IBM/Apache was announced, but this recent development definitely increases interest to CouchDB ** Just from the -package options I used to compile it; I may have something omitted here. -- Dimitry Golubovsky Anywhere on the Web

5 5

NW Functional Programming Interest Group
by Greg Meredith 18 Jul '08

18 Jul '08

All, Apologies for multiple listings. A small cadre of us are organizing a Northwest Functional Programming Interest Group (hey... NWFPIG, that's kinda funny). Our first official meeting is at the The Seattle Public Library 1000 - 4th Ave. Seattle, WA 98104 from 17:00 - 18:00 on February 20th. On the first meeting's agenda we'll be - giving people who are interested in or actively using FP for work or play a chance to meet - seeking to build up a pipeline of presentations and guest speakers - trying to keep organizational mishigosh to a minimum Hope to see you there. Monadically yours, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 806 55th St NE Seattle, WA 98105 +1 206.650.3740 http://biosimilarity.blogspot.com

2 7

I/O system brokenness with named pipes
by John Goerzen 05 Jul '08

05 Jul '08

So I have a need to write data to a POSIX named pipe (aka FIFO). Long story involving a command that doesn't have an option to read data from stdin, but can from a named pipe. I have created the named pipe from Haskell no problem. But I can't use writeFile to write data to it. Worse, it returns: *** Exception: /tmp/bakroller.zD0xHj/fifo: openFile: does not exist (No such device or address) which is completely false, as it *does* exist, and I can cat to it as expected. The call should block until everything is read on the remote end. I thought maybe writeFile is being weird, so I tried: openFile "/tmp/bakroller.zD0xHj/fifo" WriteMode Same thing. There is no logical reason I can see for this behavior. In fact, something must be going to *extra* effort to avoid writing to a named pipe, and I can't work out why. Named pipes are a standard, useful part of a system and shouldn't be ignored like this. Interestingly, readFile works fine on a named pipe. What's going on here? Am I going to have to resort to the System.Posix interface just to be able to write to a named pipe? -- John

10 20