November 2007 - Haskell-Cafe

can someone explain monad transformers to me, or how do you combine maybe and IO?
by Anatoly Yakovenko 12 Nov '07

12 Nov '07

I wanted something that would work like liftM but with IO as well, so something like this: > liftM ((+) 1) $ Just 1 Just 2 but with the function lifted being of type (a -> IO b). so I came up with maybeIO::(a -> IO b) -> (Maybe a -> IO (Maybe b)) maybeIO ff = (\ aa -> case aa of Nothing -> return $ Nothing Just vv -> do rv <- ff vv return $ Just rv) incIO:: Int -> IO Int incIO ii = return $ ii + 1 > maybeIO incIO $ Just 1 Just 2 works just like I want it to. But isn't this something that a monad transformer should be able to do?

3 2

How to do this in Haskell
by Chris Smith 12 Nov '07

12 Nov '07

If you wanted to write a Haskell application that included a WYSIWYG HTML editor, how would you do it? More details: - I'll probably be using Gtk2Hs for the app, though that could change with a (very) good reason. - The top priorities for the editor are that it resemble common word processors in editing functions, and that the display looks as near as possible to what can be expected from some major browser such as FireFox or IE. If it's not possible to do extremely well in both of these criteria, then I may as well abandon the project now. - I'd like for the result to be cross-platform, but Windows-only would be just as good from my boss's perspective. So, with all that in mind, I'm looking for options. What looks most realistic that I've found to date is building an XP-COM implementation for Haskell via the FFI and either a code generation tool or Template Haskell, and then using that to try to embed the Mozilla editor component. Given my serious lack of knowledge in XP-COM or the Mozilla project or GTK, that looks sort of scary. Any other ideas? -- Chris Smith

5 6

Data.Set.member vs Data.List.elem
by Neil Mitchell 12 Nov '07

12 Nov '07

Hi, Is there a good reason that Data.Set uses the name "member" while Data.List (or the Prelude) uses the name "elem", for what to me seem identical concepts. I realise that in Set's the traditional test is for "membership", but it seems awfully arbitrary that one jumped one way and one jumped the other. I've just written an entire module's worth of Haskell with Set.elem, as that "felt" right, now I'm going back and fixing it. Thanks Neil

2 1

Re: [Haskell-cafe] Interesting effect of upgrading GHC
by Andrew Coppin 12 Nov '07

12 Nov '07

Gwern Branwen wrote: > FWIW, I was actually discussing compilation with -O2 on 6.8 with Sjannssen and he told me that even with -O2 turned on, GHC now defaults to -fasm instead of -fvia-c. Ah. Yeah, that could well make a big difference... (Especially on a machine with insufficient RAM.) > Also, the release notes are talking about the runtime speed of binaries, not compilation. > But since GHC is compiled with GHC, you would expect a (small) speedup of GHC. (And indeed that is what the release notes specifically suggest.) Either way, I (and probably a number of other people) will go test what speed difference it actually makes to compiled code. ;-) (I've been wondering for a while now whether there's much to choose between -fasm and -fvia-c.)

1 0

Re: [Haskell] GHC6.8.1 can not compile the simple example
by Neil Mitchell 12 Nov '07

12 Nov '07

Hi David, In future, please post emails to haskell-cafe@, the haskell@ list is for annoucements. The correct command line is: ghc --make c.hs Thanks Neil On Nov 12, 2007 1:11 PM, david yu <davidyuhxl(a)gmail.com> wrote: > Link error is: > [davidyu@linuxpower test]$ ghc c.hs > c.o: In function `rM7_info': > (.text+0xaa): undefined reference to > `containerszm0zi1zi0zi0_DataziMap_lookup_closure' > c.o: In function `rMd_info': > (.text+0x1fa): undefined reference to > `containerszm0zi1zi0zi0_DataziMap_fromList_closure' > c.o: In function `sVJ_info': > (.text+0xa3b): undefined reference to > `__stginit_containerszm0zi1zi0zi0_DataziMap_' > c.o: In function `rM7_srt': > (.data+0x18): undefined reference to > `containerszm0zi1zi0zi0_DataziMap_lookup_closure' > c.o: In function `rMd_srt': > (.data+0x60): undefined reference to > `containerszm0zi1zi0zi0_DataziMap_fromList_closure' > collect2: ld returned 1 exit status > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell > >

1 0

Upgrading X11
by Jim Burton 12 Nov '07

12 Nov '07

I have X11 1.2.2 installed and wanted to upgrade to 1.3 (to satisfy the dependencies of another package), but "Setup configure" tells me I don't have the headers installed. I do, and when I configure 1.2.2 they're detected. Is this due to the newer version of Cabal? I have ghc 6.6, Cabal 1.1.6. Thanks, -- View this message in context: http://www.nabble.com/Upgrading-X11-tf4785984.html#a13691779 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 3

Memory Leak Help
by J. Garrett Morris 12 Nov '07

12 Nov '07

Hello, I have code which seems to contain a memory leak, but I'm not sure where it is or what's causing it. Any help would be greatly appreciated: The code is: data Ratings = Ratings { movieCount :: Int , movieLookup :: IOUArray Int Word32 , movieRatings :: IOUArray Word32 Word32 } readRatingsFromText :: Int -> Int -> C.ByteString -> IO Ratings readRatingsFromText movieCount ratingCount text = do movieLookup <- newArray_ (0, movieCount - 1) movieRatings <- newArray_ (0, fromIntegral ratingCount - 1) iter movieLookup movieRatings 0 (C.lines text) return (Ratings movieCount movieLookup movieRatings) where iter :: IOUArray Int Word32 -> IOUArray Word32 Word32 -> Word32 -> [C.ByteString] -> IO () iter !movieLookup !movieRatings !i [] = return () iter !movieLookup !movieRatings !i (s:ss) | c == ':' = do writeArray movieLookup movie i iter movieLookup movieRatings i ss | otherwise = do writeArray movieRatings i rating -- *** iter movieLookup movieRatings (i + 1) ss where Just (x, rest) = C.readInt s c = C.head rest Just (y, _) = C.readInt (C.tail rest) movie = x - 1 rating = fromIntegral x `shiftL` 3 .|. fromIntegral y :: Word32 main = do args <- getArgs ratings <- readRatingsFromText (read $ args !! 0) (read $ args !! 1) =<< B.readFile (args !! 2) return () This attempts to read a file that looks like: 1: 401,2 503,1 ... 2: 506,5 230,4 possibly with additional junk at the end of each line into an array. When I run this, memory usage grows without bound. If I comment out the line with -- ***, the memory profile is flat. Without storing the ratings, it's not fantastically useful; however, it does demonstrate that it should be possible to iterate through the file with a flat memory profile (which is my goal). I'm compiling with ghc --make -O2 Any help would be greatly appreciated. Thanks! /g -- The man who'd introduced them didn't much like either of them, though he acted as if he did, anxious as he was to preserve good relations at all times. One never knew, after all, now did one now did one now did one.

2 1

Implementing the State Monad
by oleg＠pobox.com 11 Nov '07

11 Nov '07

apfelmus showed the implementation of the state monad as free term algebra, using GADT. Here's an implementation that does not use GADT http://okmij.org/ftp/Haskell/types.html#state-algebra All the smarts are in the observation function. This style is _very_ well explained by Ralf Hinze in his Functional Pearl `Deriving Backtracking Monad Transformers' (ICFP00) http://citeseer.ist.psu.edu/hinze00deriving.html He also showed how to optimize this term algebra (aka, `initial') implementation using continuations (sec 3.3). Where this style begins to break down is with complex monads, such as backtracking *with cut* or some other control. Note that Hinze was not able to implement his version of backtracking with cut using _free_ term algebra. The situation can be improved however if we use a special operation to reflect the search (msplit of MonadMinus). We obtain an efficient implementation then and no longer have to match on the contexts.

1 0

Haskell Weekly News: November 11, 2007
by Don Stewart 11 Nov '07

11 Nov '07

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20071111 Issue 67 - November 11, 2007 --------------------------------------------------------------------------- Welcome to issue 67 of HWN, a newsletter covering developments in the [1]Haskell community. This week sees the release of GHC 6.8.1, to rave reviews. There have been many reports of large performance improvements for Haskell programs, from small to large production systems. Congratulations to the GHC team for such a great release! 1. http://haskell.org/ Announcements GHC 6.8.1. Ian Lynagh [2]announced the release of GHC 6.8.1, a new major release of GHC. There have been a number of significant changes since the last major release, including: Haskell Program Coverage support, the GHCi debugger, pointer tagging in the runtime (with up to 10-15% speedups), constructor specialisation, improved optimisations and much more! The [3]full release notes are available. 2. http://article.gmane.org/gmane.comp.lang.haskell.general/15733 3. http://haskell.org/ghc/docs/6.8.1/html/users_guide/release-6-8-1.html Gtk2Hs 0.9.12.1. Duncan Coutts [4]announced version 0.9.12.1 of gtk2hs is [5]now available. gtk2hs is the standard graphics library for Haskell. 4. http://article.gmane.org/gmane.comp.lang.haskell.general/15738 5. http://haskell.org/gtk2hs/download/ Lazy SmallCheck 0.1. Matthew Naylor [6]announced Lazy SmallCheck 0.1, a library for exhaustive, demand-driven testing of Haskell programs. 6. http://article.gmane.org/gmane.comp.lang.haskell.general/15702 HDBC 1.1.3. John Goerzen [7]announced new releases of HDBC, the Haskell database connectivity kit, and its associated backends (for sqlite3, postgresql, odbc). 7. http://article.gmane.org/gmane.comp.lang.haskell.general/15729 xmobar. Andrea Rossato [8]announced the release of Xmobar-0.8, a minimalistic, text based, status bar. It was specifically designed to work with the XMonad Window Manager. 8. http://article.gmane.org/gmane.comp.lang.haskell.cafe/31465 Flymake Haskell. Daisuke Ikegami [9]announced flymake haskell, emacs bindings for interactive Haskell editing. 9. http://article.gmane.org/gmane.comp.lang.haskell.cafe/31453 network bytestring. Johan Tibbel [10]announced, strict ByteString versions of the recv/send family of functions for efficient network IO. 10. http://article.gmane.org/gmane.comp.lang.haskell.general/15645 ByteString search. Bryan O'Sullivan [11]announced a cabalised version of the fast Boyer-Moore and Knuth-Morris-Pratt string search code for ByteStrings 11. http://article.gmane.org/gmane.comp.lang.haskell.cafe/31229 Generating free theorems. Janis Voigtlaender [12]announced an improved version of the online and offline free theorems generator for Haskell 12. http://article.gmane.org/gmane.comp.lang.haskell.general/15693 hslogger4j 0.1.1. Bjorn Buckwalter [13]announced Hslogger4j, which provides handlers for hslogger (John Goerzen's Haskell logging framework) that are compatible with log4j's XMLLayout. 13. http://article.gmane.org/gmane.comp.lang.haskell.general/15707 Infinity 0.3. Austin Seipp [14]announced `infinity', an IRC bot in Haskell 14. http://article.gmane.org/gmane.comp.lang.haskell.cafe/31228 hswm. Remi Turk [15]announced the first and last release of hswm, a Haskell window manager. 15. http://article.gmane.org/gmane.comp.lang.haskell.cafe/30804 Hackage This week's new libraries in [16]the Hackage library database. 16. http://hackage.haskell.org/ * xmobar-0.8. Uploaded by Andrea Rossato. [17]xmobar, a minimalistic text based status bar * hsSqlite3-0.0.4. Uploaded by Evgeny Jukov. [18]hsSqlite3, bindings for Sqlite3 * cabal-rpm-0.3.2. Uploaded by Bryan OSullivan. [19]cabal-rpm turns Haskell Cabal source packages into source and binary RPM packages. * selenium-0.2.2. Uploaded by Aaron Tomb. [20]selenium, Haskell bindings to communicate with a Selenium Remote Control server. This package makes it possible to use Haskell to write test scripts that exercise web applications through a web browser. * HPDF-1.3. Uploaded by alpheccar. [21]HPDF. A PDF library with support for several pages, page transitions, outlines, annotations, compression, colors, shapes, patterns, jpegs, fonts, typesetting ... 17. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/xmobar-0.8 18. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hsSqlite3-0.0.4 19. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/cabal-rpm-0.3.2 20. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/selenium-0.2.2 21. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HPDF-1.3 * FileManip-0.3.1. Uploaded by Bryan OSullivan. [22]FileManip, a Haskell library for working with files and directories. Includes code for pattern matching, finding files, modifying file contents, and more. * stringsearch-0.2. Uploaded by Bryan OSullivan. [23]stringsearch, fast search of ByteStrings. * nano-md5-0.1. Uploaded by Don Stewart. [24]nano-md5, ByteString bindings to OpenSSL. * denominate-0.4.1. Uploaded by Calvin Smith. [25]denominate provides a main program for performing bulk file and directory renaming, using a built-in filename converter or user-defined converters. * ContArrow 0.0.2. Uploaded by Evgeny Jukov. [26]ContArrow, Control.Arrow.Transformer.Cont 22. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/FileManip-0.3.1 23. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stringsearch-0.2 24. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/nano-md5-0.1 25. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/denominate-0.4.1 26. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ * state 0.0.2. Uploaded by Evgeny Jukov. [27]state. State. * infinity 0.3. Uploaded by Austin Seipp. [28]infinity, a tiny, pluggable irc bot. * unix-compat 0.1.2.1. Uploaded by Duncan Coutts. [29]unix-compat, portable implementations of parts of the unix package. * Ranged-sets 0.1.1. Uploaded by Paul Johnson. [30]Ranged-sets. A ranged set is an ordered list of ranges. * IFS 0.1.1. Uploaded by alpheccar. [31]IFS, a library to describe IFS and generate PPM pictures from the descriptions 27. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 28. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 29. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 30. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 31. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ * bktrees 0.1.3. Uploaded by Josef Svenningsson. [32]bktrees. Burhard-Keller trees provide an implementation of sets which apart from the ordinary operations also has an approximate member search, allowing you to search for elements that are of a certain distance from the element you are searching for. * pqc 0.2. Uploaded by Don Stewart. [33]pqc, a parallel batch driver for QuickCheck * strict 0.2. Uploaded by Don Stewart. [34]strict, strict data types. * HsSVN 0.2. Uploaded by PHO. [35]HsSVN, (Part of) Subversion binding for Haskell * HsHyperEstraier 0.2. Uploaded by PHO. [36]HsHyperEstraier, a HyperEstraier binding for Haskell. HyperEstraier is an embeddable full text search engine which is supposed to be independent to any particular natural languages. 32. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 33. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 34. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 35. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 36. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ * HsOpenSSL 0.3.1. Uploaded by PHO. [37]HsOpenSSL, a (part of) OpenSSL binding for Haskell. It can generate RSA and DSA keys, read and write PEM files, generate message digests, sign and verify messages, encrypt and decrypt messages. * Finance-Quote-Yahoo 0.4. Uploaded by Brad Clawsie. [38]Finance-Quote-Yahoo, obtain quote data from finance.yahoo.com * LRU 0.1.1. Uploaded by Adam Langley. [39]LRU, an LRU data structure * base 3.0. Uploaded by Ross Paterson. [40]base, the Prelude and its support libraries, and a large collection of useful libraries ranging from data structures to parsing combinators and debugging utilities. * regex-posix 0.72.0.2. Uploaded by Duncan Coutts. [41]regex-posix, posix regex support. 37. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 38. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Finance-Quote-Ya… 39. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/LRU-0.1.1 40. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/base-3.0.0.0 41. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/regex-posix-0.72… * xhtml 3000.0.2.1. Uploaded by Bjorn Bringert. [42]xhtml, combinators for producing XHTML 1.0, including the Strict, Transitional and Frameset variants. * Win32 2.1.0.0. Uploaded by Esa Ilari Vuokko. [43]Win32, a binding to part of the Win32 library * unix 2.2.0.0. Uploaded by Ross Paterson. [44]unix, POSIX functionality * time 1.1.2.0. Uploaded by Ross Paterson. [45]time, time handling. * template-haskell 2.2.0.0. Uploaded by Ross Paterson. [46]template-haskell, support for manipulating Haskell syntax trees 42. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/xhtml-3000.0.2.1 43. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Win32-2.1.0.0 44. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/unix-2.2.0.0 45. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/time-1.1.2.0 46. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/template-haskell… * stm 2.1.1.0. Uploaded by Ross Paterson. [47]stm, software transational memory * regex-compat 0.71.0.1. Uploaded by Ross Paterson. [48]regex-compat, backwards compatible regex support * regex-base 0.72.0.1. Uploaded by Ross Paterson. [49]regex-base, regex support. * readline 1.0.1.0. Uploaded by Ross Paterson. [50]readline, an interface to the GNU readline library * random 1.0.0.0. Uploaded by Ross Paterson. [51]random, random number generation 47. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stm-2.1.1.0 48. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/regex-compat-0.7… 49. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/regex-base-0.72.… 50. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/readline-1.0.1.0 51. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/random-1.0.0.0 * QuickCheck 1.1.0.0. Uploaded by Ross Paterson. [52]QuickCheck, automatic testing of Haskell programs * process 1.0.0.0. Uploaded by Ross Paterson. [53]process, jobs and processes * pretty 1.0.0.0. Uploaded by Ross Paterson. [54]pretty, pretty printing library. * parsec 2.1.0.0. Uploaded by Ross Paterson. [55]parsec, monadic parser combinators. * parallel 1.0.0.0. Uploaded by Ross Paterson. [56]parallel, support for parallel programming 52. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/QuickCheck-1.1.0… 53. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/process-1.0.0.0 54. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/pretty-1.0.0.0 55. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/parsec-2.1.0.0 56. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/parallel-1.0.0.0 * packedstring 0.1.0.0. Uploaded by Ross Paterson. [57]packedstring, packed strings * OpenGL 2.2.1.1. Uploaded by Ross Paterson. [58]OpenGL, binding for the OpenGL graphics system * OpenAL 1.3.1.1. Uploaded by Ross Paterson. [59]OpenAL, binding to the OpenAL cross-platform 3D audio API. * old-time 1.0.0.0. Uploaded by Ross Paterson. [60]old-time, time library. * alex 2.2. Uploaded by Simon Marlow. [61]alex is a tool for generating lexical analysers in Haskell 57. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/packedstring-0.1… 58. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/OpenGL-2.2.1.1 59. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/OpenAL-1.3.1.1 60. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/old-time-1.0.0.0 61. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/alex-2.2 * Cabal 1.2.2.0. Uploaded by Duncan Coutts. [62]Cabal is the framework for packaging Haskell software * HaXml 1.19.1. Uploaded by Malcolm Wallace. [63]HaXml, Utilities for manipulating XML documents * HDBC-odbc 1.1.3.0. Uploaded by John Goerzen. [64]HDBC-odbc, ODBC driver for HDBC * HDBC-postgresql 1.1.3.0. Uploaded by John Goerzen. [65]HDBC-postgresql is a PostgreSQL driver for HDBC * HDBC-sqlite3 1.1.3.0. Uploaded by John Goerzen. [66]HDBC-sqlite3 is a Sqlite v3 driver for HDBC 62. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Cabal-1.2.2.0 63. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HaXml-1.19.1 64. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HDBC-odbc-1.1.3.0 65. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HDBC-postgresql-… 66. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HDBC-sqlite3-1.1… * HDBC 1.1.3. Uploaded by John Goerzen. [67]HDBC is a Haskell Database library * X11 1.3.0. Uploaded by Don Stewart. [68]X11 is a library of bindings to the X11 libraries and server * HsOpenSSL 0.3. Uploaded by Masatake Daimon. [69]HsOpenSSL, (Part of) OpenSSL binding for Haskell * Imlib 0.1. Uploaded by Cale Gibbard. [70]Imlib, Haskell binding for Imlib 2 * Stream 0.2.2. Uploaded by Wouter Swierstra. [71]Stream, a library for manipulating infinite lists. 67. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HDBC-1.1.3 68. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/X11-1.3.0 69. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HsOpenSSL-0.3 70. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Imlib-0.1 71. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Stream-0.2.2 * sat 1.0. Uploaded by AndriiZvorygin. [72]sat, CNF SATisfier * torrent 2007.10.27. Uploaded by David Himmelstrup. [73]torrent, BitTorrent file parser * bencode 0.2. Uploaded by David Himmelstrup. [74]bencode, Parser and printer for bencoded data. * SDL 0.5.1. Uploaded by David Himmelstrup. [75]SDL, binding to libSDL * NGrams 1.0. Uploaded by Justin Bailey. [76]ngrams, Simple application for calculating n-grams using Google 72. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/sat-1.0 73. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/torrent-2007.10.… 74. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bencode-0.2 75. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/SDL-0.5.1 76. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/NGrams-1.0 Discussion Bootstrapping Haskell. Andrew Copping [77]wondered how the first Haskell compilers were bootstrapped, leading to some interesting historical details. GHC 6.8 performance. Dan Piponi [78]asked about Haskell performance for low level array manipulation, with some excellent speedups produced by GHC 6.8 77. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/31459 78. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/31314 Jobs Software Development Engineer at MSR. Don Syme announced that [79]the F Sharp team is hiring! We have two positions open right now. The first is a software development engineer specializing in Visual Studio and libraries. The second Post Calendar is a software development engineer 79. http://cs.hubfs.net/blogs/f_team/archive/2007/10/30/3900.aspx PhD position at Chalmers. John Hughes [80]announced that the Functional Programming group at Chalmers is seeking to recruit a PhD student to work on domain-specific languages embedded in Haskell for hardware design, and for programming graphics processors. PhD positions in Sweden are 'real jobs', paying a respectable salary for up to five years. 80. http://article.gmane.org/gmane.comp.lang.haskell.general/15714 Blog noise [81]Haskell news from the [82]blogosphere. * [83]Scala for bioinformatics * [84]I like Haskell a lot * [85]Haskell history * [86]Continuation Passing Style for Monads * [87]Abuse: Is it ruby? Is it Haskell? It's both! * [88]Learning Haskell? * [89]For loops in Haskell * [90]A Simple Programming Puzzle Seen Through Three Differenent Lenses 81. http://planet.haskell.org/ 82. http://haskell.org/haskellwiki/Blog_articles 83. http://tiago.org/ps/2007/10/26/scala-for-bioinformatics/ 84. http://www.noulakaz.net/weblog/2007/04/20/i-like-haskell-a-lot/ 85. http://caos.di.uminho.pt/~ulisses/blog/2007/10/27/haskell-history/ 86. http://r6.ca/blog/20071028T162529Z.html 87. http://meta-meta.blogspot.com/2007/05/abuse-is-it-ruby-is-it-haskell-its-bo… 88. http://www.dynamicdrive.com/forums/showthread.php?t=26094 89. http://osfameron.vox.com/library/post/for-loops-in-haskell.html?_c=feed-atom 90. http://thraxil.org/users/anders/posts/2007/10/30/A-Simple-Programming-Puzzl… * [91]Scala Makes Me Think * [92]Haskell Substring Function * [93]Multicore Programming and Automatic Parallelisation * [94]Spinoza SOS in Haskell * [95]Why not just use Haskell? * [96]Chain delegates (in Haskell) * [97]Parser Combinators in C * [98]Will hybrid languages like D render functional languages like Haskell, OCaml and Common Lisp irrelevant? * [99]Category Theory for the Java Programmer * [100]Benchmarking ray tracing, Haskell vs. OCaml 91. http://blog.snowtide.com/2007/10/31/scala-makes-me-think 92. http://ironmonkey.blogspot.com/2007/10/haskell-substring-function_31.html 93. http://hnr.dnsalias.net/wp/?p=31 94. http://seta07.blogspot.com/2007/10/spinoza-sos-in-haskell.html 95. http://www.hackinghat.com/index.php/c/66 96. http://thoughtspam.spaces.live.com/Blog/cns!253515AE06513617!454.entry 97. http://www.math.chalmers.se/~koen/ParserComboC/parser-combo-c.html 98. http://pinderkent.blogsavy.com/archives/141 99. http://reperiendi.wordpress.com/2007/11/03/category-theory-for-the-java-pro… 100. http://augustss.blogspot.com/2007/11/benchmarking-ray-tracing-haskell-vs.ht… * [101]Some lambda calculus examples * [102]Beautiful timetables * [103]References, Arrows and Categories * [104]Anamorphisms in Ruby * [105]Type metaprogramming in Haskell and C++ * [106]A Small Combinatorial Library 101. http://augustss.blogspot.com/2007/11/some-lambda-calculus-examples-syntax-i… 102. http://onthebalcony.wordpress.com/2007/11/11/beautiful-timetables/ 103. http://twan.home.fmf.nl/blog/haskell/References-Arrows-and-Categories.detai… 104. http://weblog.raganwald.com/2007/11/really-useful-anamorphisms-in-ruby.html 105. http://www.rubinsteyn.com/template_insanity.html 106. http://sigfpe.blogspot.com/2007/11/small-combinatorial-library.html Quotes of the Week * faxathisia: Omg! I spent 2 days writing this code and it's worked the first time I run it. Only possible with Haskell :D * anonymous: The thing is Haskell isn't suited for young people, whereas the OBJECT model of C++ is * sethg: I feel like I still dont understand comonads * fnord123: Haskell mainly helps with my C++ template coding when I'm doing money oriented programming * Tac-Tics: I get the feeling if all I ever use is the IO monad, someone here will shower me in holy monad fire and cleanse the evil from me.... leaving burn marks all over * Anton van Straaten: there's a new movement towards 'functional eating' which involves using a knife and fork (think ML) or chopsticks (Haskell ;) instead of a chainsaw. Its proponents claim that this approach is far superior, but chainsaw fans are skeptical. * SamB: what happens in the monad... stays in the monad... * Brent Yorgey: Friends don't let friends write in COBOL. * Bulat Ziganshin: It's a whole new era in low-level GHC programming About the Haskell Weekly News New editions are posted to [107]the Haskell mailing list as well as to [108]the Haskell Sequence and [109]Planet Haskell. [110]RSS is also available, and headlines appear on [111]haskell.org. Headlines are available as [112]PDF. To help create new editions of this newsletter, please see the [113]contributing information. Send stories to dons at galois.com. The darcs repository is available at darcs get [114]http://code.haskell.org/~dons/code/hwn/ 107. http://www.haskell.org/mailman/listinfo/haskell 108. http://sequence.complete.org/ 109. http://planet.haskell.org/ 110. http://sequence.complete.org/node/feed 111. http://haskell.org/ 112. http://code.haskell.org/~dons/code/hwn/archives/20071111.pdf 113. http://haskell.org/haskellwiki/HWN 114. http://code.haskell.org/~dons/code/hwn/

1 0

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