May 2008 - Haskell-Cafe

ANNOUNCE: Sessions 2008.5.2
by Matthew Sackman 06 May '08

06 May '08

Howdy, I'm pleased to announce the general availability of Session Types for Haskell, version 2008.5.2. It is available from my website[0], Hackage[1][2] and I've just updated the online tutorial[3] to take into account the recent changes and new features. [0] http://wellquite.org/non-blog/sessions-2008.5.2.tar.gz [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/sessions-2008.5.2 [2] http://hackage.haskell.org/ [3] http://wellquite.org/sessions/tutorial_1.html Session types are a means of describing communication between multiple threads, and statically verifying that the communication being performed is safe and conforms to the specification. The library supports multiple, concurrent channels being open and actions upon those channels being interleaved; forking new threads; the communication of process IDs, allowing threads to establish new channels between each other; higher-order channels, allowing an established channel to be sent over a channel to another process; and many other features common to session type systems. The significant new changes in this version are: a) an entirely new means to specify session types. This removes the old absolute indexing, is composeable and far more flexible and powerful than the old system. b) support for higher-order channels and session types allowing channels to be sent and received. This permits additional communication patterns such as two threads which are otherwise unaware of each other being able to communicate with one another by sending and receiving a channel via a common third party - delegation. Tests[4] and an example application[5] are available which should, in combination with the tutorial[6], explain how session types can be used. As ever, any feedback is very gratefully received. [4] http://wellquite.org/non-blog/sessions-browseable/Control/Concurrent/Sessio… [5] http://wellquite.org/non-blog/sessions-browseable/Control/Concurrent/Sessio… [6] http://wellquite.org/sessions/tutorial_1.html Matthew

1 1

Non-Overlapping Patterns
by PR Stanley 06 May '08

06 May '08

Hi isZero :: Int -> Bool isZero 0 = True isZero n | n /= 0 = False The order in which the above equations appear makes no difference to the application of isZero. Does the Haskell interpreter rewrite patterns into one single definition using some sort of switch or if construct? Why does an equation without a guard have to be placed after the more specific cases?To put it another way, why doesn't the interpreter identify the more specific cases and put them before the general ones. Cheers Paul

5 5

Help me speed up my program... or back to the issue of memoization
by Kirill Kuvaldin 05 May '08

05 May '08

Hello, I wrote a program in haskell that works with lattice finite automata (the generalization of notion of finite state automata). Let me post the source code as it is not that long... The problem is that my algorithm that computes the run (see function fun) of an automaton on the given word is not very optimal and takes a loooong time as the input word gets larger... (e.g. try this one "run m3 "11101101110001010101" ") Due to the nature of every haskell function being a referentially transparent, I think I could have speeded up its performance using memoization. I've read the page on haskell wiki (http://www.haskell.org/haskellwiki/Memoization) but it didn't help me because it looks I have to modify the actual function source code to make use of memoized values. What I'm looking for is a kind of a general solution (say, silver bullet :) ) so that I will be able to use my function like > new_run = memoize run and the results of the "new_run" get automatically memoized. Probably it makes sense to memoize deltaext func as well. Is that possible to do that in Haskell?? Thanks a lot! Kirill ======= SOURCE CODE ===== -- data type for lattice data Lattice l = Lattice [l] -- set of lattice elements (l -> l -> l) -- supremum operation (l -> l -> l) -- infimum operation -- returns the lowest lattice element lattice0 (Lattice l s i) = l !! 0 -- returns the greatest lattice element lattice1 (Lattice l s i) = l !! ((length l)-1) -- supremum of 2 lattice elements sup (Lattice l s i) x y = s x y -- infimum of 2 lattice elements inf (Lattice l s i) x y = i x y supremum (Lattice l sup inf) [] = lattice0 (Lattice l sup inf) supremum (Lattice l sup inf) (x:xs) = sup x (supremum (Lattice l sup inf) xs) infimum (Lattice l sup inf) [] = lattice1 (Lattice l sup inf) infimum (Lattice l sup inf) (x:xs) = inf x (infimum (Lattice l sup inf) xs) inf3 (Lattice l s i) x y z = infimum (Lattice l s i) [x,y,z] --- data type for Lattice Automata (LA) data LA l state sym = LA (Lattice l) -- lattice [state] -- set of states [sym] -- alphabet (state -> sym -> state -> l) -- fuzzy transition function (state -> l) -- fuzzy initial state (state -> l) -- fuzzy final state --- extended transition function deltaext :: (Eq state) => (LA l state sym) -> state -> [sym] -> state -> l deltaext (LA l states chars delta sigma0 sigma1) x [] y = if x == y then (lattice1 l) else (lattice0 l) deltaext la@(LA l states chars delta sigma0 sigma1) x (a:w) y = supremum l [ inf l (delta x a z) (deltaext la z w y) | z <- states] -- runs the Lattice Automaton on the given word run la@(LA l states chars delta sigma0 sigma1) w = supremum l [ inf3 l (sigma0 x) (deltaext la x w y) (sigma1 y) | x <- states, y <- states] --- --- examples --- l3 = Lattice [0.0, 0.5, 1.0] max min where max x y = if x > y then x else y min x y = if x < y then x else y m3 = LA l3 ['a', 'b'] ['0', '1'] delta sigma0 sigma1 where delta 'a' '0' 'a' = 1 delta 'a' '0' 'b' = 0.5 delta 'b' '0' 'a' = 0.5 delta 'b' '0' 'b' = 1 delta 'a' '1' 'a' = 0 delta 'a' '1' 'b' = 1 delta 'b' '1' 'a' = 1 delta 'b' '1' 'b' = 1 sigma0 'a' = 1 sigma0 'b' = 0.5 sigma1 'a' = 0.5 sigma1 'b' = 1

3 2

Parsec on TeX
by Ross Boylan 05 May '08

05 May '08

I am new to Haskell and Parsec, and am trying to understand both. I tried to follow the example of how to use Parsec to parse TeX begin/end groups, but can't get it to run. I'm using HUGS -98 on Debian. When I copied the code I got errors about unknown terms (reserved and braces). I've tried to get them from the lexer, but now get this error :load grammar.hsl ERROR "grammar.hsl":21 - Type error in explicitly typed binding *** Term : envEnd *** Type : String -> GenParser Char a [Char] *** Does not match : String -> Parser () Can anyone help me understand what the problem is? Here's the code the caused the above error; I believe the part after --TeX example is verbatim from the Parsec documentation. I picked haskell as the language for to lexer "arbitrarily." import Text.ParserCombinators.Parsec import qualified Text.ParserCombinators.Parsec.Token as P import Text.ParserCombinators.Parsec.Language(haskell) reserved = P.reserved haskell braces = P.braces haskell -- TeX example environment = do{ name <- envBegin ; environment ; envEnd name } <|> return () envBegin :: Parser String envBegin = do{ reserved "\\begin" ; braces (many1 letter) } envEnd :: String -> Parser () envEnd name = do{ reserved "\\end" ; braces (string name) }

8 16

Data structure to manage collection of sets with efficient lookup, intersection?
by Patrick Surry 05 May '08

05 May '08

New to Haskell, with a mental block about how to represent this situation efficiently: I have an unknown function f which is defined on subsets of some universal set (say integers 1...N). I know the values of f for some subsets, and using those can infer values on other subsets. So what I need is a way to manage a collection of subsets s_i (and the associated values f(s_i)) so that I can efficiently (a) check whether a subset s is already 'known' in my collection, and (b) find all subsets t in the collection that intersect s. In a "traditional" language, I'd likely create a dictionary with keys s_i containing the f(s_i) as values, along with a separate dictionary keyed on the elements of the universal set (1...N) in which each entry is a list of all s_i containing the given element of the universal set. Together they let me check, given a subset s, whether I know f(s), and also get the list of all known subsets intersecting s (by the union of the lists of sets containing each element of s). I can't quite wrap my head around how to do this efficiently in Haskell, maybe because of the way the above is duplicating information about the subsets across two different data structures? Any thoughts? Thanks, Patrick ________________________________________________________________________ DISCLAIMER: This e-mail is intended only for the addressee named above. As this e-mail may contain confidential or privileged information, if you are not the named addressee, you are not authorised to retain, read, copy or disseminate this message or any part of it. If you received this email in error, please notify the sender and delete the message from your computer.

3 2

Cabalizing darcs
by Gwern Branwen 05 May '08

05 May '08

So recently I spent a bit of time working on a cabalization of Darcs. It works well for me, and is reasonably easy to apply (attached are three files; do a 'darcs get --lazy http://darcs.net' with Darcs-2 to get the latest, and copy the files into it, the usual autoconf, and it should then work as normal; if this doesn't work for you, I'd appreciate knowing). My question for y'all is: would you find an unofficial version of Darcs - one with the cabalization added and uploaded to Hackage - useful? Or would it just be frustrating and redundant and Not Good? (If yes, any suggestions for a package name? 'darcs' is out, but 'darcs-cb' and 'darcs-cabalized' strike me as horribly clunky or obscure.) -- gwern Threat WANK football Talent anarchy RIT interception Hutsul forschung ISS

4 5

unapplying function definitions?
by PR Stanley 05 May '08

05 May '08

Hi What on earth is unapplying function definitions? The following is taken from chapter 13 of the Hutton book: "...when reasoning about programs, function definitions can be both applied from left to right and unapplied from right to left." Cheers Paul

4 4

Question related to Multi Param Type Classes
by Sai Hemanth K 05 May '08

05 May '08

Hi, I declared a multi param type class as below: *class MyString m c where zIndex :: m -> Int -> c zLength :: m -> Int zPack :: [c] -> m zEquals :: c ->c -> Bool zWrap :: [c] -> (m,AnExistingDataType)* In the end I did not needed it for my program, but for those few minutes I played with the idea, I came across a zillion questions. Can some body help me here please? When I defined a function like below, \begin{code} compareStr::(MyString m c) => (m,Int) ->(m,Int)->Int->Int compareStr (s1,pos1) (s2,pos2) soFar | (pos1 < zLength s1) && (pos2 < zLength s2) = let c1 = zIndex s1 pos1 c2 = zIndex s2 pos2 in if(zEquals c1 c2) then compareStr (s1,(pos1 + 1)) (s2, (pos2 + 1)) (soFar + 1) else soFar | otherwise = soFar \end{code} when I loaded it on ghci ( invoked with -XMultiParamTypeClasses ), I got an essay in greek (or is it latin?), which started something like below: Could not deduce (MyString m c) from the context (MyString m c4) arising from a use of `zLength' at GenericZAlgo.lhs:42:21-31 Possible fix: add (MyString m c) to the context of the type signature for `compareStr' In the second argument of `(<)', namely `zLength s1' In the first argument of `(&&)', namely `(pos1 < zLength s1)' In a pattern guard for the definition of `compareStr': (pos1 < zLength s1) && (pos2 < zLength s2) And if I let the type inference run the show, the type it shows is : compareStr :: (MyString t c2, MyString m c2, Num a, MyString t1 c2, MyString t c, MyString t1 c1) => (t, Int) -> (t1, Int) -> a -> a And puzzlingly, if I try the same thing myself and reload it on the ghci,I still get similar error. I can go on about other 'puzzles'. Can some one please tell me whats going on here? Apologies, if it is something that's been documented left to right, top to bottom, but I could not get anywhere readily. Any pointers to the right documentation will be much appreciated. On the surface it looks like something that n00bs like yours truly better stay away. But I have a feeling that this one may throw some more light on type inference. Many thanks

5 4

Grokking monads by not overlooking concatMap
by Achim Schneider 05 May '08

05 May '08

guard True = return () guard False = [] -- the textbook example f = do x <- [1..4] y <- [2..8] guard (x*y==8) return (x,y) -- the translation. f' = [1..4] >>= (\x -> [2..8] >>= (\y -> (if (x*y == 8) then return () else []) >> return (x,y))) -- another one. note that we can move the final -- return out of the parens. It would even work without it, but we'd -- get a list containing many empty lists: concat fixes that. f'' = [1..4] >>= (\x -> [2..8] >>= (\y -> if (x*y == 8) then [(x,y)] else [] >>= return )) -- bind desugared. Actually, it seems to be impossible to -- write this in monadic notation and I'm getting quite confused. f''' = concatMap (\x -> concatMap (\y -> if x*y == 8 then [(x,y)] else []) [2..8]) [1..4] -- That's the one I've been looking for. Remember that -- return e = [e] f'''' = concatMap (\x -> concatMap (\y -> concatMap (\_ -> [(x,y)]) (if x*y == 8 then [()] else [])) [2..8]) [1..4] Morale: Premature term elimination is the root of all misunderstanding. Haskell wins the wickedness of design contest by using [()] and [] as truth values. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.

2 5

A common pattern
by Andrew Coppin 05 May '08

05 May '08

I've found myself writing code like this several times now. Is there a better way? read_args h = do line <- hGetLine h case line of "." -> return [] ('#':y) -> do ys <- read_args h return (y:ys)

4 5