January 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

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

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

Cryptographic hash uniquness (was [Haskell-cafe] Simple network client)
by Peter Verswyvelen 11 May '08

11 May '08

>winds up having a write cache, which is mutable in practice. The >interesting thing is that the block's location is the cryptographic >hash of its contents, which leads to all sorts of neat properties (as >well as requiring immutability). That's interesting. When I developed a version control system for a customer, I also used a cryptographic hash as the database key of file+content in question, but I was afraid I might have clashes (two files with different content generating the same hash)... My intuition told me that the odds of two cryptographic hashes (on meaningful content) colliding was much less than the earth being destroyed by an asteroid... But this is just intuition... What does computer science tell us about this? Thank you, Peter

6 6

Old editions of The Monad.Reader lost
by Henk-Jan van Tuyl 10 May '08

10 May '08

L.S., Now that all hawiki pages have been removed, we have lost some valuable information. For example The Monad.Reader; on http://www.haskell.org/haskellwiki/The_Monad.Reader it says: Older editions can be found on the old Haskell wiki – they haven't been included here for licensing reasons. The page it links to, a hawiki page, has dissappeared. I propose to bring at least the The Monad.Reader pages back. Backups of these pages can be found at the Wayback Machine, but there is no guarantee that will always be there. -- Met vriendelijke groet, Henk-Jan van Tuyl -- http://functor.bamikanarie.com http://Van.Tuyl.eu/ --

3 6

Anyone mind proofing a short monad transformers explanation?
by Jack Kelly 22 Apr '08

22 Apr '08

I sent this to a friend who asked me about monad transformers and he reckons it should be saved somewhere. If anyone feels up to giving it a quick fact-check, that'd be great. I'm not sure what to do with it, though. It doesn't seem to be made of the right stuff for a tutorial but I'm not sure what to do with it. --- SNIP --- Basically it's like making a double, triple, quadruple, ... monad by wrapping around existing monads that provide wanted functionality. You have an innermost monad (usually Identity or IO but you can use any monad). You then wrap monad transformers around this monad to make bigger, better monads. Concrete example: Suppose I was writing a server. Each client thread must be of type IO () (that's because forkIO :: IO () -> IO ThreadID)). Suppose also that this server has some configuration that (in an imperative program) would be global that the clients all need to query. > data Config = Config Foo Bar Baz One way of doing this is to use currying and making all the client threads of type Config -> IO (). Not too nice because any functions they call have to be passed the Config parameter manually. The Reader monad solves this problem but we've already got one monad. We need to wrap IO in a ReaderT. The type constructor for ReaderT is ReaderT r m a, with r the shared environment to read from, m the inner monad and a the return type. Our client_func becomes: > client_func :: ReaderT Config IO () We can then use the ask, asks and local functions as if Reader was the only Monad: (these examples are inside do blocks) > p <- asks port (Assuming some function port :: Config -> Int or similar.) To do stuff in IO (or in the general case any inner monad) the liftIO function is used to make an IO function work in this wrapped space: (given h :: Handle, the client's handle) > liftIO $ hPutStrLn h "You lose" > liftIO $ hFlush h IO is once again special. For other inner monads, the lift function does the same thing. Note also that IO has no transformer and must therefore always be the innermost monad. This is all well and good, but the client_func now has type ReaderT Config IO () and forkIO needs a function of type IO (). The escape function for Reader is runReader :: Reader r a -> r -> a and similarly for ReaderT the escape function is runReaderT :: ReaderT r m a -> r -> m a: (Given some c :: Config that's been assembled from config files or the like) > forkIO (runReaderT client_func c) Will do the trick. Monad transformers are like onions. They make you cry but you learn to appreciate them. Like onions, they're also made of layers. Each layer is the functionality of a new monad, you lift monadic functions to get into the inner monads and you have transformerised functions to unwrap each layer. They're also like a present in that regard: in this example we unwrapped the outer wrapping paper to get to the present: an object of type IO (), which lets us make haskell do something.

3 2

Separate a string into a list of strings
by Sara Kenedy 18 Apr '08

18 Apr '08

Hi all, I want to write a function to separate a string into a list of strings separated by commas. Example: separate :: String -> [String] separate "Haskell, Haskell, and Haskell" = ["Haskell", "Haskell", "and Haskell"] If anyone has some ideas, please share with me. Thanks. S.

14 35