November 2007 - 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

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

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

Libraries need a new owner
by Adrian Hey 27 Mar '08

27 Mar '08

Hello Folks, As some of you will be aware, I have been working on various Map implementations that currently live here.. http://code.haskell.org/collections/collections-ghc6.8 The libs in question being Data.Tree.AVL, Data.Trie.General and a few other bits like Data.COrdering and the AVL based Data.Map/Set clones. Well, I have decided to stop work on these. So they need a new owner if they're going to go anywhere. If anyone is interested in the job then I suggest they contact myself or Jean-Philippe Bernardy. Of course I will be happy to provide any help or advise anyone who takes over these libs may feel they need from me. I might even contribute a few patches from time to time myself :-) Thanks -- Adrian Hey

3 7

Export Haskell Libraries
by SevenThunders 12 Feb '08

12 Feb '08

I've finished a good sized Haskell project which I now must expose as a library (along with a lot of C code) to my fellow engineers. I had originally devoped my code on Windows XP and managed to learn how to wrap my Haskell code in a DLL and create an MSVC linkable library stub for the DLL. Although involved, the output in windows is relatively transparent in that as long as the paths are available to the Haskell runtime libraries and my DLL, linking is straightforward. Now however I find I must export the same libraries to linux. I decided to get 'smart' and repackage my build tools using CMAKE and cabal. Building the C object files is no problem and even configuring Cabal to generate my executables is not too painful. However the pain begins when one tries to link any Haskell object files or libraries to an external C program. Using ghc -v during the build reveals that gcc has about 50 -u flag arguments and links to 9 or 10 different libraries. Given that my little component is just a tiny part of a large software project involving many more engineers and many man years of work, it's not going to be fun to link my little library using all these crazy build flags to a large external project, especially when order is important. Wouldn't it be nice if there were a single run time library I could link to, (or even generate on the fly) that didn't have this intricate build step. How is ghc/Haskell supposed to integrate with the rest of the software world? A related issue in the building of my export libraries is cabal itself. I want to package my own library with some external object files etc and some Haskell code. It's easily done with ar and the correct object files. Unfortunately it is not clear from the documentation how I can force cabal to place the object files and generated stub files in a place where I can use them. (CMake is kind of forcing me to have them reside with the source for reasons I don't want to go into here.) I instead find myself copying the object files (*.o) back into the source directory from an obscure tmp directory several layers down from the source directory. This is not particularly portable and is probably quite fragile once someone decides to change the directory hiearcharchy in cabal. I guess I am surprised that on linux, with all of it's amazing software development tools, that Haskell export libraries would be this tricky to develop. -- View this message in context: http://www.nabble.com/Export-Haskell-Libraries-tf3569747.html#a9972866 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

6 10

viewing HS files in Firefox
by Isaac Dupree 10 Jan '08

10 Jan '08

When I try to go to one of the Module.hs files, e.g. on darcs.haskell.org, it now has type HS and Firefox refuses to display it (and only lets me download it). Does anyone know how to make Firefox treat certain file types as others (HS as plain text, in particular)? so that I can browse them with any convenience Thanks, Isaac

13 16

Cabal and DB packages
by manu 08 Jan '08

08 Jan '08

Hello, I'm trying to do something that should be fairly simple, installing some DB package so I can use MySQL or SQLite. However I've had troubles building HSQL, HaskellDB and Takusen before giving up (I am using ghc 6.8.1 and Cabal-1.2.2.0). ------------------ with HSQL : Database/HSQL.hsc:66:7: Could not find module `System.Time': it is a member of package old-time-1.0.0.0, which is hidden so I added 'old-time' to the 'build-depends' line in the .cabal file but then it fails building with Building hsql-1.7... [1 of 2] Compiling Database.HSQL.Types ( Database/HSQL/Types.hs, dist/ build/Database/HSQL/Types.o ) Database/HSQL/Types.hs:134:18: Not in scope: type variable `forall' Database/HSQL/Types.hs:134:25: Not in scope: type variable `a' Database/HSQL/Types.hs:134:27: Illegal operator `.' in type `forall a . (Int -> FieldDef -> (FieldDef -> CString -> Int -> IO a) -> IO a)' (Use -XTypeOperators to allow operators in types) etc... At this point, it goes over my head... --------------- What the hell, I'll use HaskellDB and FlatDB, but then I get this message while building HaskellDB : src/Database/HaskellDB/HDBRec.hs:106:11: Illegal signature in pattern: l f a Use -XPatternSignatures to permit it when I add 'PatternSignatures' to the 'Extensions:' line in .cabal, it fails configuring with : Setup.hs: haskelldb.cabal:8: Parse of field 'extensions' failed: Jeeeesus, nevermind, I'll try Takusen --------------- with Takusen : $ runhaskell Setup.hs configure Setup.hs:26:7: Could not find module `Distribution.Program': Use -v to see a list of the files searched for. I give up... ---------------- Is there any simple way to do it though ? Is there any problems with Cabal that I need to work around ? Help !! Manu

4 3