- Haskell-Cafe - Haskell.org

Implementing the State Monad (Was: Can every monad can be implemented with Cont?)
by apfelmus 11 Nov '07

11 Nov '07

jeff p wrote: >>>> Didn't someone already prove all monads can be implemented in terms >>>> of Cont? >>> >>> Cont and StateT, wasn't it? >>> And the schemers have no choice about running in StateT :) >> >> You sure? I want to see the proof :) > > I think this is referring to Andrzej Filinski's paper "Representing > Layered Monads" in which it shown that stacks of monads can be > implemented directly (no layering) by using call/cc and mutable state. Thanks for the reference! I still don't understand Filinski's papers enough to say whether there's more to the embedding than just type Cont m a = forall b . (a -> m b) -> m b reify :: Monad m => Cont m a -> m a reify f = f return reflect :: Monad m => m a -> Cont m a reflect x = (x >>=) Does this already give a performance benefit without further inlining? I doubt it. Anyway, all this leads to a fun and easy way to implement monads, for example the state monad. We have the primitive operations type State s a get :: State s s put :: s -> State s () together with the usual monad laws and the operational semantics evalState :: State s a -> (s -> a) evalState (return x) = \_ -> x evalState (get >>= k) = \s -> evalState (k s ) s -- make the state s available to k evalState (put s >>= k) = \_ -> evalState (k ()) s -- use a new state s Why "operational semantics"? Well, we're just specifying what happens when we "execute" a get or put "instruction" by saying how the execution proceeds with the next instruction k pointed out by >>=. We're not using the "usual" and "elaborate" type like s -> (a,s) to thread the state around, we're using a humble function s -> a to specify that a value a depends on some state s . The operational semantics will do the state plumbing for us. In other words, the we don't have to come with a special implementation like s -> (a,s) that works, we will *mechanically* get one from our intended operational semantics. Now, how to implement? Well, the best way to start is to represent each primitive operation with a new constructor: (GADT notation, needs the -XGADTs flag) data State :: * -> * -> * where Return :: a -> State s a (:>>=) :: State s a -> (a -> State s b) -> State s b Get :: State s s Put :: s -> State s a With this _term representation_, we can implement the operational semantics by evalState ((m :>>= n) :>>= k) = evalState (m :>>= (n :>>= k)) -- monad law associativity evalState (Return x :>>= k) = evalState (k x) -- monad law left unit evalState (Get :>>= k) = \s -> evalState (k s ) s -- semantics of get evalState (Put s :>>= k) = \_ -> evalState (k ()) s -- semantics of put evalState (Return x) = \_ -> x -- semantics of return evalState m = evalState (m :>>= Return) -- monad law right unit Neat, isn't it? Every law and every specification for the primitive instructions has been used exactly once. Simple and painless, but not fully optimized yet. With the first equation, using :>>= left-associatively has similar problems like using ++ left-associatively. Both concat' = foldl (++) [] sequence_' = foldl (>>) (return ()) would show quadratic time behavior. So, just like with difference lists, the idea is to represent the operations in the monad together with the _context_ they are commonly used in. For concatenating lists, the context is (xs ++ _) so that every list xs is represented by \ys -> (xs ++ ys) For our state monad, the context is evalState (m :>>= _) i.e., we make evaluation and sequencing "built-in". More specifically, we also make the evaluation of the next instructions built-in, so that every monadic action m will be represented by \k -> evalState (m :>>= k') where k = evalState . k' In other words, we will represent the type State s a by State' s a = forall b . (a -> (s -> b)) -> (s -> b) But this is just the continuation monad! data Cont m a = Cont (forall b . (a -> m b) -> m b) type State' s a = Cont (s ->) a with m a = s -> a the result type of our semantics evalState . So, we already get >>= and return for free, knowing that they fulfill the monad laws return x = \k -> k x m >>= f = \k -> m (flip f k) Our custom primitive operations get and put are straightforward to implement get = \k -> evalState (Get :>>= k') = \k -> \s -> evalState (k' s ) s = \k -> \s -> k s s put s = \k -> \_ -> k () s These definitions are crystal clear from their operational semantics, given some practice reading them. Last but not least, there is evalState which implements the behavior of the Return instruction evalState m = evalState (m' :>>= Return) = (\k -> evalState (m' :>>= k')) (evalState . Return) = m (\x -> evalState (Return x)) = m (\x -> \_ -> x) That's it for the state monad. For reference, here's the full implementation type State s a = Cont ((->) s) a get = \k s -> k s s put s = \k _ -> k () s evalState m = m const We get >>= and return for free from the predefined Cont (assuming that the "done right"-version with universal quantification would be in the libraries, that is). Of course, this approach isn't limited to the state monad. Here are some parser combinators type Result a = String -> [a] type Parser a = Cont (Result) a run p = p (\x i -> if null i then [x] else []) symbol = \k i -> case i of { c:cs -> k c; [] -> []; } fail = \k i -> [] p +++ q = \k i -> p k i ++ q k i Can you see the operational semantics? (Think of p k as run (p >>= k)). If not, stick to the term implementation and check out Unimo below for a free >>= :) This simple way of implementing monads by their operational semantics is known for quite some time John Hughes. The Design of a Pretty-printing Library. http://citeseer.ist.psu.edu/hughes95design.html Chuan-kai Lin. Programming Monads Operationally with Unimo. http://web.cecs.pdx.edu/~cklin/papers/unimo-143.pdf and is in fact related to the good old continuation passing style of IO and parser combinators. But I think it's powerful and I'd like it to be well-known. Regards, apfelmus PS: Put differently, the question of the original thread "Can every monad can be implemented with Cont?" is whether Unimo can implement strictly more monads than Cont.

1 0

GHC 6.8.1 Documentation
by Cale Gibbard 11 Nov '07

11 Nov '07

Hello all, Recently I noticed that all of my bookmarks to the hierarchical libraries documentation broke, and I'm not entirely happy with the solution of just correcting all the links to point at the new URLs since the URLs all have package version numbers in their names, which means that I'll have to update them all over again next time. Is there any chance we could get stable URLs for the latest version of each module somewhere? (Perhaps via symlinks on the webserver?) I also noticed that the links to the source code seem to be missing from all the 6.8.1 Haddock docs now, which is something that I used quite a lot in the past. It'd be nice to have those back. - Cale

2 1

missed clause???
by Ryan Bloor 11 Nov '07

11 Nov '07

hi I was testing my code when I came across a strange predicament. The input is a list of ints and a Results type which is of type [(int,.......),(Int......)......]. I am comparing each int from the list to the first element in each member of results. But it works for 1-9 but not for 10 onwards.... why? Have I missed a clause anywhere...... it only does the first one after that. --Print the points of eight games poolsPoints :: [Int] -> Results -> Int poolsPoints [] [] = 0 poolsPoints [] _ = 0 poolsPoints _ [] = 0 poolsPoints (x:xs) ((a,b,c,d,e):t) | (x == a && c>d) = 1 + poolsPoints xs t | (x == a && c<d) = 1 + poolsPoints xs t | (x == a && c==0 && d==0) = 2 + poolsPoints xs t | (x == a && c==d && c>0) = 3 + poolsPoints xs t | otherwise = 0 + poolsPoints [x] t Thanks Ryan _________________________________________________________________ The next generation of MSN Hotmail has arrived - Windows Live Hotmail http://www.newhotmail.co.uk

2 1

Announce: xmobar-0.8 released!
by Andrea Rossato 11 Nov '07

11 Nov '07

Hello! I'm very glad to announce the release of Xmobar-0.8. You can grab the source code from Hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/xmobar-0.8 Xmobar is a minimalistic, text based, status bar. It was specifically designed to work with the XMonad Window Manager. Inspired by the Ion3 status bar, it supports similar features, like dynamic color management, output templates, and extensibility through plugins. A precompiled binary is available here: http://code.haskell.org/~arossato/xmobar/xmobar-0.8.bin A recent screen shot can be found here: http://code.haskell.org/~arossato/xmobar/xmobar-0.8.png A screen shot of xmonad and xmobar (my desktop): http://haskell.org/sitewiki/images/a/ae/Arossato-config.png Xmobar depends on X11-1.3.0 and Cabal-1.2 but works both with ghc-6.6.x and ghc-6.8.1. Here you can find a version of the 0.8 source tree that works with Cabal-1.1.x, but will *not* compile with ghc-6.8.1: http://code.haskell.org/~arossato/xmobar/xmobar-0.8-Cabal-1.1-ghc-6.6.tar.gz Some basic documentation is available at the following address: http://code.haskell.org/~arossato/xmobar/ I would like to thank Robert Manea and Spencer Janssen for their help in understanding X and Xlibs. Thanks to Claus Reinke for making me understand existential types (or at least for letting me think I grasp them ;). Xmobar incorporates patches from: Krzysztof Kosciuszkiewicz, Spencer Janssen, Jens Petersen, Dmitry Kurochkin, and Lennart Kolmodin. Hope you will enjoy! Andrea Rossato What's new ========== There are a lot of changes since the last release: a. Configuration: - removed xPos, yPos, width, height, align, and refresh configuration options; - added position and alignSep configuration options: the first is used to set the position (Top, Bottom or Static; the second to set the characters to be used to separate, in the output template, text that must be aligned to the left, centered, or aligned to the right; (please have look at xmobar.config-sample and the README for more details) b. Plugins: - added a plugin to read Unix named pipe (useful to display XMonad logs); - added a plugin to read from standard input; - a new plugin API makes it possible to write plugins that perform asynchronous actions. The new API is totally backward compatible; c. Output template: - it is now possible to align text in the output template. By default text before a '}' will be align to left, the text in between '}' and '{' will be centered, and the text after a '{' will be align to the right, like: "left } centered { right" - strings can have also a background color set: "<fc=red,white>%date%<fc>" will display the output of the "date" command in red with a white background. d. Concurrency: now Xmobar uses Software Transactional Memory and the main window is updated only when needed e. Documentation: I now use Pandoc for the README, this way I have also created an HTML version of. I hope that makes the documentation a bit more accessible: http://code.haskell.org/~arossato/xmobar/ f. The darcs repository has been moved to: http://code.haskell.org/xmobar g. XRandR: since positioning is now done automatically, XRandR should be supported too, even thought support could be buggy due to the fact that I cannot actually test it, since I don't have capable hardware. h. Cabal-1.2 and ghc-6.8.1 support. i. Many other small changes and code cleanup: darcs changes will tell you everything. Configuration Example ===================== This is my ~/.xmobarrc: Config { font = "-bitstream-charter-*-r-normal-*-10-*-*-*-*-56-*-*" , bgColor = "black" , fgColor = "grey" , position = Top , commands = [ Run Weather "LIPB" ["-L","18","-H","27","--normal","green","--high","red","--low","lightblue"] 36000 , Run Network "eth1" ["-L","0","-H","32","--normal","green","--high","red"] 10 , Run Cpu ["-L","3","-H","50","--normal","green","--high","red"] 10 , Run Memory ["-t","Mem: <usedratio>%"] 10 , Run Battery ["-L","50","-H","75","--high","green","--normal","yellow", "--low", "red"] 10 , Run Swap [] 10 , Run Com "uname" ["-s","-r"] "" 36000 , Run Date "%a %b %_d %Y * %H:%M:%S" "mydate" 10 , Run PipeReader "/home/andrea/.xmonad-status" "xlog" ] , sepChar = "%" , alignSep = "}{" , template = "%xlog% }{ %cpu% | %memory% * %swap% | %eth1% | %LIPB% | <fc=orange>%mydate%</fc> | %battery%" }

1 0

Sinus in Haskell
by Hans van Thiel 11 Nov '07

11 Nov '07

Hello All, Can anybody explain the results for 1.0, 2.0 and 3.0 times pi below? GHCi yields the same results. I did search the Haskell report and my text books, but to no avail. Thanks in advance, Hans van Thiel Hugs> sin (0.0 * pi) 0.0 Hugs> sin (0.5 * pi) 1.0 Hugs> sin (1.0 * pi) 1.22460635382238e-16 Hugs> sin (1.5 * pi) -1.0 Hugs> sin (2.0 * pi) -2.44921270764475e-16 Hugs> sin (2.5 * pi) 1.0 Hugs> sin (3.0 * pi) 3.67381906146713e-16 Hugs>

12 15

WideFinder
by manu 11 Nov '07

11 Nov '07

Haskell is conspicuously absent from the languages used to tackle Tim Bray's Wide Finder problem (http://www.tbray.org/ongoing/When/200x/ 2007/10/30/WF-Results?updated). So far we have Ocaml, Erlang, Python, Ruby, etc... Bryan quickly wrote a program on his blog (http://www.serpentine.com/ blog/2007/09/25/what-the-heck-is-a-wide-finder-anyway/) that would place Haskell right in the second position. JoCaml is the fastest so far (http://eigenclass.org/hiki.rb?fast- widefinder)... Can Haskell do better ? Care to take a shot ? Manu

6 8

Re: Flymake Haskell
by Daisuke IKEGAMI 11 Nov '07

11 Nov '07

<cbf55b100711081320k10988f5fke345b9d01bcf64e9(a)mail.gmail.com> <20071109.090048.74745692.ikegami(a)madscientist.jp> <jwvwssq4r4f.fsf-monnier%2Bemacs(a)gnu.org> Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi, Stefan wrote: > I looked at http://www.emacswiki.org/cgi-bin/emacs/FlymakeHaskell > but it's not clear what's going on. I've been written the instruction of Flymake Haskell for both Emacs21 and Emacs22 at; http://www.emacswiki.org/cgi-bin/emacs/FlymakeHaskell Note that it will not work in the future, since the flymake-mode has been developed so actively. I'm not a native English speaker. Please fix typo or inappropriate expressions. I wish it helps to write Haskell code on Emacs. Best wishes, ike

1 0

O'Reilly "Real World Haskell" book
by Galchin Vasili 11 Nov '07

11 Nov '07

Hello, What is the proposed table of contents for "Real World Haskell"? Regards, Vasili

2 1

Whither memo and hash-consing?
by Chung-chieh Shan 10 Nov '07

10 Nov '07

Hello, What is the current status of the Memo module, for memoizing functions? It seems to have disappeared from the standard Hugs/GHC distributions; are we supposed to just find the old code on Google which uses System.Mem.Weak? A related question is whether anyone has built a library for hash-consing. Ideally it's just a function "hashCons" with a type like "(Ord a) => a -> a". Thank you. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig The old name for the Giraffe was Cameleopard, literally a Camel-Leopard.

1 0

Trouble using unboxed arrays
by Justin Bailey 10 Nov '07

10 Nov '07

I would like to create a data structure that uses an unboxed array as one of its components. I would like the data structure to be parameterized over the type of the elements of the array. Further, I'd like to build the array using runSTUArray. I can't make the code work though. My naive approach: data Ring a = Ring (UArray Int a) and the code to make the array: makeArray :: [a] -> Ring a makeArray ls = Ring (ST.runSTUArray (ST.newListArray (0, length ls - 1) ls)) But that doesn't work. I get from GHC (6.8.1): Could not deduce (MArray (STUArray s) a (ST s)) from the context () arising from a use of `newListArray' I am pretty sure I need to constrain 'a' to primitive types only, but how? Can I do it in the data definition? Thanks in advance for any help! Justin

3 2