July 2008 - Haskell-Cafe

Commutative monads vs Applicative functors
by Ronald Guida 09 Jul '16

09 Jul '16

I have a few questions about commutative monads and applicative functors. >From what I have read about applicative functors, they are weaker than monads because with a monad, I can use the results of a computation to select between alternative future computations and their side effects, whereas with an applicative functor, I can only select between the results of computations, while the structure of those computations and their side effects are fixed in advance. But then there are commutative monads. I'm not exactly sure what a commutative monad is, but my understanding is that in a commutative monad the order of side effects does not matter. This leads me to wonder, are commutative monads still stronger than applicative functors, or are they equivalent? And by the way, what exactly is a commutative monad?

6 6

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

really difficult for a beginner like me...
by Ivan Amarquaye 24 Mar '10

24 Mar '10

Hi everyone, this is my first posting on here and this was what drove me here and the quest to know more as i anticipate a lot of help and direction in this quite new and different environment haskell.I have this paper that i'm working on and need to solve these scenarios/ cases based on some sample codes: Scenarios/cases: 1) Allow words to be hyphenated and treat the hyphenated word as a single word (including the hyphen). 2) As for no. 2 but if the hyphen is the last character on a line treat the hyphenated word as a single word without the hyphen. 3) Treat a capitalised word (one or more capital letters) the same as lower case, i.e. only the lower case word appears in the index. 4) Treat a word ending in an ‘s’ as a plural and thus the same as the singular, i.e. only the singular appears in the index. 5) As for no. 5 but (a) treat suffix ‘ss’ as not a plural; and (b) treat the plural suffixes ‘sses’, ‘zzes’, ‘oes’, ‘xes’, ‘shes’, ‘ches’ the same as the singular, i.e. without the ‘es’, e.g. “branches” (except for 4- and 5-letter plurals with suffices ‘oes’ and ‘ches’, e.g. “floes”, and 4-letter plural suffix ‘xes’); and (c) treat the plural suffix ‘ies’ (except for 4-letter plurals, e.g. “pies”) as the singular suffix ‘y’. 6) Make the output more readable in the form of an index table. 7) Use an output file 8) Include a user-friendly menu by which the user can choose input and output file names. This is the code i'm supposed tomodify and in some cases create new functions to support.I also need some explanation as the various approaches in solving them.............................................................................................. The function makeIndex given a document produces a list of entries. Each entry is a word and a list of line numbers (for words > 4 letters) Type definitions: import Prelude -- hiding (Word) -- predefined Word hidden, so we can define ours -- type String = [Char] defined in Prelude type Doc = String type Line = String type Word = String -- our version makeIndex :: Doc -> [ ([Int], Word) ] A data-directed design considers a sequence of functions (i.e using composition operator ‘.’) to transform the document of type, Doc, into an index of type, [ ([Int], Word) ]. splitUp the document, doc, into a list of lines, [Line]. numLines pairs each line with a line number, [(Int, Line)]. allNumWords splits lines into words and line no., [(Int, Word)]. sortLs sorts words into alphabetical order, [(Int, Word)]. makeLists makes a list for each line number, [([Int], Word)]. amalgamate nos. into a list of nos. for each word, [([Int], Word)]. shorten into a list for words > 4 letters, [([Int], Word)]. makeIndex = shorten . -- [([Int], Word)] -> [([Int], Word)] amalgamate . -- [([Int], Word)] -> [([Int], Word)] makeLists . -- [(Int, Word)] -> [([Int], Word)] sortLs . -- [(Int, Word)] -> [(Int, Word)] allNumWords . -- [(Int, Line)] -> [(Int, Word)] numLines . -- [Line] -> [(Int, Line)] splitUp -- Doc -> [Line] Last -- [a] -> [a ] splitUp function splitUp :: Doc -> [Line] splitUp [] = [] splitUp text = takeWhile (/='\n') text : -- first line (splitUp . -- splitup other lines dropWhile (==’\n’) . -- delete 1st newline(s) dropWhile (/='\n')) text -- other lines Example: splitUp “hello world\n\nnext world” => [“hello world”, “next world”] numLines function: numLines :: [Line] -> [(Int, Line)] numLines lines -- list of pairs of = zip [1 .. length lines] lines -- line no. & line Example: numLines [“hello world”, “next world”] => [(1, “hello world”), (2, “next world”)] splitWords function: -- for each line -- a) split into words -- b) attach line no. to each word splitWords :: Line -> [Word] -- a) splitWords [ ] = [ ] splitWords line = takeWhile isLetter line : -- first word in line (splitWords . -- split other words dropWhile (not.isLetter && Last ==’-’) . -- delete separators dropWhile isLetter) line -- other words where isLetter ch = (‘a’<=ch) && (ch<=’z’) || (‘A’<=ch) && (ch<=’Z’) Example: splitWords “hello world” => [“hello”, “world”] allNumWords function: numWords :: (Int, Line) -> [(Int, Word)] -- b) numWords (number, line) = map addLineNum ( splitWords line) -- all line pairs where addLineNum word = (number, word) -- a pair allNumWords :: [(Int, Line)] -> [(Int, Word)] allNumWords = concat . map numWords -- doc pairs Examples: addLineNum “hello” => (1, “hello”) numWords (1, “hello world”) => [(1, “hello”), (1, “world”)] allNumWords [(1, “hello world”), (2, “next world”)] => [(1, “hello”), (1, “world”), (2, “next”), (2, “world”)] SortLs function: sortLs :: [(Int, Word)] -> [(Int, Word)] sortLs [ ] = [ ] sortLs (a:x) = sortLs [b | b <- x, compare b a] -- sort 1st half ++ [a] ++ -- 1st in middle sortLs [b | b <- x, compare a b] -- sort 2nd half where compare (n1, w1) (n2, w2) = (w1 < w2) -- 1st word less || (w1 == w2 && n1 < n2) -- check no. Example: sortLs [(1, “hello”), (1, “world”), (2, “next”), (2, “world”)] => [(1, “hello”), (2, “next”), (1, “world”), (2, “world”)] makeLists function: makeLists :: [(Int, Word)] -> [([Int], Word)] makeLists = map mk -- all pairs where mk (num, word) = ([num], word) -- list of single no. Examples: mk (1, “hello”) => ([1], “hello”) makeLists [(1, “hello”), (2, “next”), (1, “world”), (2, “world”)] => [([1], “hello”), ([2], “next”), ([1], “world”), ([2], “world”)] Amalgamate function: amalgamate :: [([Int], Word)] -> [([Int], Word)] amalgamate [ ] = [ ] amalgamate [a] = [a] amalgamate ((n1, w1) : (n2, w2) : rest) -- pairs of pairs | w1 /= w2 = (n1, w1) : amalgamate ((n2, w2) : rest) | otherwise = amalgamate ((n1 ++ n2, w1) : rest) -- if words are same grow list of numbers Example: amalgamate [([1], “hello”), ([2], “next”), ([1], “world”), ([2], “world”)] => [([1], “hello”), ([2], “next”), ([1, 2], “world”)] Shorten function: shorten :: [([Int], Word)] -> [([Int], Word)] shorten = filter long -- keep pairs >4 where long (num, word) = length word > 4 -- check word >4 Example: shorten [([1], “hello”), ([2], “next”), ([1, 2], “world”)] => [([1], “hello”), ([1, 2], “world”)] _________________________________________________________________ Connect to the next generation of MSN Messenger http://imagine-msn.com/messenger/launch80/default.aspx?locale=en-us&source=…

6 8

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

Re: Haskell on ARM (was Re: ANN: Topkata)
by Jeremy Apthorp 30 Jan '09

30 Jan '09

2008/6/25 Braden Shepherdson <Braden.Shepherdson(a)gmail.com>: > Jeremy Shaw wrote: >> >> If any does attempt to build for the ARM, please, please, please, >> document what you do in the wiki. And, if you do, edit the wiki as you >> go, you definitely won't be able to remember what you did after the >> fact. (Or, at the very least, use some program to capture everything >> you do so that you can refer to it later). >> >> And, finally, I heard vague rumors a while ago that made me think that >> GHC 6.10 might have a pure ANSI-C backend? Is there any truth to this? >> That would make porting much easier if it meant you did not have to do >> steps 1-4. >> >> j. >> ps. I would be happy to try to answer any questions if someone tries a >> port. I would still like to run GHC on my 770, and I hope to own an >> iPhone if they fix a few ommisions (bluetooth keyboard support, and >> similar stuff). >> > > > I recently acquired the ARM-based Nokia N810 (and <3 it), powered by Maemo. > Running a uname -a on it: > > Linux Nokia-N810-42-19 2.6.21-omap1 #2 Fri Nov 16 16:24:58 EET 2007 armv6l > unknown > > I would love a working GHC implementation on it, if for nothing else than > how awesome it would be. Whether that means using a C back-end or native > compilation doesn't matter to me so much. > > I might be one to attempt this, as I know C and ARM-ish asm decently well > and have a powerful desktop to compile on. I have no familiarity > with GHC internals, though. Lastly, I won't have anything like the time to > attempt this seriously until mid-September or so. Oops, forgot to Cc the list. Next year I'll be working on a project for my undergraduate computing course at UNSW that will involve getting GHC to target the Nintendo DS. It'll require cross-compilation, because the DS isn't powerful enough to actually run GHC (4M main ram and a 66MHz processor). It'll also require that I significantly strip down the runtime system, as the current RTS won't fit in 4M and leave any left over for the main application. I'll be documenting the whole process, but I won't be starting until next year... Jeremy

11 15

Network.FastCGI does not emit stderr outputs to lighttpd's error.log?
by Agent Zhang 04 Nov '08

04 Nov '08

Hi, I'm trying Network.FastCGI + lighttpd 1.4.9 to develop a RESTful service platform. I've found that stderr (especially those from Debug.Trace) get lost in the error.log file. But plain CGI mode with Network.CGI works perfectly (all stderr outputs appear in error.log). Besides, my Perl fastcgi script also logs stderr with the same lighttpd. So it does seem that my lighttpd's mod_fastcgi module is OK. Is this a known issue in the Haskell fastcgi library? Is there a workaround or a fix? Thanks in advance :) Cheers, -agentzh

3 4

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

Exceptions
by Adrian Neumann 18 Sep '08

18 Sep '08

Hello, I think it'd be nice if the compiler could warn me if there are any exceptions which I'm not catching, similar to checked exceptions in Java. Does anyone know of a possibility to do that in Haskell? Adrian

6 6