August 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

Reader monad, implicit parameters, or something else altogether?
by Bjorn Buckwalter 16 Dec '08

16 Dec '08

All, I have a growing amount of astrodynamics code that relies on various physical "constants". The problem with these so called "constants" are that they either aren't really constants or aren't well known. An example is the leap second table (see Data.Time.Clock.TAI). I'd like to be able to fetch current values of these constants at runtime and make them accessible to my astrodynamics functions by some means. To clarify, once initialized the constants will be considered constant for the remainder of the program. I'd store the constants in a data structure along the lines of: > data AstroData a = AstroData > { mu_Earth :: GravitationalParameter a > , leapSeconds :: LeapSecondTable > } I would like to know if there is any consensus on what is the best way to make such a data structure accessible in pure functions. Passing it explicitly would be a mess. It seems that two options are to use either a Reader monad or implicit parameters. Using a Reader monad is straight forward enough though it requires writing/converting code in/to monadic style and adds some clutter to the formulae. It seems implicit parameters could be cleaner but I've seen them referred to as everything from evil to "just what you need" and rendering the Reader monad obsolete... What do you people recommend? Thanks, Bjorn Buckwalter

5 7

two problems with Data.Binary and Data.ByteString
by Tim Newsham 05 Nov '08

05 Nov '08

I have a program that read in and populated a large data structure and then saved it out with Data.Binary and Data.ByteString.Lazy.Char8: saveState db = B.writeFile stateFile =<< encode <$> atomically (readTVar db) when I go to read this in later I get a stack overflow: loadState db = do d <- decode <$> B.readFile stateFile atomically $ writeTVar db d Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize' to increase it. or from ghci: d <- liftM decode (Data.ByteString.Lazy.Char8.readFile "savedState.bin") :: IO InstrsDb fromList *** Exception: stack overflow The data type I'm storing is a Map (of maps): type DailyDb = M.Map Date Daily type InstrsDb = M.Map String DailyDb What's going on here? Why is the system capable of building and saving the data but not in reading and umarhsalling it? What is the proper way to track down where the exception is happening? Any debugging tips? I also noticed another issue while testing. If my program loads the data at startup by calling loadState then all later calls to saveState give an error: Log: savedState.bin: openFile: resource busy (file is locked) this does not occur if the program wasnt loaded. My best guess here is that B.readFile isnt completing and closing the file for some reason. Is there a good way to force this? Tim Newsham http://www.thenewsh.com/~newsham/

10 49

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