- Haskell-Cafe - Haskell.org

UTF-16
by Andrew Coppin 26 Jul '07

26 Jul '07

I don't know if anybody cares, but... Today a wrote some trivial code to decode (not encode) UTF-16. I believe somebody out there has a UTF-8 decoder, but I needed UTF-16 as it happens. (I didn't bother decoding code points outside the BMP - I'm sure you can figure out why.) If anybody is interested, I can share the code - but it's pretty minimal...

5 6

Fwd: [Haskell-cafe] HDBC or HSQL
by George Moschovitis 26 Jul '07

26 Jul '07

Ok, I am evaluating HDBC. I wrote a simple test program: import Database.HDBC import Database.HDBC.PostgreSQL main = do db <- connectPostgreSQL "dbname=Test user=postgres password='mypass'" putStrLn "done" when I run it I get the following error: db: exception :: Database.HDBC.SqlError Can I get a more specific error? Is there a way to inspect this exception more deeply? thanks, -g. -- http://www.me.gr http://phidz.com http://blog.gmosx.com http://cull.gr http://www.joy.gr http://nitroproject.org

1 1

expension of fractions
by Tom Pledger 26 Jul '07

26 Jul '07

Arie Groeneveld wrote: : | Looking at the result of my rewriting gives me the idea it isn't | Haskelly enough. | | Anyways, here's my interpretation: | | -- period m/n base = (period length, preperiod digits, period digits) | period :: Integer -> Integer -> Integer -> (Int, ([Integer], [Integer])) : Haskelliness I'd be inclined to try using a Rational (from Data.Ratio) and the properFraction function, instead of numerators and denominators and gcd. You could do away with the parts where you subscript a linked list, if you did something with elem and zip and span instead of findIndex and splitAt. Instead of translating Nothing to -1 and Just i to i, you could use the result of findIndex directly in a case expression. Correctness *Main> period 8 70 10 (6,([0],[5,7,1,4,2,8])) That should be (6,([1],[1,4,2,8,5,7])). Regards, Tom

1 0

Compile-time here document facility
by Dave Bayer 26 Jul '07

26 Jul '07

I couldn't find a compile-time here document facility, so I wrote one using Template Haskell: > module HereDocs(hereDocs) where > > import Control.Exception > import Language.Haskell.TH.Syntax > > getDoc :: String -> [String] -> (String,[String]) > getDoc eof txt = > let (doc,rest) = break (== eof) txt > in (unlines doc, drop 1 rest) > > makeVal :: String -> String -> [Dec] > makeVal var doc = let name = mkName var in > [SigD name (ConT (mkName "String")), > ValD (VarP name) (NormalB (LitE (StringL doc))) []] > > scanSrc :: [Dec] -> [String] -> Q [Dec] > scanSrc vals [] = return vals > scanSrc vals (x:xs) = case words x of > [var, "=", ('<':'<':eof)] -> > let (doc,rest) = getDoc eof xs > val = makeVal var doc > in scanSrc (vals ++ val) rest > _ -> scanSrc vals xs > > hereDocs :: FilePath -> Q [Dec] > hereDocs src = > let fin = catchJust assertions (evaluate src) (return.takeWhile > (/= ':')) > in runIO (fin >>= readFile >>= return . lines) >>= scanSrc [] One binds here documents embedded in comments by writing > import HereDocs > $(hereDocs "Main.hs") As an idiom, one can refer to the current file as follows; the first thing hereDocs does is catch assert errors in order to learn the file name: > import HereDocs > $(hereDocs $ assert False "") Here is an example use: > {-# OPTIONS_GHC -fth -Wall -Werror #-} > > module Main where > > import System > import Control.Exception > > import HereDocs > $(hereDocs $ assert False "") > > {- > ruby = <<RUBY > #!/usr/bin/env ruby > hello = <<EOF > Ruby is not > an acceptable Lisp > EOF > puts hello > RUBY > > lisp = <<LISP > #!/usr/bin/env mzscheme -qr > (display #<<EOF > Lisp is not > an acceptable Haskell > EOF > ) > (newline) > LISP > -} > > exec :: FilePath -> String -> IO ExitCode > exec fout str = do > writeFile fout str > system ("chmod +x " ++ fout ++ "; ./" ++ fout) > > main :: IO ExitCode > main = do > exec "hello.rb" ruby > exec "hello.scm" lisp

4 3

upgrading Text.Printf
by Benjamin Franksen 26 Jul '07

26 Jul '07

Hi, I am using Text.Printf (package base, ghc-6.6.1) and am missing %X formatting. Checking out the darcs repo of the base package I see that it has already been added there. Is there any way to upgrade to the latest version while keeping ghc-6.6.1? I keep hearing Bulat saying that this is not possible, but I wanted to check anyway. Is there, perhaps, a separate package that contains (a newer version of) Text.Printf? Cheers Ben

2 2

Another analogy
by Andrew Coppin 26 Jul '07

26 Jul '07

From the guy who brought you "data in Haskell is like an undead quantum cat", I present the following: "If programming languages were like vehicles, C would be a Ferrari, C++ would be a Porshe, Java would be a BWM and Haskell would be a hovercraft. It doesn't even have WHEELS! There is no steering wheel, no gearbox, no clutch... it doesn't even have BRAKES!!! It completely turns the rules upside down. I mean, it moves by PUSHING AIR. That's just crazy! It even STEERS by pushing air. It sounds so absurd, it couldn't possibly work... ...oh, but it DOES work. Very well, actually. In fact, a hovercraft can do some things that the others can't. It works on water. It can go sideways. It can REALLY turn on the spot." Insert whitty replies here...

6 8

Printing the function result
by Alexteslin 26 Jul '07

26 Jul '07

Hi, I am going through examples from the textbook and trying them out but some don't work. For example: addNum :: Int -> (Int -> Int) addNum n = addN where addN m = n+m This error message i am getting: ERROR - Cannot find "show" function for: *** Expression : addNum 4 *** Of type : Int -> Int Now, the type of show is a->String, but i need some kind of function to print the function as a result. I tried some input output functions but i don't think that is the right way to follow. Can anyone suggest me where to look? Thank you -- View this message in context: http://www.nabble.com/Printing-the-function-result-tf4145303.html#a11790986 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 3

NDP documentation
by Andrew Coppin 26 Jul '07

26 Jul '07

Actually, I was just reading through all the Data Parallel Haskell and Nested Data Parallelism documentation. It says in several places that "parallel array comprehensions are available since GHC 6.6, but they are broken; please use the development versions; this will be fixed in GHC 6.6.1". Can anybody clarify - was this actually fixed? (And shouldn't somebody update the Wiki?)

4 4

filterFirst
by Alexteslin 26 Jul '07

26 Jul '07

Hi, first I like to thank all of you guys - it really helps! I am still on a same chapter with higher order functions and this function is also confusing. But before i even define this function i am getting the type error - i don't know why? So i wrote the simpler one like: filterAlpha :: (a -> Bool) -> [a] -> [a] filterAlpha f [] = [] filterAlpha f (x:xs) |f x = x : filterAlpha xs |otherwise = filterAlpha xs and i am getting this error message: Type error in application Expression :filterAlpha xs Type : [b] Dous not match : a -> Bool To even my very little knowledge i think that this should work. What am i doing wrong? Thanks again -- View this message in context: http://www.nabble.com/filterFirst-tf4131377.html#a11749336 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 5

snoc vs cons
by Eric 26 Jul '07

26 Jul '07

Does anyone know of a good article which discusses snoc vs cons lists? E.

4 4

GHC and GLUT
by Paul L 25 Jul '07

25 Jul '07

I wonder if anybody has experience with the GLUT library that GHC currently supports? I was trying to use freeglut because I need the actionOnWindowClose function. GHC documentation seems to indicate it's possible to do this, but my effort isn't successful. I even replaced the system-wide libglut.so with the new libglut.so that comes with freeglut installation, but GHC still won't recognize it's now freeglut and I still can't use the actionOnWindowClose function. This is on Linux, and I've not tried Windows. Do I need to compile GHC myself in order to enable freeglut support? Any help is greatly appreciately! Regards, Paul L

2 2

i need wxHaskell compiled for ghc 6.6.1 on Windows
by Bulat Ziganshin 25 Jul '07

25 Jul '07

Hello haskell-cafe, can anyone provide wxHaskell already compiled/compilable with ghc 6.6.1 on Windows? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

6 16

GHC 6.6.1: Where is Graphics.SOE ?
by Dmitri O.Kondratiev 25 Jul '07

25 Jul '07

Olivier Boudry olivier.boudry(a)gmail.com wrote: (Wed Jul 18 11:56:56 EDT 2007) >Hi Dmitri, > >I built gtk2hs on Windows with GHC 6.6.1 and gtk2hs-0.9.11. Here's are the >steps that worked for me: (not sure I didn't missed some) > >First you need to install a GTK+ development package for windows. I think >mine comes from http://gladewin32.sourceforge.net/modules/wfdownloads/ > >Then you must have MSYS and MinGW installed on your computer. You'll find >information on how to install this here: >http://hackage.haskell.org/trac/ghc/wiki/Building/Windows. > >Once you've installed that stuff you can start a MSYS shell. You'll need to >set some environment variables for GTK (adapt to your path): >export GTK_BASEPATH=/c/GTK_2.0 >export GTK_CONFIG_PATH=/c/GTK_2.0/lib/pkgconfig > >Cd to the gtk2hs source directory and type: >./configure --prefix=/c/Progra~1/Haskell >make >make install > >Hope this helps. > >Good luck, > >Olivier. Oliver, thanks! I tried that, yet have some problems. I use: GHC 6.6.1, current development version of Gtk2hs (not sure what version), Gtk+ 2.10.11 (Win32) and latest available from MinGW distributions: MSYS-1.0.10.exe msysDTK-1.0.1.exe msys-autoconf-2.59.tar.bz2 msys-automake-1.8.2.tar.bz2 msys-libtool-1.5.tar.bz2 Problem 1. Gtk2hs build requires to run autoreconf. So in MSYS I have: $ autoreconf /usr/share/aclocal/autoopts.m4:22: warning: underquoted definition of AG_PATH_AUTOOPTS run info '(automake)Extending aclocal' or see http://sources.redhat.com/automake/automake.html#Extending%20aclocal configure.ac:101: error: possibly undefined macro: AC_MSG_ERROR If this token and others are legitimate, please use m4_pattern_allow. See the Autoconf documentation. autoreconf: /usr/bin/autoconf failed with exit status: 1 Notwithstanding this error autoreconf creates configure script. When I run it I get: Problem 2. $ ./configure --with-hc=/c/usr/ghc-6.6.1 --prefix=/c/usr/ghc-6.6.1 checking for a BSD-compatible install... /bin/install -c checking whether build environment is sane... yes checking for gawk... gawk checking whether make sets $(MAKE)... yes checking build system type... i686-pc-mingw32 checking host system type... i686-pc-mingw32 checking for style of include used by make... GNU checking for gcc... no checking for cc... no checking for cc... no checking for cl... no configure: error: no acceptable C compiler found in $PATH Questions: 1) Should I ignore autoreconf errors? 2) I thought that building Gtk2hs is done with GHC only. Is it right that build requires C compiler? 3) Any other ideas what is wrong with this build? Thanks! -- Dmitri O. Kondratiev dokondr(a)gmail.com http://www.geocities.com/dkondr

2 2

[meta] the haskell wiki management
by Andrea Rossato 25 Jul '07

25 Jul '07

Hi, this is what happened to me recently. Recently I had the opportunity to join the community around XMonad, a project, you should know something about it, led by some well know haskellers. It's a very exiting project, and by joining it you have the opportunity to code with people who know Haskell very well. Moreover those guys are very friendly and willing to help newcomers like me. Thanks to them I came to build up some knowledge about X window programming in Haskell - Robert and Spencer being my two principal mentors. I have this problem of mine, that when I feel grateful to someone I must find a way to get even, and I thought that writing a tutorial for newcomers could be a form of paying back the XMonad community, a subgroup of the Haskell community after all. I though that using the Haskell wiki was appropriate, so I started writing down what I learned thanks to those guys. As you may understand writing a tutorial is time consuming: not only you have to write the code and the code must be possibly clear. But I have also another problem: English is not my mother tongue, I'm sure you know that by now. So, while writing - eventually it took me up to 20 hours of work to finish the tutorial -, I started a new wiki page and updated it as new stuff was written: "X Window Programming in Haskell" was the page title. Then suddenly, Sunday night, I could not find my page anymore. So I went to "recent changes" to find out that someone had decided to change the page title to "X window programming", right after editing it. Not to remove some of the huge amount of typos, not to rephrase a sentence that a (properly) English speaker could not understand, not to debug some code, not to improve the content. No, just to enforce a rule, written here: http://www.haskell.org/haskellwiki/HaskellWiki:Guidelines A rule that reads: "Titles should use sentence-style capitalization (see [1] - wikipedia). Capitalizing more words seems to be only appropriate in larger documents like books." "Seems to be only appropriate in larger documents like books." This makes me laugh, really. I got really upset and went to the talk page of the guy who moved the page to ask for an explanation. And I moved the page back to its original title: it was not a tutorial about x window programming, but about x window programming in Haskell. And so I found out these guidelines I was not even aware of. And that people were actually enforcing them. Now, that's fine, it is a wiki after all, and authorship must be forgotten. I didn't have this feeling when I discovered the wiki for the first time. In many tutorial you could and still can find a signature. You know, I'm an academic type of guy: I don't care about copyright at all, but I care a lot about authorship. I know, this is my fault. Now, what happened next? The guy I was upset with decided to change the rules and added this to the guidelines page: "When doing a signficant renaming of a page, (i.e., something more than just correcting the case as per the guidelines), use the "Discuss this page" link to suggest the new title and the reasons why. After a reasonable amount of time, if there are no objections, go ahead and move / rename the page." But five minutes later he also decided that it was time for the new rule to be violated by the rule setter himself, and renamed other tutorials of mine, something I've written a year ago or so, without making any suggestion in the discussion page. You know, changing a wiki page title means breaking all links to that page from other sites. So, changing an old page title, means taking that page off the Net. This is fine with me and my contributions to the Haskell wiki: useless stuff that is better not reading than reading. On the other side, I'm not going to stand such behaviour and I'm not going to write a single word on that wiki anymore. I removed my signature from the x window tutorial. I'm human too, I would add. Nonetheless I do not understand if this is an explicit policy of getting rid of unwanted contributors, like me, or just a stupid way of managing a collective resource like a wiki. Having a group of people in charge of setting, enforcing and violating rules at their will is a nice form of government, that usually pisses people off. And it is very difficult to adopt such an attitude to piss only unwanted people off. You usually end up repelling people you would like to attract too. I believe it is inevitable. This is the only reason I'm writing this. Sorry for such a long useless letter, but I've seen that the Haskell community loves to talk about maintaining itself, and so on. I thought that my 2 cents could be enjoyable too. Regards, Andrea Rossato

2 3

partitions of a multiset
by Brent Yorgey 25 Jul '07

25 Jul '07

Hi all, I've written some code to generate set partitions: import Control.Arrow import Data.List -- pSet' S generates the power set of S, with each subset paired -- with its complement. -- e.g. pSet' [1,2] = [([1,2],[]),([1],[2]),([2],[1]),([],[1,2])]. pSet' :: [a] -> [([a],[a])] pSet' [] = [([],[])] pSet' (x:xs) = mp first ++ mp second where mp which = map (which (x:)) psRest psRest = pSet' xs -- partitions S generates a list of partitions of S. -- e.g. partitions [1,2,3] = [[[1,2,3]],[[1,2],[3]],[[1,3],[2]],[[1],[2,3]],[[1],[2],[3]]]. partitions :: [a] -> [[[a]]] partitions [] = [[]] partitions (x:xs) = (pSet' xs) >>= ((x:) *** partitions >>> uncurry (map . (:))) However, this version of partitions generates duplicates when given a multiset, for example: *Combinatorics> partitions [1,1,2] [[[1,1,2]],[[1,1],[2]],[[1,2],[1]],[[1],[1,2]],[[1],[1],[2]]] The partition [[1,2],[1]] is generated twice (order doesn't matter). I'd like to write a version of partitions which generates duplicate-free output even for input multisets, but haven't come up with a good method yet. Any ideas? -Brent PS Yes, this is for Project Euler. =)

3 5

Re: [Haskell] Re: View patterns in GHC: Request for feedback
by Claus Reinke 25 Jul '07

25 Jul '07

>> unit :: Typ -> Maybe () >> arrow :: Type -> Maybe (Typ,Typ) >> size :: Typ -> Integer >> size (unit -> ()) = 1 >> size (arrow -> (t1,t2)) = size t1 + size t2 > Though I guess you would not object to: > > size (unit -> Just ()) = 1 > size (arrow -> Just (t1,t2)) = size t1 + size t2 > ? actually, i might!-) it is not just that, in general, you have to invent and declare those intermediate view types, but that their use obscures the overall pattern, once you start nesting abstract and concrete patterns (and if you don't nest them, view patterns don't add much). claus

1 0

Dealing with large OOHaskell records
by Scott West 25 Jul '07

25 Jul '07

Hello all, Does anyone have any experience with using large-ish (20 element) OOHaskell records? I'm finding that as the records get large, compile times get fairly ridiculous. Is there some explicit typing I should be doing to help the type-checker? Thanks! Scott

1 0

expension of fractions
by Arie Groeneveld 24 Jul '07

24 Jul '07

Hi, I don't know if this is the right place to post this, but here I go. I translated a BC-program found on the home page of Keith Matthews, http://www.numbertheory.org/keith.html. It's about the expension of a (not necessarily reduced) fraction m/n in base b. Looking at the result of my rewriting gives me the idea it isn't Haskelly enough. Anyways, here's my interpretation: -- period m/n base = (period length, preperiod digits, period digits) period :: Integer -> Integer -> Integer -> (Int, ([Integer], [Integer])) period m n base | m' >= n' = error $ show m ++ " >= " ++ show n | m' < 1 = error $ "m (" ++ show m ++ ") < 1" | n' < 1 = error $ "n (" ++ show n ++ ") < 1" | base <= 1 = error $ "base (" ++ show base ++ ") < 2" | otherwise = decimals [] [m'] where g = gcd m n m' = m `div` g n' = n `div` g decimals qs rs | i' /= -1 = (length rs - i', splitAt i' qsi) | otherwise = decimals qsi (rs++[ri]) where (qi,ri) = divMod (base * last rs) n i = findIndex (==ri) rs i' = if i == Nothing then -1 else fromJust i qsi = qs++[qi] Which comes from the BC program: (Keith Matthews) define period(m,n,b){ auto a[],g,i,p,j,c[] g=gcd(m,n) m=m/g;n=n/g if(m>=n){"m>=n:"; return(0)} if(m<1){"m<1:"; return(0)} if(n<1){"n<1:"; return(0)} if(b<=1){"b<=1:"; return(0)} i=0 c[0]=m flag=0 while(flag==0){ p=b*c[i] i=i+1 c[i]=p%n a[i]=p/n /*print "a[",i,"]=",a[i],"\n" /* the i-th digit */ if(i==1000){ print "limit of 1000 digits produced\n" return(0) } for(j=0;j<i;j++){ if(c[i]==c[j]){ flag=1 break } } } print "the expansion of ",m,"/",n," to base ",b,"\n" if(j){ print "preperiod digits: " for(k=1;k<=j;k++){ print a[k],"," } print "\n" } print "period digits: " for(k=j+1;k<=i;k++){ print a[k] if(k<i){ print "," } } print "\n" t=i-j "period-length = ";return(t) }

1 0

Optimising UTF8-CString -> String marshaling, plus comments on withCStringLen/peekCStringLen
by Alistair Bayley 24 Jul '07

24 Jul '07

Hello cafe, D'ya fancy an optimisation exercise? In Takusen we currently marshal UTF8-encoded CStrings by first turning the CString into [word8], and then running this through a [Word8] -> String UTF8 decoder. We thought it would be more space-efficient (and hopefully faster) to marshal directly from the CString buffer, rather than use an intermediate list. We assumed it would be most space-efficient by working backwards from the end of the CString buffer, like the peekArray/peekArray0 functions in Foreign.Marshal.Array. So I implemented it and benchmarked against the original UTF8 marshaling function, which simply converts CString -> [Word] -> String. And to my surprise, the [Word8] -> String solution seems to be faster, and uses less memory, than the function which creates the String directly from the CString buffer. Now I appreciate that GHC's optimisations are quite effective (presumably deforestation should take credit here), but I thought I'd ask the haskell-cafe optimiser if we could do better with the direct-from-buffer function. I'm loath to start eyeballing GHC Core, but if needs must... The code is attached. I also have some comments/questions about the various CStringLen functions in Foreign.C.String. The Haddock comment for CStringLen states: "A string with explicit length information in bytes..." and for CWString something similar: "A wide character string with explicit length information in bytes..." I know this is a blatant lie, though, because the code (unless I've grossly misunderstood it) for newCStringLen, withStringLen, newCWStringLen, and withCWStringLen all return the number of Haskell Chars in the String i.e. the number of Unicode chars, NOT the number of bytes. However, for the sake of inconsistency, the peekC{W}StringLen functions take, respectively, the number of Word8 or Word16/Word32 elements (whether CWString is Word16 or Word32 depends on your plaform, apparently) in the C{W}String array/buffer. So the outputs from newCStringLen etc are not reliably usable as inputs to their duals (peekCStringLen etc.) The only cases that they do work in this way is where the CStrings are encoded with fixed-width encodings i.e. there are no surrogate units in the encoding. So we have three different approaches: 1. Haddock comments say bytes 2. with/newC{W}StringLen returns unicode char count 3. peekC{W}StringLen expects Word8 or Word16 count (1) and (3) can be considered equivalent, in the sense that if you know the number of Word16 units then you know the number of Word8 units, and vice versa. It'd be nice if we could have one consistent aproach. For a start, I think we should eliminate (2), because it's dead easy the get the number of unicode chars from a String (length, if you didn't know). So whether to settle on (1) or (3) depends on what the most likely use case is for the length information. Presumably it's going to be passed to a foreign function which expects the length either in bytes or in Word16/Word32 units. Does anyone have any evidence or opinion as to which case is the most common: bytes, or encoding units? Alistair

6 11

Profiling and Threading: never the twain shall meet
by Dougal Stanton 24 Jul '07

24 Jul '07

Hi Haskellers, It seems that profiling and threading are not supported at the same time in GHC6.6. At least, it objects to using both the flags at the same time, and there's a Trac entry for that issue. So I just wanted to be sure that I really need threading. I'm passing text through some filters written in perl, just ordinary command line programs. I do it like this: > do > (hin, hout, herr, ph) <- runInteractiveProcess cmd args Nothing Nothing > forkIO $ hPutStr hin content >> hClose hin > out <- hGetContents hout > return (ph, out) which seems to require threading. If I compile without, it will hang indefinitely, I presume deadlocked. Is there a way this can be done without threading? But it's not a great issue for me if I can't do profiling in this case. I just wanted to try out the feature, and it seemed worthwhile checking I was doing this right. Cheers, Dougal.

3 2

My Haskell ICFP '07 Programming Competition entry
by Antoine Latter 24 Jul '07

24 Jul '07

Hello, I'd just like to call attention to a few recent blog posts containing myself and my friend Creighton's entry into the ICFP '07 programming competition. Mainly because I'm looking to find someone who knows Haskell and the contest so they can tell me where my bug is :) Also, if anyone wants to see a Haskell approach towards the contest's DNA to RNA conversion, here you go. It's not always idiomatic HAskell, but that's what happens in a 72 hour contest. Any feedback would be appreciated. The bug (I believe) occurs somewhere in the implementation of "matchpattern", which is in the fourth URL. Bellow are the URLs of the Haskell source code (with comments included as blog posts). We only got as far as the DNA to RNA conversion algorithm. -Antoine http://panicsonic.blogspot.com/2007/07/icfp-07-post-mortem-i.html http://panicsonic.blogspot.com/2007/07/icfp-07-post-mortem-ii.html http://panicsonic.blogspot.com/2007/07/icfp-07-post-mortem-iii.html http://panicsonic.blogspot.com/2007/07/icfp-07-post-mortem-iv.html

2 1

Minim interpreter
by Jon Harrop 24 Jul '07

24 Jul '07

Anyone care to code up a Haskell implementation of this trivial interpreter for comparison: http://groups.google.co.uk/group/comp.lang.lisp/browse_frm/thread/7b1ab36f5… -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

5 9

Re: Genuine Eratosthenes sieve [Was: Optimization fun]
by Jens Blanck 24 Jul '07

24 Jul '07

> > The point about "Eratosthenes's sieve" is that it does not specify > algorithmically how to find the next number to be crossed. It does not > even define how to store (crossed) numbers, it stores them "on paper". But , I believe that Eratosthenes's sieve does specify how to store numbers and how to find the next to cross out. This is how I remember it: 0 List the numbers from 2 onwards. 1 Take first uncrossed number, say p. 2 Cross every pth number from there on (crossed or not). 3 Repeat from 1. That "crossed or not" appears above makes repeated filters very tricky. It is trivial with a mutable array, but that is not the preferred way so one needs to somehow merge the crossing out lists. I haven't looked at it really, but being sorted lists I would have thought that this merger would be easy without resorting to things like priority queues, could someone point this out to me? The above mayeasily be optimised to only listing odd numbers (still cross out every pth number in the list), and much less importantly by starting from whereever p*p is. Jens

12 22

Frustrating experience of a wannabe contributor
by Andreas Marth 24 Jul '07

24 Jul '07

Today I had 2 hours time and thought I might contribute to the haskell community. The topic I thought I might be able to give some hints is about creating DLLs. So I went to www.haskell.org which redirected me to the wiki www.haskell.org/haskellwiki/Haskell. So I entered "DLL" into the search to find what is already there and thus began the unpleasant experience. There was nothing in the search result. So I tried to find a place where it might have posted or at least fit into. That was the next step into nowhere. There is an entry "Contributing to this site" which leads to http://www.haskell.org/haskellwiki/HaskellWiki:Contributing, but thats gives zero directions where to put what or how to contribute efficiently. There are two other categories under "Learning Haskell": "Wiki articles" and "Blog articles". After going to "Blog articles" it was clear that it was not the right place either. So I went to "Wiki articles" (http://www.haskell.org/haskellwiki/Category:Haskell) which had such interesting subcategories as "Orphaned projects" and "News". (Remember this is under "Learning Haskell".) At this point I dicided that I might eventually post here under "Tutorials", but first try to find out was is already there. With there I meant the knowledge in the mailing lists. So I went to http://www.haskell.org/haskellwiki/Mailing_lists and there to the archives http://www.haskell.org/pipermail/haskell/ and http://www.haskell.org/pipermail/haskell-cafe/. Unfortunately you cant search this. So I went back and after reading through the mailing list page again went to http://www.mail-archive.com/haskell@haskell.org/index.html. That is the place where you can search the archive. Unfortunately you get the results in a totally mixed up order. When you click on the "Date" link you get it sorted, but it is not your search that is sorted it is the whole archive that is sorted. If you search again you get the same mixed up result as before. So it is not possible t get your search results sorted. (I had a quick check at "refine search" link (http://www.mail-archive.com/faq.html#search) but that gives me only the syntax for different filters but no sorting.) That was the time where I decided it might be best to write this experience down to maybe give some impulses to change. I did a last search on the haskell wiki for "create" as I thought the would be something that would be used in the DLL context and sure enough that generates 133 results and 2 of them are about DLLs (http://www.haskell.org/haskellwiki/GHC/FAQ and http://www.haskell.org/haskellwiki/GHC/Using_the_FFI) So it is not that there isn't anything about DLLs on the wiki it just doesn't find it. (By the way http://www.haskell.org/haskellwiki/GHC/FAQ links to http://www.haskell.org/ghc/docs/latest/html/users_guide/win32-dlls.html#win3 2-dlls-foreign wich has a typo for generations but is not editable.) If that is the experience someone gets early on in his haskell adventure he might very well get frustrated. So what to do? 1.) make the wiki search function return all documents containig the search term 2.) create a USEFUL search function for the mailing archives 3.) consider creating a new wiki topic "Problems and solutions working with haskell" I am especially woried about the unusable information in the mailing list archives. We have a great community here and lots of wonderful information was exchanged here but it is not accesible right now! Sorry for the long post I hope it is useful in one way or another. PS: I am in this community for a few years already so this hassle didn't drive me away from haskell, but I must say that similar experiences drove me away from a few haskell projects I had interests in (wxHaskell comes to mind). And it might also be a good idea to have a category "Fata morgana of solved problems" or so. What would qualify? COM interaction, HDirect and from the mailing list today: haskell_mod. An early move of a project into that category might a) stipulate a change of maintainer ship early enough before to much knowledge is lost and b) gives a clear warning that things might be more difficult than all the research papers imply (see COM integration).

9 15

Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)
by Dave Bayer 24 Jul '07

24 Jul '07

As an exercise, trying to understand the beautiful paper Stream Fusion From Lists to Streams to Nothing at All Duncan Coutts, Roman Leshchinskiy and Don Stewart http://www.cse.unsw.edu.au/~dons/papers/CLS07.html http://www.cse.unsw.edu.au/~dons/streams.html I recoded my prime sieve using a pared down version of their Stream datatype; this is the simplest version I could write that achieves a significant speedup. My reaction to their paper was, if streams are better internally than lists, why not code directly in streams? Lists enjoy a serious notational advantage in Haskell, but one could imagine a language where the list notation was reserved for stream semantics. My sieve was spending half its time in "merge", so I made only the changes necessary to convert "merge" to use streams. My streams are infinite, and "merge" can be written to not use Skip, so Step goes away. Even though "nextx" and "nexty" only have one case now, using case statements is significantly faster than using let or where clauses. I'm imagining that I read about this somewhere, but if I did, it didn't sink in until I was tuning this code. I don't know if this is related to fusion optimization, or a general effect. The timings are > [Integer] -O2 1*10^6 2*10^6 3*10^6 4*10^6 5*10^6 > --------------------------------------------------------- > ONeillPrimes | 3.338 | 7.320 | 11.911 | 18.225 | 21.785 > StreamPrimes | 3.867 | 8.405 | 13.656 | 21.542 | 37.640 > BayerPrimes | 3.960 | 8.940 | 18.528 | 33.221 | 38.568 Here is the code: > {-# OPTIONS_GHC -fglasgow-exts #-} > > module StreamPrimes (primes) where > > -- stream code > > data Stream a = forall s. Stream (s -> (a,s)) s > data AStream a = A a (AStream a) | B (Stream a) > > stream :: [a] -> Stream a > stream xs = Stream next xs > where > next [] = undefined > next (x:xt) = (x,xt) > > astream :: [a] -> AStream a > astream [] = undefined > astream (x:xt) = A x $ B $ stream xt > > merge :: Ord a => Stream a -> Stream a -> Stream a > merge (Stream nextx vs) (Stream nexty ws) = > Stream next (vt,ws,Left v) > where > (v,vt) = nextx vs > next (xs,ys,Left x) = > case nexty ys of > (y,yt) -> > if x < y > then (x,(xs,yt,Right y)) > else (y,(xs,yt,Left x)) > next (xs,ys,Right y) = > case nextx xs of > (x,xt) -> > if x < y > then (x,(xt,ys,Right y)) > else (y,(xt,ys,Left x)) > > mergeA :: Ord a => AStream a -> AStream a -> AStream a > mergeA (A x xt) ys = A x (mergeA xt ys) > mergeA (B xs) ys = mergeB xs ys > > mergeB :: Ord a => Stream a -> AStream a -> AStream a > mergeB s@(Stream next xs) ys@(A y yt) = > case next xs of > (x,xt) -> > if x < y > then A x (mergeB (Stream next xt) ys) > else A y (mergeB s yt) > mergeB xs (B ys) = B $ merge xs ys > > -- Code for venturi :: Ord a => [[a]] -> [a] > > root :: Ord a => AStream a -> [AStream a] -> [a] > root (A x xt) yss = x : (root xt yss) > root (B xs) (ys:yst) = root (mergeB xs ys) yst > root _ _ = undefined > > pair :: Ord a => [AStream a] -> [AStream a] > pair (x:y:xt) = mergeA x y : (pair xt) > pair _ = undefined > > group :: Ord a => [AStream a] -> [AStream a] > group (x:xt) = x : (group $ pair xt) > group _ = undefined > > venturi :: Ord a => [[a]] -> [a] > venturi (x:xt) = root (astream x) $ group $ map astream 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)

1 0

Equational Reasoning goes wrong
by Neil Mitchell 23 Jul '07

23 Jul '07

Hi Haskell is known for its power at equational reasoning - being able to treat a program like a set of theorems. For example: break g = span (not . g) Which means we can replace: f = span (not . g) with: f = break g by doing the opposite of inlining, and we still have a valid program. However, if we use the rule that "anywhere we encounter span (not . g) we can replace it with break g" then we can redefine break as: break g = break g Clearly this went wrong! Is the folding back rule true in general, only in specific cases, or only modulo termination? Thanks Neil

11 10

Practise fingerspelling with Haskell! (Code cleanup request)
by Dougal Stanton 23 Jul '07

23 Jul '07

The following is a slap-dash program for generating a list of pairs of words which differ by, at most, one letter. It's quite verbose at the moment, because (a) that was the way I wrote it, a snippet at a time, and (b) I lack the wit to make it shorter. Can anyone recommend ways to make this program more efficient/neat/elegant? It runs in decent time on my machine, but it's not exceedingly pretty and I'm sure it can be made shorter too. (The full thing can be found at <http://193.219.108.225/code/fingerspell/> if you want to pull in a working version to play with. The purpose of the program is for a game to practise fingerspelling when learning sign language. More on that here: <http://brokenhut.livejournal.com/265471.html>.) Cheers, D. ---- edited highlights below ---- -- Number of letters difference between two words. difference :: Pair -> Int difference = length . filter (==False) . uncurry (zipWith (==)) -- Keep only pairs that differ by at most -- one letter difference. keepOneDiff :: PairSet -> PairSet keepOneDiff = map snd . filter (\x -> (fst x) < 2) . map (difference &&& id) -- Pairs of words of equal length, sorted to reduce -- duplicates of (a,b), (b,a) type. They shouldn't -- be completely eradicated because part of the game -- is to spot when they;re the same word. listPairs :: WordSet -> PairSet listPairs ws = [ (w, w') | w <- ws, w' <- ws, length w == length w', w <= w' ] -- Take N pairs of words which are the same -- length and differ by at most one letter. wordpairs :: Int -> WordSet -> PairSet wordpairs n = take n . keepOneDiff . listPairs fingerspell wl p = do wordfile <- words `liftM` readFile "/usr/share/dict/words" mapM_ pretty $ wordpairs p $ filter (requirements) wordfile -- Make sure all the words are of the required length and are -- just made up of letters, not punctuation. where requirements w = length w == wl && all (isAlpha) w pretty (x,y) = putStrLn $ x ++ ", " ++ y

5 10

Haskell Weekly News: July 23, 2007
by dons＠cse.unsw.edu.au 23 Jul '07

23 Jul '07

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20070723 Issue 63 - July 23, 2007 --------------------------------------------------------------------------- Welcome to issue 63 of HWN, a weekly newsletter covering developments in the [1]Haskell community. This week, the HWN rises zombie-like from its repository, as your friendly HWN editor tries to get his PhD finished. This bumper issue is filled out with 100 new Haskell blog articles and dozens of new libraries! 1. http://haskell.org/ Announcements Learn Haskell in 10 minutes. Chris Smith [2]prepared a new tutorial on the basics of Haskell 2. http://haskell.org/haskellwiki/Learn_Haskell_in_10_minutes Haskell Program Coverage 0.4. Andy Gill [3]announced release 0.4 of Hpc, a tool for Haskell developers. Hpc is a tool-kit to record and display Haskell Program Coverage. Hpc includes tools that instrument Haskell programs to record program coverage, run instrumented programs, and display the coverage information obtained. 3. http://article.gmane.org/gmane.comp.lang.haskell.general/15381 Uniplate 1.0. Neil Mitchell [4]announced Uniplate (formerly known as Play), a library for boilerplate removal requiring only Haskell 98 (for normal use) and optionally multi-parameter type classes (for more advanced features). 4. http://article.gmane.org/gmane.comp.lang.haskell.general/15366 Atom: Hardware description in Haskell. Tom Hawkins [5]announced Atom, a high-level hardware description language embedded in Haskell that compiles conditional term rewriting systems into conventional HDL. 5. http://article.gmane.org/gmane.comp.lang.haskell.general/15341 Catch. Neil Mitchell [6]announced a pattern-match checker for Haskell, named Catch. Do you sometimes encounter the dreaded 'pattern match failure: head' message? Do you have incomplete patterns which sometimes fail? Do you have incomplete patterns which you know don't fail, but still get compiler warnings about them? Would you like to statically ensure the absence of all calls to error? This is what Catch helps ... catch! 6. http://article.gmane.org/gmane.comp.lang.haskell.general/15334 Haskell Communities and Activities Report. Andres Loeh [7]announced that the Haskell Communities and Activities Report is now available, covering the increasingly diverse groups, projects and individuals working on, with, or inspired by Haskell. 7. http://article.gmane.org/gmane.comp.lang.haskell.general/15302 The Reduceron. Matthew Naylor [8]announced the Reduceron, a processor for executing Haskell programs on FPGA with the aim of exploring how custom architectural features can improve the speed in which Haskell functions are evaluated. Being described entirely in Haskell (using Lava), the Reduceron also serves as an interesting application of functional languages to the design of complex control circuits such as processors. 8. http://article.gmane.org/gmane.comp.lang.haskell.general/15301 Data.Derive. Neil Mitchell [9]announced Data.Derive, a library and a tool for deriving instances for Haskell programs. It is designed to work with custom derivations, SYB and Template Haskell mechanisms. The tool requires GHC, but the generated code is portable to all compilers. We see this tool as a competitor to DrIFT. 9. http://article.gmane.org/gmane.comp.lang.haskell.general/15292 Piffle, a packet filter language. Jaap Weel [10]announced Piffle, a compiler for a packet filter language in Haskell: a good example of how Haskell can be used in an application domain (low level computer networking) where people tend to use C for everything, including writing compilers. 10. http://article.gmane.org/gmane.comp.lang.haskell.general/15290 Towards a Programming Language Nirvana. Simon Peyton-Jones [11]appears on video, talking about the Haskell path to programming language Nirvana 11. http://channel9.msdn.com/showpost.aspx?postid=326762 Yi 0.2. Jean-Philippe Bernardy [12]announced the 0.2.0 release of the Yi editor. Yi is a text editor written and extensible in Haskell. The goal of Yi is to provide a flexible, powerful and correct editor core dynamically scriptable in Haskell. Yi si also a Haskell interpreter, very much like emacs is a Lisp interpreter, this makes really easy to dynamically hack, experiment and modify Yi. All tools and goodies written in haskell are also readily available from the editor. This is implemented by binding to the GHC API. 12. http://article.gmane.org/gmane.comp.lang.haskell.general/15260 Foreign.AppleScript. Wouter Swierstra [13]announced a library for compiling and executing AppleScript from Haskell. AppleScript is a scripting language available on all modern Apple computers. It can be used to script most applications on running on MacOS X. 13. http://article.gmane.org/gmane.comp.lang.haskell.general/15246 Asterisk Gateway Interface. Jeremy Shaw [14]uploaded a simple AGI interface to [15]hackage. For more about Asterix, see [16]here. 14. http://article.gmane.org/gmane.comp.lang.haskell.general/15245 15. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AGI 16. http://www.voip-info.org/wiki-Asterisk+AGI Harpy. Dirk Kleeblatt [17]announced Harpy, a library for run-time code generation of x86 machine code. It provides not only a low level interface to code generation operations, but also a convenient domain specific language for machine code fragments, a collection of code generation combinators and a disassembler. [18]Lennart Augustsson has written a series of articles demonstrating its use for fast EDSLs. 17. http://article.gmane.org/gmane.comp.lang.haskell.general/15237 18. http://haskell.org/haskellwiki/Blog_articles/EDSLs Yaml Reference. Gaal Yahas [19]announced a Haskell (Cabal) package containing the YAML spec productions wrapped in Haskell magic to convert them to an executable parser. The parser is streaming. It isn't intended to serve as a basis for a YAML tool chain; instead it is meant to serve as a reference implementation of the spec. 19. http://ben-kiki.org/oren/YamlReference/ Haskell' This section covers the [20]Haskell' standardisation process. * [21]Dependent types * [22]Monomorphism restriction * [23]Operator backquoting * [24]Type signatures in export lists * [25]Pragma syntax * [26]inits is too strict * [27]Module system initialisation * [28]Polymorphic strict fields 20. http://hackage.haskell.org/trac/haskell-prime 21. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2282 22. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2262 23. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2247 24. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2240 25. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2238 26. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2232 27. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2212 28. http://thread.gmane.org/gmane.comp.lang.haskell.prime/2192 Libraries This week's proposals and extensions to the [29]standard libraries. * [30]Add exeExtension to System.Info * [31]The drive functions in the filepath package * [32]Optimising words * [33]Add dropPrefix 29. http://haskell.org/haskellwiki/Library_submissions 30. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/7155 31. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/7129 32. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/7094 33. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/7032 Hackage This week's new libraries in [34]the Hackage library database. 34. http://hackage.haskell.org/ * HsOpenSSL-0.1. Masatake Daimon [35]HsOpenSSL 0.1, OpenSSL binding for Haskell 35. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HsOpenSSL-0.1 * Emping-0.3. Hans Van Thiel [36]Emping derives heuristic rules from nominal data 36. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Emping-0.3 * parsely-0.1. Samuel Bronson [37]parsely, Typeclasses for parsing monads, and some instances 37. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/parsely-0.1 * sessions-2007.7.15. Matthew Sackman [38]sessions, Session Types for Haskell 38. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/sessions-2007.7.… * CC-delcont-0.1. Dan Doel [39]CC-delcont1, An implementation of multi-prompt delimited continuations 39. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/CC-delcont-0.1 * gd-3000.3.0. Bjorn Bringert [40]gd, A binding to the GD graphics library 40. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/gd-3000.3.0 * StrategyLib-4.0.0.0. Samuel Bronson [41]StrategyLib, Strafunski's StrategyLib 41. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/StrategyLib-4.0.… * ports-0.4.3.2. Don Stewart [42]ports, concurrent and distributed Haskell programming in the IO monad without relying on mutable variables. 42. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ports-0.4.3.2 * Finance-Quote-Yahoo-0.1. Brad Clawsie [43]Yahoo-0.1, Obtain quote data from finance.yahoo.com 43. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Finance-Quote-Ya… * logict-0.2. Dan Doel [44]LogicT, A continuation-based, backtracking, logic programming monad. 44. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/logict-0.2.1 * utf8-string-0.1. Eric Mertens [45]utf8-string, Support for reading and writing UTF8 Strings 45. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/utf8-string-0.1 * type-int-0.4. Edward Kmett [46]type-int, Type level 2s- and 16s- complement Integers (positive and negative), Booleans, Ord and Eq 46. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/type-int-0.4 * cgi-3001.1.5. BjornBringert [47]cgi-3001, a Haskell library for writing CGI programs 47. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/cgi-3001.1.5 * xmobar-0.6. AndreaRossato [48]xmobar, Xmobar is a minimal status bar for the XMonad Window Manager 48. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/xmobar-0.6 * monad-param-0.0.2. EdwardKmett [49]monad-param, parameterized monads 49. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/monad-param-0.0.2 * dfsbuild-1.0.1. JohnGoerzen [50]dfsbuild, dfsbuild is the program used to create the Debian From Scratch CD image. 50. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dfsbuild-1.0.1 Conference roundup AngloHaskell is [51]coming up in Cambridge, August 10-11 Haskell Hackathon 07 II. Hac07 is [52]coming up in Freiburg, Oct 5-7 51. http://haskell.org/haskellwiki/AngloHaskell 52. http://article.gmane.org/gmane.comp.lang.haskell.general/15416 Blog noise [53]Haskell news from the [54]blogosphere. There really has been 100 new articles since the last issue! 53. http://planet.haskell.org/ 54. http://haskell.org/haskellwiki/Blog_articles * [55]ONLamp: An Introduction to Haskell * [56]ONLamp: An Introduction to Haskell: Part 2: Pure Functions * [57]Knuth-Morris-Pratt in Haskell * [58]Towards Better Error Handling * [59]Dynamic epsilons in Haskell with a bit of type hackery * [60]Null pointers vs None vs Maybe * [61]Lambda calculus in alligator form * [62]Learning Haskell databases * [63]liskell.org * [64]Norvig's spell checker and idiomatic Haskell * [65]Trying out functional programming * [66]Trying out functional programming: part 2 * [67]Roll Your Own Window Manager: Tracking Focus with a Zipper * [68]You Lazy Thunk! * [69]What's a monad? * [70]Erlang: how syntax can discourage good programming practices * [71]Regular expressions in Haskell * [72]Producing diagrams * [73]Notes on Chapter 2 of SOE * [74]Xmonad and KDE on kubuntu feisty * [75]Does XMonad crash? On proving pattern coverage with Catch 55. http://www.onlamp.com/pub/a/onlamp/2007/05/21/an-introduction-to-haskell---… 56. http://www.onlamp.com/pub/a/onlamp/2007/07/12/introduction-to-haskell-pure-… 57. http://twan.home.fmf.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell.details 58. http://nominolo.blogspot.com/2007/05/towards-better-error-handling.html 59. http://augustss.blogspot.com/2007/05/i-was-asked-if-my-fixed-number-module.… 60. http://lukeplant.me.uk/blog.php?id=1107301659 61. http://worrydream.com/AlligatorEggs/ 62. http://davblog48.blogspot.com/2007/05/trying-to-learn-haskell-database.html 63. http://liskell.org/ 64. http://www.serpentine.com/blog/2007/05/14/norvigs-spell-checker-and-idiomat… 65. http://concise-software.blogspot.com/2007/05/trying-out-functional-programm… 66. http://concise-software.blogspot.com/2007/05/trying-out-functional-programm… 67. http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17#xmonad_part1b_zipper 68. http://blog.tmorris.net/you-lazy-thunk/ 69. http://unenterprise.blogspot.com/2007/05/whats-monad.html 70. http://www.acooke.org/cute/ErlangsSyn0.html 71. http://michaelspeer.blogspot.com/2007/05/initial-code-at-regular-expression… 72. http://pozorvlak.livejournal.com/55568.html 73. http://osfameron.vox.com/library/post/notes-on-chapter-2-of-soe.html 74. http://totherme.livejournal.com/4154.html 75. http://neilmitchell.blogspot.com/2007/05/does-xmonad-crash.html * [76]A simple echo server * [77]More deforestation * [78]State of the computer book market * [79]Pragmatic Haskell * [80]Analysing Haskell book sales * [81]Real-world Haskell: it's time * [82]Real-World Haskell * [83]Tim O'Reilly: Real World Haskell title under development * [84]Haskell: Ready for Prime Time * [85]Haskell's time has come * [86]Haskell Book in the Making! * [87]Finally, a book on how Haskell can be applied to 'real-world' problems! * [88]Haskell - Ready for the mainstream? * [89]Great news in the Haskell Books front * [90]Practical reasons for learning some functional languages * [91]Preconditions on XMonad * [92]Xmonad does status bars right by not doing them at all * [93]Perfect Programming Languages: Part 1, Syntactic Similarity * [94]Haskell diary, day 1 * [95]A functional programmer stole my job 76. http://abstractabsurd.blogspot.com/2007/05/couple-of-silly-examples.html 77. http://neilmitchell.blogspot.com/2007/05/13-faster-than-ghc.html 78. http://radar.oreilly.com/archives/2007/05/state_of_the_co_10.html 79. http://blogs.nubgames.com/code/?p=23 80. http://notes-on-haskell.blogspot.com/2007/05/analyzing-book-sales.html 81. http://www.realworldhaskell.org/blog/2007/05/23/real-world-haskell-its-time/ 82. http://changelog.complete.org/posts/612-Real-World-Haskell.html 83. http://radar.oreilly.com/archives/2007/05/real_world_hask.html 84. http://notes-on-haskell.blogspot.com/2007/05/haskell-ready-for-prime-time.h… 85. http://telematique.typepad.com/twf/2007/05/haskells_time_h.html 86. http://triple.aeoth.net/2007/05/25/haskell-book-in-the-making/ 87. http://binil.wordpress.com/2007/05/24/finally-a-book-on-how-haskell-can-be-… 88. http://blog.uncommons.org/?p=23 89. http://codemiscellany.blogspot.com/2007/05/great-news-in-haskell-books-fron… 90. http://kevinoncode.blogspot.com/2007/05/functional-languages-on-horizon.html 91. http://neilmitchell.blogspot.com/2007/05/preconditions-on-xmonad.html 92. http://gimbo.org.uk/blog/2007/05/30/xmonad-does-status-bars-right/ 93. http://disparatemathematician.blogspot.com/2007/05/perfect-programming-lang… 94. http://firstian.blogspot.com/2007/05/haskell-diary-day-1.html 95. http://ocamlnews.blogspot.com/2007/05/functional-programmer-stole-my-job.ht… * [96]Haskell incarnate: robots and Haskell * [97]Chapter 3 of SOE * [98]Implementing Network.HTTP with ByteStrings * [99]Signal handling in Haskell * [100]ML, Haskell and Coq * [101]Djinn, Coq, Monad and a bit of Haskell * [102]A beginner with Parsec * [103]A perceptron in Haskell * [104]Piffle: a packet filter language with a compiler written in Haskell * [105]OriDSEL: a DSL for origami * [106]Joel's compiler in OCaml and Haskell * [107]JGraph in Haskell * [108]A neural network in Haskell * [109]Scientific.Dimension: Type Arithmetic and Physical Units in Haskell * [110]Flattening an array of arrays * [111]Travelling Salesman Problem: Introduction (in Haskell) * [112]Parallel programming, functional vs. imperative languages * [113]The impossible is only possible sometimes * [114]More Scheming with Haskell * [115]How to write tolerably efficient optimzation code without really trying... 96. http://sigfpe.blogspot.com/2007/05/haskell-incarnate.html 97. http://osfameron.vox.com/library/post/chapter-3-soe.html 98. http://nominolo.blogspot.com/2007/05/networkhttp-bytestrings.html 99. http://therning.org/magnus/archives/285 100. http://www.rubrication.net/2007/04/21/how-a-real-module-system-should-work/ 101. http://www.alpheccar.org/en/posts/show/70 102. http://davblog48.blogspot.com/2007/05/parsec.html 103. http://jpmoresmau.blogspot.com/2007/05/perceptron-in-haskell.html 104. http://usr-share-morlock.blogspot.com/2007/05/piffle-packet-filter-language… 105. http://www.gaetanocaruana.com/2007/05/25/embedding-origami-constructs/ 106. http://wagerlabs.com/2007/5/26/who-let-the-dogs-out 107. http://equi-nox.blogspot.com/2007/05/jgraph-in-haskell.html 108. http://jpmoresmau.blogspot.com/2007/06/very-dumb-neural-network-in-haskell.… 109. http://liftm.wordpress.com/2007/06/03/scientificdimension-type-arithmetic-a… 110. http://julipedia.blogspot.com/2007/06/flattening-array-of-arrays.html 111. http://illicittech.blogspot.com/2007/06/travelling-salesman-problem.html 112. http://enfranchisedmind.com/blog/archive/2007/06/10/251 113. http://michaelspeer.blogspot.com/2007/06/impossible-is-only-possible-someti… 114. http://sami.samhuri.net/2007/6/14/more-scheming-with-haskell 115. http://sigfpe.blogspot.com/2007/06/how-to-write-tolerably-efficient.html * [116]Harpy: generating machine code from a Haskell * [117]A little DSL embedded in Haskell * [118]Generating more code with Harpy * [119]Representing DSL expressions in Haskell * [120]Disassembly * [121]A simple embedded compiler in Haskell * [122]Functional composition * [123]Beautiful Haskell implementation of a power set * [124]Constructability, Uncountability, and w-Haskell * [125]Uncountable Ordinals, part 2 * [126]Category Theory and Haskell 3 : Algebras and Monads * [127]The Supermarket Pricing Kata in Haskell * [128]Implementing a type for partial values * [129]Appreciating Constraint Programming * [130]Continuing with continuations in Haskell * [131]Find the Bug * [132]Haskell decision making * [133]Learning Haskell and Number Theory: The End of GCD * [134]A foray into number theory with Haskell * [135]Flatten Benchmark for Haskell 116. http://augustss.blogspot.com/2007/06/playing-with-harpy-recently-there-was.… 117. http://augustss.blogspot.com/2007/06/massive-overload-in-my-last-post-i-had… 118. http://augustss.blogspot.com/2007/06/generating-more-code-with-harpy-after.… 119. http://augustss.blogspot.com/2007/06/representing-dsl-expressions-in-haskel… 120. http://augustss.blogspot.com/2007/06/disassembly-harpy-package-also-contain… 121. http://augustss.blogspot.com/2007/06/simple-compiler-in-my-last-post-i.html 122. http://neilmitchell.blogspot.com/2007/06/functional-composition.html 123. http://community.livejournal.com/evan_tech/220036.html 124. http://blog.jbapple.com/2007/06/constructability-uncountability-and.html 125. http://blog.jbapple.com/2007/06/ordinals-part-2.html 126. http://www.alpheccar.org/en/posts/show/77 127. http://blog.moertel.com/articles/2006/04/28/the-supermarket-pricing-kata-in… 128. http://conal-elliott.blogspot.com/2007/07/implementing-type-for-partial-val… 129. http://boriken.frayser.org/wordpress/2007/07/04/appreciating-chr-constraint… 130. http://therning.org/magnus/archives/306 131. http://cdsmith.wordpress.com/2007/07/05/find-the-bug/ 132. http://realfiction.net/?q=node/123 133. http://cdsmith.wordpress.com/2007/07/05/learning-haskell-and-number-theory-… 134. http://www.akalin.cx/2007/07/06/a-foray-into-number-theory-with-haskell/ 135. http://notvincenz.blogspot.com/2007/07/flatten-benchmark.html * [136]Solving an arithmetic puzzle with Haskell * [137]Haskell DataPipe * [138]Refining my first steps with Parsec * [139]Equational Reasoning in Haskell * [140]Peano's Axioms Part I: Haskell and Type Theory, and Object Oriented Programming * [141]Making Haskell faster than C! * [142]Power serious: power series in ten one-liners * [143]Haskell for Programmers: a tutorial * [144]Parameterized Monads in Haskell * [145]Monomorphism and the unintentional fib * [146]Cohatoe - Contributing Haskell to Eclipse * [147]Getting started with HUnit * [148]A Neat Problem * [149]Parsing, CFGs, and Type Hacking * [150]Using haskell for reading raw ethernet frames * [151]A simple Haskell malware: X11 keylogger * [152]I'll have a Buchburger with fries: solving XKCD's menu puzzle 136. http://byorgey.wordpress.com/2007/06/21/solving-an-arithmetic-puzzle-with-h… 137. http://emilliken.blogspot.com/2007/07/haskell-datapipe.html 138. http://lstephen.wordpress.com/2007/06/22/refining-my-first-steps-with-parse… 139. http://neilmitchell.blogspot.com/2007/07/equational-reasoning-in-haskell.ht… 140. http://disparatemathematician.blogspot.com/2007/07/peanos-axioms-part-i-has… 141. http://neilmitchell.blogspot.com/2007/07/making-haskell-faster-than-c.html 142. http://www.cs.dartmouth.edu/~doug/powser.html 143. http://neugierig.org/software/darcs/haskell-for-programmers/haskell-for-pro… 144. http://comonad.com/reader/2007/parameterized-monads-in-haskell/ 145. http://koweycode.blogspot.com/2007/07/monomorphism-and-unintentional-fib.ht… 146. http://leiffrenzel.de/eclipse/cohatoe/ 147. http://leiffrenzel.de/papers/getting-started-with-hunit.html 148. http://cdsmith.wordpress.com/2007/07/17/a-neat-problem/ 149. http://cdsmith.wordpress.com/2007/07/19/parsing-cfgs-and-type-hacking/ 150. http://emilliken.blogspot.com/2007/07/using-haskell-for-reading-raw-etherne… 151. http://emilliken.blogspot.com/2007/07/simple-haskell-malware-x11-keylogger.… 152. http://sigfpe.blogspot.com/2007/07/ill-have-buchburger-with-fries.html Quotes of the Week * Smith's Law: Any sufficiently large test suite for a program written in a dynamic language will contain an ad-hoc, informally-specified, bug-ridden, slow, patchy implementation of half of the Haskell type system * pshaw: I think the key hook that allowed me to pass interview #2 was that I put the word 'Haskell' on my resume. * monochrom: Fear leads to uncertainty. Uncertainty leads to doubt. Doubt leads to theorem proving. * Adam Turoff: Let me start by being perfectly clear: if you are a professional programmer, then Haskell is in your future. * Apfelmus: In the end, I think that strong types is only one thing that makes Haskell programs work after compilation. The other ones are higher-order functions and *purity*. No type system can achieve what purity offers. About the Haskell Weekly News Each week, new editions are posted to [153]the Haskell mailing list as well as to [154]the Haskell Sequence and [155]Planet Haskell. [156]RSS is also available, and headlines appear on [157]haskell.org. Headlines are available as [158]PDF. To help create new editions of this newsletter, please see the [159]contributing information. Send stories to dons at cse.unsw.edu.au. The darcs repository is available at darcs get [160]http://www.cse.unsw.edu.au/~dons/code/hwn 153. http://www.haskell.org/mailman/listinfo/haskell 154. http://sequence.complete.org/ 155. http://planet.haskell.org/ 156. http://sequence.complete.org/node/feed 157. http://haskell.org/ 158. http://www.cse.unsw.edu.au/~dons/code/hwn/archives/20070723.pdf 159. http://haskell.org/haskellwiki/HWN 160. http://www.cse.unsw.edu.au/~dons/code/hwn

1 0

Speedy parsing
by Re, Joseph (IT) 23 Jul '07

23 Jul '07

I was hoping someone could direct me to material on how I might go about optimizing a small parsing program I wrote. Used for calculating differences between two files that store a hash of hashes (each line is a hash, each line has "key=value" pairs seperated by commas), the bottleneck seems to be in getting the data into memory (in a usable structure) quickly, as I'm working with extremely large files (>250,000 line, 100MB+ files are normal in size, some are quite larger, and I have to process a large number of them often). Extracting just the parsing elements of my current python implementation: FILE: compare.py > import sys > def parse(lines): > print "Parsing",len(lines),"lines..." > failed = 0 > hashes = {} > for line in lines: > try: > hash = {} > parts = line.split(",") > for part in parts: > k,v = part.split("=") > hash[k] = v > hashes[ hash["LogOffset"] ] = hash > except: > if line != "": > failed += 1 > if failed > 0: > print "[ERROR] Failed to parse:",failed,"lines" > print "...Parsing resulted in",len(hashes),"unique hashes" > return hashes > > def normalize(lines): > lineset = set() > for line in lines: > if "Type=Heartbeat" == line[0:14]: pass > elif line == "": pass > else: lineset.add( line ) #use set to get only uniques > return lineset > > def main(): > hashes = parse( normalize ( open(sys.argv[1]).readlines() )) > > if __name__ == '__main__': main() $ time python compare.py 38807lineFile Removed 52 bad lines Parsing 38807 lines... ...Parsing resulted in 38807 unique hashes real 0m3.807s user 0m3.330s sys 0m0.470s $ time python compare.py 255919lineFile Removed 0 bad lines Parsing 255919 lines... ...Parsing resulted in 255868 unique hashes real 0m30.889s user 0m23.970s sys 0m2.900s *note: profiling shows over 7.1 million calls to the split() function, to give you a good idea of the number of pairs the file contains. Once you factor in much increased filesizes, actually preforming the analysis, and running it on a few dozen files, my tests started to become quite time consuming (not to mention it takes 1GB of memory for just the 250K line files, although execution time is still much more important at the moment thanks to ram being cheap). Thusly, I figured I'd rewrite it in C, but first I wanted to give Haskell a shot, if only to see how it compared to python (hoping maybe I could convince my boss to let me use it more often if the results were good). The first thing I wanted to check was if parsec was a viable option. Without even putting the data into lists/maps, I found it too slow. FILE: compare_parsec.hs > {-# OPTIONS_GHC -O2 #-} > module Main where > import System.Environment (getArgs) > import Text.ParserCombinators.Parsec > > csv = do x <- record `sepEndBy` many1 (oneOf "\n") > eof > return x > record = field `sepBy` char ',' > field = many (anyToken) > > main = do > ~[filename] <- getArgs > putStrLn "Parsing log..." > res <- parseFromFile csv filename > case res of > Left err -> print err > Right xs -> putStrLn "...Success" $ time ./compare_parsec 38807lineFile Parsing log... ...Success real 0m13.809s user 0m11.560s sys 0m2.180s $ time ./compare_parsec 255919lineFile Parsing log... ...Success real 1m28.983s user 1m8.480s sys 0m9.530s This, sadly, is significantly worse than the python code above. Perhaps someone here can offer advice on more efficient use of parsec? Unfortunately I don't have profiling libraries for parsec available on this machine, nor have I had any luck finding material on the web. After this, I tried doing my own parsing, since the format is strict and regular. I tried pushing it to lists (fast, not very usable) and maps (much easier for the analysis stage and what the python code does, but much worse speedwise). FILE: compare_lists.hs > {-# OPTIONS_GHC -O2 -fglasgow-exts #-} > module Main where > import System.Environment (getArgs) > type Field = (String,String) > type Record = [Field] > type Log = [Record] > > main = do > ~[filename1] <- getArgs > file1 <- readFile filename1 > putStrLn "Parsing file1..." > let data1 = parseLog file1 > print data1 > putStrLn "...Done" > > -- parse file > parseLog :: String -> Log > parseLog log = foldr f [] (lines log) > where f "" a = a > f "\n" a = a > f x a = (parseRecord x):a > -- parse record > parseRecord :: String -> Record > parseRecord record = foldr (\x a -> (parseField x):a) [] (split ',' record) > -- parse field > -- no error detection/handling now > parseField :: String -> Field > parseField s = (takeWhile isntCharEq s, tail $ dropWhile isntCharEq s) > > isntCharEq :: Char -> Bool > isntCharEq '=' = False > isntCharEq _ = True > > split :: Eq a => a -> [a] -> [[a]] > split delim = foldr f [[]] > where > f x rest@(r:rs) > | x == delim = [] : rest > | otherwise = (x:r) : rs I wasn't sure the best way to force evaluation on this, so I opt'd to print it and direct stdout to /dev/null (and noted how long a program that just read and print the same file to /dev/null took as well). Any better suggestions are welcome. $ time ./compare_lists 38807lineFile > /dev/null real 0m4.958s (0m0.445s for the putStrLn $ readFile program) user 0m4.830s sys 0m0.110s $ time ./compare_lists 255919lineFile > /dev/null real 0m31.047s (0m2.620s for the putStrLn $ readFile program) user 0m30.310s sys 0m0.690s These speeds are relatively the same as python, but the data is easily usable in comparision, so finally I implemented the useful version: FILE: compare_maps.hs > {-# OPTIONS_GHC -O2 -fglasgow-exts #-} > module Main where > import qualified Data.Map as Map > import System.Environment (getArgs) > import Control.Monad > > type Field = (String,String) > type Record = Map.Map String String > type Log = Map.Map String Record > > main = do > ~[filename] <- getArgs > d <- liftM parseLog $ readFile filename > putStr $ strMaps d > -- parse file > parseLog :: String -> Log > parseLog logstr = foldr f Map.empty (lines logstr) > where f "" a = a > f "\n" a = a > f x a = let (k,v) = parseRecord1 x > in Map.insert k v a > -- parse record line > parseRecord1 :: String -> (String,Record) > parseRecord1 recordstr = do let r = parseRecord recordstr > (idRecord r, r) > > -- extract unique id used for comparision amoungst line hashes in other files > idRecord :: Record -> String > idRecord r = case (Map.lookup "LogID" r) of > Nothing -> "ERROR" > Just id -> id > > parseRecord :: String -> Record > parseRecord recordstr = foldr f Map.empty (split ',' recordstr) > where f x a = case parseField x of > Nothing -> a > Just (k,v) -> Map.insert k v a > -- parse k=v fields > parseField :: String -> Maybe Field > parseField "" = Nothing > parseField s = Just (takeWhile isntCharEq s, tail $ dropWhile isntCharEq s) > > isntCharEq :: Char -> Bool > isntCharEq '=' = False > isntCharEq _ = True > -- map functions > strMaps = Map.fold (\x a -> (strMap x) ++ "\n" ++ a) "" > strMap = unlines . map (\(k,v) -> k ++ ":" ++ v) . Map.toAscList > -- list functions > split :: Eq a => a -> [a] -> [[a]] > split delim = foldr f [[]] > where > f x rest@(r:rs) > | x == delim = [] : rest > | otherwise = (x:r) : rs $ time ./compare_maps 38807lineFile > /dev/null real 0m24.207s (0m0.445s for the putStrLn $ readFile program) user 0m22.430s sys 0m1.680s $ time ./compare_maps 255919lineFile > /dev/null real 5m24.927s (0m2.620s for the putStrLn $ readFile program) user 5m5.240s sys 0m12.770s Until this point I had only been throwing on -O2. I believe -fvia-C is included with -O currently, and I'm not well versed enough to know what others could help me out, so I left it at that. Next I tried checking out what the garbage collector was doing (I assume the footprint is smaller than python, but that would still be quite large). Flipping on -Sstderr I saw that only a third of the time spent was doing real work (67.9% doing GC). For the 38K file: 2,794,465,788 bytes allocated in the heap 1,956,668,360 bytes copied during GC (scavenged) 21,884,948 bytes copied during GC (not scavenged) 185,541,764 bytes maximum residency (16 sample(s)) 5329 collections in generation 0 ( 9.03s) 16 collections in generation 1 ( 5.99s) 523 Mb total memory in use MUT time 7.10s ( 7.80s elapsed) GC time 15.02s ( 16.68s elapsed) Total time 22.12s ( 24.48s elapsed) %GC time 67.9% (68.1% elapsed) For the 250K file: 17,509,820,952 bytes allocated in the heap 12,270,870,276 bytes copied during GC (scavenged) 136,831,020 bytes copied during GC (not scavenged) 1,307,822,788 bytes maximum residency (21 sample(s)) 33390 collections in generation 0 (121.65s) 21 collections in generation 1 ( 42.37s) 3244 Mb total memory in use MUT time 146.25s (151.51s elapsed) GC time 164.02s (172.73s elapsed) Total time 310.27s (324.24s elapsed) %GC time 52.9% (53.3% elapsed) Not being paticularly knowledgeable in this area, I tried some options I thought were reasonable after reading the (http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control .html#rts-options-gc). The following are with the small (38K) file. Running with a larger heap (-H) didn't seem to help: 256m 35s 512m 37s 768m 37s 1g 29s Playing with the allocation area size (-A) didn't help either: 128k 29s 256k 25s (default) 512k 23s 768k 25s 1m 23s 2m 32s 5m 32s 10m 32s The 250K file shows improvement from the little bit I've played around with defaults -> 5m24s, 33.3K collections, 53% GC time -H1g -> 4m53s, 16.8K collecctions, 56% GC time -H3g -A5m -> 4m16s total time, 3500 collections, 52% GC time -H4g -A50m -> 4m26s total time, 350 collections, 57% GC time (-H3g -A5m and -H4g -A50m give approx. 4m16s total time, 3500 collections, but still 52% GC time), so I'll try to run some more tests with different options for it, but this still isn't even remotely close to python's speed, so I assume improving the code would prove more fruitful. At this point I'm out of ideas, so I was hoping someone could identify something stupid I've done (I'm still novice of FP in general, let alone for high performance) or direct me to a guide,website,paper,library, or some other form of help. For reference, the tests above were done on an 8 proc (possibly 4 real but hyperthreaded?) 2.8ghz Xeon workstation with 16gb memory runing an SMP enabled 2.4.21-47 linux kernel and ghc 6.6.1 Thanks -- Joseph Re -------------------------------------------------------- NOTICE: If received in error, please destroy and notify sender. Sender does not intend to waive confidentiality or privilege. Use of this email is prohibited when received in error.

5 7

Ray tracer
by Andrew Coppin 23 Jul '07

23 Jul '07

The "Haskell ray tracer" seems to be a pretty standard and widely-used example program. But has anybody ever seriously tried to make a "production-grade" implementation? (I.e., one that is user-friendly, efficient, and with lots of functionallity.)

7 14

Help with IO and randomR
by Niko Korhonen 23 Jul '07

23 Jul '07

I'm writing some code to generate a dither (=noise) signal. I'm trying to generate an infinite series of noise with triangular distribution but my code hangs into an infinite loop. The problem is that I'm not very good with Haskell IO yet and I can't figure out how to write this piece of IO code without it looping infinitely. So, in short, how do I do this without getting into an infinite loop: tpdfs :: (Int, Int) -> IO [Int] tpdfs (low, high) = do first <- getStdRandom (randomR (low, high)) second <- getStdRandom (randomR (low, high)) let r = (first + second) `div` 2 rest <- tpdfs (low, high) return (r : rest) Caller site: do nums <- tpdfs (2, 12) let ns = take 7 nums Niko

4 6

Re: Re[4]: [Haskell-cafe] Newbie question about tuples
by Peter Verswyvelen 22 Jul '07

22 Jul '07

Thanks Bulat, but now you scattered my hopes that GHC would magically do all these optimizations for me ;-) I must say that although the performance of Haskell is not really a concern to me, I was a bit disappointed that even with all the tricks of the state monad, unboxing, and no-bounds-check, the matrix-vector multiplication was still 7 to 8 times slower than the C version. And at the end of the paper, it's only a factor 4 slower. Okay, going from 300x slower to 4x slower is impressive, but why is it *still* 4x slower? It would be interesting to compare the assembly code generated by the C compiler versus the GHC compiler; after all, we're just talking about a vector/matrix multiplication, which is just a couple of lines of assembly code... And now I'm again talking about performance, nooo! ;-) >http://www.cse.unsw.edu.au/~chak/papers/afp-arrays.ps.gz

3 8

[OT] Install ghc6-doc fails
by J. Pablo Fernández 22 Jul '07

22 Jul '07

Hello, This may be a bit off topic, but maybe someone here has importante related information. I am running Kubuntu, the lattests stable version, but I am running unstable Haskell packages, that is, I fetch the dsc, diff and tarballs and build the debs myself of what will come in the next version of Kubuntu. So I have the advantage of running recent versions, and at the same time, keeping packages (which come usefull when I want to remove everything, or when mainstream software is too weird). But, installing the ghc6-doc packages gives me this error: (Reading database ... 156024 files and directories currently installed.) Preparing to replace ghc6-doc 6.6.1-2 (using ghc6-doc_6.6.1-2_all.deb) ... Unpacking replacement ghc6-doc ... Setting up ghc6-doc (6.6.1-2) ... haddock: Warning: The interface file "base/base.haddock" could not be read. Maybe it's from a later version of Haddock? haddock: Warning: The interface file "Cabal/Cabal.haddock" could not be read. Maybe it's from a later version of Haddock? haddock: Warning: The interface file "filepath/filepath.haddock" could not be read. Maybe it's from a later version of Haddock? haddock: Warning: The interface file "parsec/parsec.haddock" could not be read. Maybe it's from a later version of Haddock? haddock: Warning: The interface file "readline/readline.haddock" could not be read. Maybe it's from a later version of Haddock? haddock: Warning: The interface file "regex-base/regex-base.haddock" could not be read. Maybe it's from a later version of Haddock? haddock: Warning: The interface file "regex-compat/regex-compat.haddock" could not be read. Maybe it's from a later version of Haddock? haddock: Warning: The interface file "regex-posix/regex-posix.haddock" could not be read. Maybe it's from a later version of Haddock? haddock: Data.Binary.getWord8: end of file dpkg: error processing ghc6-doc (--install): subprocess post-installation script returned error exit status 1 Errors were encountered while processing: ghc6-doc I am running the lattest haddock (0.8), so the problem might be something else. Any ideas what the problem might be? Thank you. -- J. Pablo Fernández <pupeno(a)pupeno.com> (http://pupeno.com)

1 1

Re: [Haskell-cafe] Haskell & monads for newbies
by Andrew Coppin 22 Jul '07

22 Jul '07

Peter Verswyvelen wrote: > Ouch, I should not have brought up these monads again! I should have known better ;-) > Mmm... ;-) > I hope the Haskell community understands that for outsiders / newbies who want to learn or just look at Haskell and then do some Googling, all this monad talk looks a bit euh "strange"? Yeah. I spent time on another forum trying to explain Haskell. I wrote a fifty-mile long post that's basically a complete beginner's introduction to the language. Every reply was of the form "wow, did you write all that yourself? That's really good! You should write stuff for a living... Haskell sounds kinda cool, but... monads look very hard, and basically everything I write programs for is mainly about I/O..." I'm sure others have seen something similar... > Maybe in the next version of Haskell monads should be called something different SPJ suggested "warm fuzzy thing". ;-) > and then all these tutorials and discussions about monads will then be silently forgotten over time ;-) > Oh, I don't know about that... (I for one still haven't figured out how to work monad transformers, for example. And they look useful...)

9 15

how can I call GHC.init and GHC.initPackages?
by Vadim 21 Jul '07

21 Jul '07

Hi all, The following lines of code: import GHC main :: [PackageIdentifier] -> IO () main pkgs = GHC.defaultErrorHandler defaultDynFlags $ do GHC.init (Just GHC_LIBDIR) interactive pkgs seemingly worked in GHC 6.6 but they do not work in 6.6.1 anymore with error message: [1 of 1] Compiling Hide.Hide ( src/Hide/Hide.hs, dist/build/Hide/Hide.o ) src/Hide/Hide.hs:34:9: Not in scope: `GHC.init' src/Hide/Hide.hs:44:18: Not in scope: `GHC.initPackages' ******************** setup build failed for packages/baseApp Thanks for any help on the subject. Vadim.

1 0

gui libs? no thanks, i'm just browsing.. ;-)
by Claus Reinke 21 Jul '07

21 Jul '07

gui libs are wonderful, but haskell sometimes has too few and sometimes has too many. and those we have do not work with every haskell implementation. and when they do work (usually with ghc, these days), they need to be rebuilt whenever ghc is updated, even if the gui lib hasn't changed at all (one gui lib binding per ghc version). still, we put up with that when we need all those gui lib features, because we have to, and we're happy to live in one of those periods when there are such bindings to full-featured gui libraries. but what about quick and dirty/cheap and cheerful graphics? over the years, HGL/SOEGraphics has served as a persistent reminder that things keep changing, and that when they do, something breaks. even if all people want to do is draw some simple graphics, or animations. i don't have a solution, but i'd like to throw another alternative into the ring, based on the ongoing fight between web browsers and other guis for world dominance.. the idea is well known: build your app as a server, and put an ajax-based gui in front of it, even if server and browser run on the same machine. attached is a silly quick&dirty demo of some of the relevant concepts, including a fake haskell http-server, an html/canvas/httprequest/ javascript-based gui, and some simple graphics/buttons/text. tested on windows, with opera 9.01 and ghc 6.6.1. it will probably not work with other browsers, but it should work with opera on other platforms, or with other haskell implementations supporting Network. (you might have to hardcode the file name at the top of the source if not using ghc; to make it work with other browsers, you need workarounds for standard browser incompatibilities) to run, load Canvas.hs into ghci and call main. then start up opera, and visit 'http://localhost:8000/start' (to change that port number, change both 'main' in the haskell source, and 'get' in the html source). that should yield an html page with further instructions. have a look, and please let me know if it works on your os/ haskell implementation, and what you think about the idea. i won't do it myself, but perhaps someone could code up SOEGraphics based on this?-) and if not, this might still help out some of you who need simple low-overhead guis (things can get hairy very quickly if you need more than simple guis)? some of you might have to fight through implementing browser- based guis for their day jobs anyhow, but may want to put haskell behind those guis; or you might find haskell prototyping an easier sell, if the gui can be reused for the "real" implementation.. claus further reading/download: Opera browser (windows, macos, solaris, linux, ..) http://www.opera.com/download/ html 5 -- working draft, june 2007 (3.14.11 canvas element) http://www.whatwg.org/specs/web-apps/current-work/#the-canvas canvas tutorial http://developer.mozilla.org/en/docs/Canvas_tutorial http://developer.mozilla.org/en/docs/Drawing_Graphics_with_Canvas

7 15

Re: Haskell-Cafe Digest, Vol 47, Issue 189
by Kyle L Bittinger 21 Jul '07

21 Jul '07

I wrote a short perl script to convert literate Haskell emails into pdf's. It requires lhs2TeX and pdflatex and might not work on Windows. You can darcs get http://rwf.mit.edu/~kyle/src/lhs-email/ I've tested it on a couple of articles from Oleg's FTP site - the source and pdf output are in the folder above (not checked into darcs). I wrote this in a few hours because I (personally) have trouble reading long articles in fixed-width fonts. I also like to print the longer emails to study offline. BE WARNED that this is written in hacked-up-outofcontrol-line-noise perl, so don't look at the source if that gives you seizures. The script might be tangentially related to this thread: http://thread.gmane.org/gmane.comp.lang.haskell.cafe/18020/focus=18020 --Kyle

1 0

Producing MinimumValue
by Alexteslin 20 Jul '07

20 Jul '07

Hello, I am trying to define a function as part of the exercises that gives a result of a minimum value of the input list of ints. Such as this: minimumValue :: [Int] -> Int minimumValue ns ... using either filter or map functions but Not foldr1, because the exercise precedes the section on foldr1. I am confused because using filter - it generates a list on some constraint function for each element. Any hints will be very appreciated. Thank you -- View this message in context: http://www.nabble.com/Producing-MinimumValue-tf4106379.html#a11677240 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

14 27

List minimum - performance question
by Dusan Kolar 20 Jul '07

20 Jul '07

Hello all, Inspired by exercise on the minimal value of a given list I tried myself produce several versions of such a function: exercise: using just ($), head, filter, null, id, map, (<) without explicit recursion definition direct-forward: direct implementation using forward recursion, if-then-else, (<) direct-backward: direct implementation using backward recursion, if-then-else, (<) foldl: using foldl, lambda abstraction, if-then-else, (<) foldr: using foldr, lambda abstraction, if-then-else, (<) From a recursion point of view, I see a similarity between direct-forward and foldl. Of course, the same similarity is between direct-backward and foldr. Am I right? If yes, then there is something strange in the results I have gained (see below). I did my measurements in winhugs (Version: Sep 2006) for lists of length 10, 100, 1000 and 50 elements. I tested on list with the same constant, list where the first number is minimal (these two cases are from this point of view similar/the same), lists, where some element in the "middle" is minimal, and finally lists, where the last element is the minimal one. As for constant and first minimal element list I got the same result, we can join them and have just three categories of lists, let's call them first, mid, last. Even if I know that using number of reductions and number of cells does not provide exact results, I assume that impact of parameter and printing of the result is the same for all tested functions and is either constant for the result printing (always number 1 in the result) and at most linear in the parameter processing (I would assume no direct impact here, just algorithm influence, is that right?). Thus, the results may be compared. First of all, the time/reduction complexity (n is a length of the list): first mid last exercise 9n+34 <not evaluated> 4.5n^2+21.5n+17 direct-forward 7n+15 7n+15 7n+15 direct-backward 7n+15 7n+15 7n+15 foldl 8n+14 8n+14 8n+14 foldr 8n+14 8n+14 8n+14 There is nothing special on the results, the exercise solution was not evaluated for the middle element lists as the position of the minimal value in the list is a parameter of the function. Now, let me show results for number of used cells: first mid last exercise 10n+54 <not evaluated> 5n^2+29n+26 direct-forward 8n+24 8n+25 9n+23 direct-backward 9n+22 9n+22 9n+22 foldl 11n+22 11n+22 11n+22 foldr 10n+23 10n+23 10n+23 Again, roughly looking at the results, there is nothing special, average space complexity is as it may be expected. Looking at the exact formulas, there are two things that come strange to me: 1) From a recursion point of view, there are pairs direct-forward ~ foldl and direct-backward ~ foldr. Nevertheless, from a space consumption point of view, this doesn't hold and the pairs are swapped. Why? Is this a winhugs specialty? Is this due to reduction strategy? Laziness? 2) Direct-forward implementation provides three different formulas. Why? Why the mid formula is fixed no matter where the minimal value is? Thanks for any answers/hints/references. Especially, if this is RTFM one. ;-) Dusan P.S. I know, that sources may be helpful, but as this is an exercise I don't want to provide them directly to the list. ;-) But I can provide them, of course. :-)

1 0

Maintaining the community
by dons＠cse.unsw.edu.au 20 Jul '07

20 Jul '07

As we sit here riding the Haskell wave: http://www.cse.unsw.edu.au/~dons/tmp/cafe.png with nearly 2000 (!) people reading haskell-cafe@, perhaps its time to think some more about how to build and maintain this lovely Haskell community we have. Just yesterday I received an email: "I posted it to Haskell-Cafe and received loads of brilliant responses. Wow, those guys are awesome. I'm definitely going to learn Haskell now." Which is *exactly* the kind of (view of the) community we want to build and encourage, so we can keep the Haskell project growing into the future. I think the main thing we need to remember is to help train new experts in the community, to be fluent in the culture, ensuring that expertise and a knowledge of the culture diffuses through the new people arriving. That is, to help people progress from newbie, to intermediate, to expert, and thus ensure the culture is maintained (avoiding `Eternal September'). This graphic[1] sums the main issue up nicely, in my view: http://headrush.typepad.com/photos/uncategorized/buildingausercommunity.jpg And the steps to follow (people can think about how best they apply to them) (also from [1]): * Encourage newer users--especially those who've been active askers--to start trying to answer questions We're pretty good with this, but we can be *explicit* about it. If you're taking a lot from the community, please put a lot back in (in terms of writing about it, contributing answers, new libraries, and so on). I note this is also exactly what the Summer of Code helps do too -- we've had several people paid to progress from newbie to expert, thanks to the SoC. * Give tips on how to answer questions Answering politely, and in detail, explaining common misunderstandings is better than one word replies. * Adopt a near-zero-tolerance "Be Nice" policy when people answer questions We are very good here already, both on email and IRC. * Teach and encourage the more advanced users (including moderators) how to correct a wrong answer while maintaining the original answerer's dignity. This is hard, perhaps people can think some more about this. * Re-examine your reward/levels strategy for your community This is also important: on the IRC channel we actually use participation data (http://www.cse.unsw.edu.au/~dons/irc/haskell-07.html) to determine who gets moderator privledges. For the community in general, rewards are along the lines of "going to the hackathon", "becoming the domain expert for some library". Cheers and happy hacking, Don [1]. http://headrush.typepad.com/creating_passionate_users/2006/12/how_to_build_…

45 111

Type hacking help
by Chris Smith 20 Jul '07

20 Jul '07

I've just written my first real piece of type system hacking in Haskell. I think it turned out okay, but if any of you more experienced folk have suggestions, I'd appreciate them. Code follows. More explanation is at http://cdsmith.wordpress.com/2007/07/19/parsing-cfgs-and-type-hacking/ {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE NoMonomorphismRestriction #-} data Var a = Var String data RHS a b = RHS a b (&) = RHS -- a convenient operator infixr 5 & {- (Action a b c) means the following: A production with a right hand side of type: a may be associated with a semantic rule of type: b to produce a rule with semantic result type: c -} class Action a b c | a b -> c, a c -> b instance Action (Var x) (x -> y) y instance Action Char y y instance Action () y y instance (Action a b c) => Action (RHS (Var x) a) (x -> b) c instance (Action a b c) => Action (RHS Char a) b c {- The RuleSet monad is used to define rules of a grammar in a convenient 'do' notation. -} data Rule = forall a b c. (Action a b c) => Rule (Var c, a, b) data RuleSet x = RuleSet ([Rule], x) instance Monad RuleSet where a >>= k = let RuleSet (r1, v1) = a RuleSet (r2, v2) = k v1 in RuleSet (r1 ++ r2, v2) return x = RuleSet ([], x) (==>) :: (Action a b c) => Var c -> a -> b -> RuleSet () (==>) lhs rhs sem = RuleSet ([Rule (lhs, rhs, sem)], ()) infixr 4 ==> {- Grammar. A grammar is a set of rules together with a start symbol. -} data Grammar a = Grammar (Var a) [Rule] grammar s (RuleSet (rs, x)) = Grammar s rs {- Sample grammar. The parentheses in the let bindings are required: they force the rules to be monomorphic, which is needed for type checking to work properly. -} g = let ( expr ) = Var "expression" ( term ) = Var "term" ( termmore ) = Var "term operator" ( fact ) = Var "factor" ( factmore ) = Var "factor operator" ( digit ) = Var "digit" ( digits ) = Var "digits" in grammar expr $ do expr ==> term & termmore $ \x y -> y x termmore ==> () $ \x -> x termmore ==> '+' & term & termmore $ \x y z -> y (x + z) termmore ==> '-' & term & termmore $ \x y z -> y (x - z) term ==> fact & factmore $ \x y -> y x factmore ==> () $ \x -> x factmore ==> '*' & fact & factmore $ \x y z -> y (x * z) factmore ==> '/' & fact & factmore $ \x y z -> y (x / z) fact ==> '(' & expr & ')' $ \x -> x fact ==> digit & digits $ \x y -> y x digits ==> () $ \x -> x digits ==> digit & digits $ \x y z -> y (10*x + z) digit ==> '0' $ 0 digit ==> '1' $ 1 digit ==> '2' $ 2 digit ==> '3' $ 3 digit ==> '4' $ 4 digit ==> '5' $ 5 digit ==> '6' $ 6 digit ==> '7' $ 7 digit ==> '8' $ 8 digit ==> '9' $ 9 Thanks, -- Chris Smith

1 0

Master's thesis project at Philips Research
by Robert van Herk 20 Jul '07

20 Jul '07

At Philips Research (Eindhoven, The Netherlands), we have a Haskell master-thesis project in the context of interactive toys. We are developing a platform for serious toys and games. In this project, we add advanced interactivity based on wireless sensors to traditional toy designs. This can be used to create a whole range of new, revolutionary, exciting toys and games. One of the design goals is that it will be easy for a non-technical person to write applications for the toys and games. For this we are developing a programming language. In this context, we are looking for a student. The project would encompass be the following: - Design and finetune a grammer for this language - Create a parser and compiler for this language - Implement an interpreter to run the compiled code on embedded hardware Some design goals are: - The language should cover the functionality needed to elegantly program the required set of applications - The language should be easily understandable for a non-technical person We are looking for somebody who: - is a master student in Computer Science - has knowledge of language design and compiler design - can write code that runs well on constrained hardware - is a good “team-player” - can express himself well in English Of course, affinity with story designing or toy designing is advantageous. Please contact me by e-mail if you are interested! Regards, Robert --------------------- Robert van Herk Research Scientist, IT Group, Philips Research High Tech Capus 37 (WY) 7.40 Eindhoven The Netherlands

2 1

Is this haskelly enough? -- errm but every answer is wrong(?)
by Anthony Clayden 20 Jul '07

20 Jul '07

(Or at least the problem is under-specified.) 1. There may be several sub-sequences having the maximum sum. So the type for the solution should be :: Num a => [a] -> [[a]] (Note that the problem didn't ask for the maximum itself.) 2. The inits . tails approach adds a fault: It introduces a sprinkling of empty sub-sequences. These have sum zero. So in case the input list is all negative numbers ... Being a software tester for my day job, I looked first not for an elegant and/or efficient solution; but for where to stretch the boundaries of the problem. > However, the key point is that this is a TRICK QUESTION. <snip>

5 4

Time consumption nub
by Arie Groeneveld 20 Jul '07

20 Jul '07

Hi, Wondering about time space consuming: 'nub' vs 'map head.group.sort' Consider: ry = [1..10000] ++ replicate 13 5 ++ replicate 21 34 *Main> length . nub $ ry 10000 (5.18 secs, 1050000 bytes) *Main> length . map head . group . sort $ ry 10000 (0.03 secs, 6293384 bytes) Time space nub --- + fnub +++ - + is better ;-) Thanks @@i=arie

3 4

Stream processors as arrows
by Miguel Mitrofanov 20 Jul '07

20 Jul '07

I'm trying to do Exercise 2.5.2 from John Hughes's "Programming with Arrows". It asks to make the type SP defined as (notation is slightly different) > data SP a b = Inp (a -> SP a b) | Out b (SP a b) an instance of Arrow, ArrowChoice and ArrowLoop. Some parts of it are straightforward, e.g. > arr f = fix $ \sp -> Inp $ \x -> Out (f x) sp Some are a bit tricky; for "first" I ended up with code > first = fix first' > where first' f sp = Inp $ \(x,z) -> let g = firstL x > h = firstR z > in case sp of Inp _ -> (g . h) f sp > Out _ _ -> (h . g) f sp > firstL x f (Inp fsp) = f $ fsp x > firstL x f sp = first' (firstL x f) sp > firstR z f (Out y sp) = Out (y,z) $ f sp > firstR z f sp = first' (firstR z f) sp which is a bit funny. But the real problem I don't know how to deal with is "loop". My first attempt was somethig like this: > loop (Out (y,z) sp) = Out y $ loop' z loop sp > where loop' z f (Inp fsp) = Inp $ \x -> f $ fsp (x,z) > loop' z f (Out (y,z') sp) = Out y $ loop' z' (loop' z f) sp since I thought it's pointless to make a loop that don't do any output. But then I ran into trouble: *StreamProc> process (loop returnA) [1..10] *** Exception: g:/StreamProc.hs:(26,4)-(28,90): Non-exhaustive patterns in function loop So I realized that both arr and first are doing input first and output second, and that causes this error. I've tried to fix this with > loop (Inp fsp) = Inp $ \x -> let Out (y,z) sp = fsp (x,z) in Out y $ loop sp This works as desired: *StreamProc> process (loop returnA) [1..10] [1,2,3,4,5,6,7,8,9,10] But it seems to solve the problem by shifting it one step away from us. I'm not sure this is enough. Any advice/suggestions?

2 2

xkcd #287 "NP-Complete"
by Tom Pledger 20 Jul '07

20 Jul '07

We've seen some nice concise solutions that can deal with the original problem: solve 1505 [215, 275, 335, 355, 420, 580] I'll be a nuisance and bring up this case: solve 150005 [2, 4, 150001] A more scalable solution is to use an explicit heap that brings together all the ways to get to each partial sum. I coded one using Data.Map, but it's a bit long-winded and ugly. Perhaps a purpose-built heap monad would make it more elegant... as long as it could be reused elsewhere. Just musing. :-) - Tom

5 7

historical question about Haskell and Haskell Curry
by Michael Vanier 19 Jul '07

19 Jul '07

We always say that Haskell is named for Haskell Curry because his work provided the logical/computational foundations for the language. How exactly is this the case? Specifically, does anyone claim that Curry's combinatorial logic is more relevant to the theoretical foundations of Haskell than e.g. Church's lambda calculus? If not, why isn't Haskell called "Alonzo"? ;-) Mike

5 5

Clearly, Haskell is ill-founded
by Thomas Conway 19 Jul '07

19 Jul '07

I don't know if you saw the following linked off /. http://www.itwire.com.au/content/view/13339/53/ An amazon link for the book is here: http://www.amazon.com/Computer-Science-Reconsidered-Invocation-Expression/d… The basic claim appears to be that discrete mathematics is a bad foundation for computer science. I suspect the subscribers to this list would beg to disagree. Enjoy, T. -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

19 32

Is this haskelly enough?
by James Hunt 19 Jul '07

19 Jul '07

Hi, As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http://www.rubyquiz.com/quiz131.html) in Haskell. Would someone be kind enough to cast their eye over my code? I get the feeling there's a better way of doing it! subarrays :: [a] -> [[a]] subarrays [] = [[]] subarrays xs = (sa xs) ++ subarrays (tail xs) where sa xs = [ys | n <- [1..length xs], ys <- [(take n xs)]] maxsubarrays :: [Integer] -> [Integer] maxsubarrays xs = msa [] (subarrays xs) where msa m [] = m msa m (x:xs) | sum x > sum m = msa x xs | otherwise = msa m xs --for testing: should return [2, 5, -1, 3] main = maxsubarrays [-1, 2, 5, -1, 3, -2, 1] I've read tutorials about the syntax of Haskell, but I can't seem to find any that teach you how to really "think" in a Haskell way. Is there anything (books, online tutorials, exercises) that anyone could recommend? Thanks, James

21 33

Using Haskell to investigate ML's value restriction
by Brian Hulley 19 Jul '07

19 Jul '07

Hi, Ii is interesting that in ML, the presence of mutable ref cells and parametric polymorphism requires the whole language to be dominated by a "value restriction" [1] to ensure that the type system remains sound, whereas in Haskell, because IORef's can only be created (and used) in the IO monad, no such restriction is necessary. I've often wondered why such a simple thing as using a monad has this magical effect, especially since it seems to me that the real problem lies in the fact that type variables in HMD type inference are not generalised properly due to the absence of an explicit representation of the quantifier, so I decided to try using Haskell's more modern type system to investigate further, using the IO monad together with (unsafePerformIO) and (evaluate) to simulate the execution of an ML program: {-# OPTIONS_GHC -fglasgow-exts #-} module Test where import Data.IORef import System.IO.Unsafe (unsafePerformIO) import Control.Exception (evaluate) ref v = unsafePerformIO $ newIORef v put r f = unsafePerformIO $ writeIORef r f get r = unsafePerformIO $ readIORef r -- Gives a core dump as expected test1 :: IO () test1 = do let r = ref (\x -> x) evaluate (put r (\x -> x + 1)) evaluate (get r True) return () (test1) is based on one of the ML examples in [1], and when executed, causes a segmentation fault. The reason seems to be the strange type that is assigned to (r): *Test> let r = ref (\x -> x) *Test> :t r r :: forall t. IORef (t -> t) *Test> (To run this you need to use ghci -fglasgow-exts Test.hs to get ghci 6.6.1 to display the quantifier.) What's strange (to me) about the above typing is that the "forall" has moved outside the IORef constructor. In other words, although we supplied the constructor with a function which can operate on any value, we got back something which, for any value, contains a function which can operate on it. The reason afaics that (test1) goes wrong is that the let binding causes (r) to be bound to the type above, so the argument matches both forall a. Num a => a -> a and Bool -> Bool so the action (evaluate (get r True)) tries to apply a function which expects a number to a Bool. However if we add an explicit type to (r) to get (what I see as) the expected quantification, the type checker correctly rejects the program: test2 :: IO () test2 = do let r :: IORef (forall a. a -> a) = ref (\x -> x) evaluate (put r (\x -> x + 1)) evaluate (get r True) return () "no instance for Num a ..." which might seem like a reason not quite related to our chain of thought so I also tested this using: test3 :: IO () test3 = do let r :: IORef (forall a. a -> a) = ref (\x -> x) evaluate (put r (\'c' -> 'c')) evaluate (get r True) return () which gives "couldn't match expected type `a' (a rigid variable) against inferred type `Char'". In other words, the IORef must always contain a function that works with anything - we can't just give it a more specialized function, so the program is rejected for the reasons we expect. Interestingly, even without type annotations, if we use a case instead of a let, the typechecker also rejects the program: test4 :: IO () test4 = case ref (\x -> x) of r -> do evaluate (put r (\'c' -> 'c')) evaluate (get r True) return () this time by noting that (Bool -> t) does not match (Char -> Char). This illustrates (afaiu) that "case" does not introduce any quantification, in contrast to "let" hence the uninstantiated meta-tyvars of r have to unify with both its uses. In conclusion, it seems that the "magic" given by always having to use IORef's inside the IO monad (without unsafePerformIO of course) is due to the fact that when used this way types involving IORefs never get generalized wrongly since they're never created by a "let" binding. Another conclusion is that if we wanted at some point to have another new strict language with Haskell's nice type system and syntax as an alternative to the ML family, and we also wanted to have references (and continuations), then either the rule for generalizing the meta-type variables in a "let" binding would have to be changed or else we would still have to use monads. I'd be interested to know if the use of impredicative types would automatically solve the "wierd quantification" problem, since: *Test> :t ref ref :: forall a. a -> IORef a therefore applying this to an argument of type (forall b. b -> b) should hopefully give a result of type (IORef (forall b. b -> b)), thus the use of impredicative types might allow such a strict variant of Haskell to use side-effects instead of monads while still retaining type soundness... ? Best regards, Brian. [1] http://www.smlnj.org/doc/Conversion/types.html

1 0