February 2008 - Haskell-Cafe

User groups meeting all over the world
by Don Stewart 08 Feb '08

08 Feb '08

The community might be interested to know that there are (at least) 7 Haskell/FP user groups meeting across the world in the next two weeks! FringeDC Washington DC/USA February 9 PDXFunc Portland/USA February 11 Fun in the afternoon London/UK February 12 BayFP San Francisco/USA February 13 Saint-Petersburg Haskell User Group Saint-Petersburg/Russia. February 16 NYFP Network New York/USA February 19 NWFPIG: Seattle FP Group Seattle/USA February 20 The Austin (Texas) group met a couple of weeks ago. This is a great development -- a year ago I don't think we had *any* groups meeting regularly. Consider dropping in to one, if there's a meetting near you, or starting your own group! All groups we know about are listed here: http://www.haskell.org/haskellwiki/User_groups -- Don

5 4

Re: [Haskell-cafe] Mutable arrays
by John Lato 08 Feb '08

08 Feb '08

Ok, I've done some testing on different array accessing strategies, and at this point I believe that, as Stefan previously suggested, using an Oleg-inspired fold for access offers the best performance. My first non-unsafe idea was to try: > import Data.Array.MArray > import Data.Array.IO > import Data.Int (Int32) > import Data.List (foldl') > > -- |Create an array. Change the type signature to experiment with different array types. > makeAry :: IO (IOUArray Integer Float) > makeAry = newListArray (1,1000000) [1..] > getElemsLazy :: (MArray a e m, Ix i) => a i e -> m [e] > getElemsLazy myAry = getBounds myAry >>= > mapM (readArray myAry) . range this works on a 1 million element Int32 array (IOArray or IOUArray): > myElems <-getElemsLazy myAry > let myMax = foldl' max 0 myElems But with a 10-million element array, I get a stack overflow. I next tried the foldA functions Stefan posted, but had some problems with them. I think that the array elements need to be instances of Bounded and Fractional, and I don't know of a suitable type. Anyway, his code is a little too compact for me to understand without further study, so I moved on. Next I created my own fold operators. These are fairly directly copied from an email Oleg posted to the haskell mailing list: > leftFoldA' myArray self iteratee seed = do > elem <- readArray myArray $ fst seed > case iteratee seed elem of > Left seed -> return seed > Right seed -> self iteratee seed > > leftFoldA :: (MArray a e m, Ix a1) => a a1 e -> ((a1, b) -> e -> Either t (a1, b)) -> a1, b) -> m t > leftFoldA array iteratee seed = > let g = (leftFoldA' array) g in > g iteratee seed > > leftFoldModA' myArray self iteratee seed = do > elem <- readArray myArray $ fst seed > result <- iteratee seed elem > case result of > Left seed -> return seed > Right seed -> self iteratee seed > > leftFoldMA :: (MArray a e m, Ix a1) => a a1 e -> ((a1, b) -> e -> m (Either t (a1, b))) -> a1, b) -> m t > leftFoldMA array iteratee seed = > let g = (leftFoldModA' array) g in > g iteratee seed the two functions to use are leftFoldA and leftFoldMA. The difference, show in the type signature, is that the iteratee in leftFoldA is pure while the iteratee in leftFoldMA operates in the monad. So if you're going to modify the array, for example, you need to use the leftFoldMA version. These folds let me define: > findMax myAry = do > (lowB, highB) <- getBounds myAry > let maxReader (ix, acc) c = > let > ix' = ix + 1 > acc' = max c acc > in acc' `seq` (if ix' > highB then Left else Right) (ix', acc') > (_, myMax) <- leftFoldA myAry maxReader (lowB, 0) > return myMax > > normalizeArray myAry = do > myMax <- findMax myAry > (lowB, highB) <- getBounds myAry > let normMod = 1/myMax > let normalizer (ix, _) c = do > let ix' = ix + 1 > curVal <- readArray myAry ix > writeArray myAry ix (curVal * normMod) > return $ (if ix' > highB then Left else Right) (ix', ()) > leftFoldMA myAry normalizer (lowB, ()) > > -- |show all elements from lowB to highB > -- this only works with IO arrays, since the readArray and print happen in the same monad. > -- you could possibly make it work with ST arrays if you use a monad transformer, but you'd have > -- to change leftFoldMA as well. > showElems myAry lowB highB = do > let showFunc (ix, _) c = do > let ix' = ix + 1 > readArray myAry ix >>= print > return $ (if ix' > highB then Left else Right) (ix', ()) > leftFoldMA myAry showFunc (lowB, ()) There are probably better ways to define the folds, but I hope these are pretty easy to follow. If I was doing a lot of different operations, I'd probably define functions like > makeIteratee highB func = (\(ix, acc) c -> > let > ix' = ix + 1 > acc' = func c acc > in acc' `seq` (if ix' > highB then Left else Right) (ix', acc')) so that findMax becomes: > findMax2 myAry = do > (lowB, highB) <- getBounds myAry > (_, myMax) <- leftFoldA myAry (makeIteratee highB max) (lowB, 0) > return myMax instead of having to define a bunch of iteratees in let clauses. Now, running the program > main :: IO () > main = do > myAry <- makeAry > (lowB, highB) <- getBounds myAry > normalizeArray myAry > showElems myAry 1 10 > showElems myAry 999990 1000000 > return () takes about 5 seconds, with no optimizations. It takes less than a second with -O2. Much better. It does take longer with boxed arrays, but that's to be expected. No unsafe functions, either. The only sketchy bit is using seq in the iteratees (e.g. maxReader in findMax) to force the accumulator. I say sketchy not because it's unsafe or unreliable, but it would be nice if it was unnecessary. Notes: I used GHC 6.8.1 on WinXP, 3.2GHZ P4, 1.5GB RAM. All of my original tests were done without any optimizations, which is why I didn't include timing information for the earlier stuff. The getElemsLazy function is fast, but the stack overflow is annoying. Using the leftFold functions is both faster and avoids the space leak. I was also using the Data.List.Stream and Control.Monad.Stream versions of foldl' and mapM, although I don't think those made much difference. Anyway, this was a good exercise for me. I learned a lot, especially about the power of left-fold enumerators. Cheers, John

2 2

Re: [Haskell-cafe] Best practice for embedding files in a GHC-compiled tool?
by Dave Bayer 08 Feb '08

08 Feb '08

On Feb 7, 2008, at 12:27 AM, gwern0(a)gmail.com wrote: > Are you assuming that the various users have GHC/Hugs installed? You > know about scripting through the 'runhaskell' binary, right? I do, and I've used this. I don't want to do that here. Let me say this again: I am making no assumptions whatsoever about various users, other than platform. Haskell is not a niche language, with the right compile options, it CAN be used in this way. Here's the extreme case: When one is installing Mac OS X, one has access to a command line via a terminal application, but the operating system is otherwise very stripped down. Nevertheless, if one customizes an install DVD by adding a single command-line tool, one can execute that tool in this environment. I'd rather use Haskell than C for such applications. With C, we can introduce one file to an alien environment, and it will run. I've linked GHC Haskell programs that can be used in this way. Such programs can be used by anyone on a given platform. Assuming that GHC/Hugs is installed divides the potential audience by a large factor. Under this extreme hypothesis, how do I embed a compressed tar file into a single file command line tool written in Haskell and compiled by GHC? Thanks, Dave

2 1

Draft chapters of "Real World Haskell" now publicly available
by Bryan O'Sullivan 08 Feb '08

08 Feb '08

John, Don and I are pleased to announce the beginning of the public beta programme for our upcoming book, "Real World Haskell". For further details, please see the following blog entry: http://www.realworldhaskell.org/blog/2008/01/21/finally-the-public-beta-pro… Thanks to all of the Haskell community members who have so far performed sterling service in commenting on our closed drafts. We look forward to your feedback! <b

10 20

Re: [Haskell-cafe] FP and Quality
by PR Stanley 08 Feb '08

08 Feb '08

Thanks, keep the tips coming. I like the ones about the type safety and line counts. Cheers, Paul At 23:33 04/02/2008, you wrote: >Good luck with this - I'd love to see the outcome. > >My experience is that FP tends to result in a lot less code, so if >there are x >bugs per line of code, FP has less bugs per complete application. > >Talking about haskell, the typesystem dissalows whole classes of bugs. Things >simply do not compile if you stitch the innards together in the wrong order >(particuarly if you are agressive about using the most general types >possible). Since this accounts for perhaps 90% of where I do things wrong in >Java, I get a corresponding decrease in run-time bugs in haskell. However, >this is somewhat compensated for by the effort needed to get haskell programs >through the compiler in the first place - debug at compile or debug at >runtime is the tradeoff here. > >FP is easier to verify mechanically than imperative programming - more of the >logic is exposed directly. It's easier to do by-case proofs, even if they are >by-hand rather than mechanical. > >However, all of this is annecdotal. Good luck collecting real stats, or >peer-reviewed annecdotes. You may have luck looking at bug-fix times vs >number of developers for equivalent FP and Java apps/libs. Worth a shot, >given that the bug-trackers tend to be public. You could probably tie it back >to the size of the 'fix' patches. Get some nice graphs? > >Matthew > >On Monday 04 February 2008, you wrote: > > Hi folks > > I'm thinking of writing a little essay arguing the case for the > > advantages of FP for producing quality software. Can the list > > recommend any papers/articles which I can use as sources of my > > argument? I have access to the IEEE database too although earlier I > > couldn't find anything on the subject. > > Thanks, Paul > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe

3 2

background question about IO monad
by Uwe Hollerbach 08 Feb '08

08 Feb '08

Hello, haskellers, I have a question for you about the IO monad. On one level, I seem to be "getting" it, at least I seem to be writing code that does what I want, but on another level I am almost certainly not at all clear on some concepts. In various tutorials around the web, I keep finding this notion that the IO monad is "one-way", that you can put stuff into it, but you can't take it out. (And, damn, some of the contortions I went through while trying to figure out how to do exceptions in my little scheme interpreter certainly bear that out! I was sure beating my head against liftIO et al for a fair while...) But let me post some code snippets here: > lispUTCTime [] = doIOAction (getClockTime) toS allErrs > where toS val = String (calendarTimeToString (toUTCTime val)) > lispUTCTime [IntNumber n] = > return (String (calendarTimeToString (toUTCTime (TOD n 0)))) This is a little function I added to the interpreter a couple of days ago: if you enter (UTCtime) with no arguments, it gets the current time and formats it as UTC: like so; this came from the first alternative above: lisp> (UTCtime) "Wed Feb 6 03:57:45 UTC 2008" and if you give an argument, you get that interpreted as a number of seconds since epoch, and that gets formatted as UTC; this is from the second alternative above: lisp> (UTCtime 1.203e9) "Thu Feb 14 14:40:00 UTC 2008" And here's the doIOAction routine: I wrote this, it's not some system-level routine. > doIOAction action ctor epred = > do ret <- liftIO (try action) > case ret of > Left err -> if epred err > then throwError (Default (show err)) > else return (Bool False) > Right val -> return (ctor val) OK, with all that as background, on one level I understand why I need the doIOAction routine in the first version of lispUTCTime: I'm calling getClockTime, that's an IO action, so I enter the IO monad, get the time, and return: all is cool. In the second version, all I'm doing is taking a number and interpreting it as a time, and writing that in a particular format; again, no problem. But after that, it sure seems to me as if I've taken data out of the IO monad... haven't I? Given that the second alternative never entered doIOAction and that after both are done I have a string of characters, prettily formatted to indicate a time, that's what it feels like to this unwashed C programmer. So, what's going on there? What's the difference between the two alternatives? I would appreciate any enlightenment you can send my way! regards, Uwe

6 11

modeling ANSI C structs in Haskell?
by Galchin Vasili 08 Feb '08

08 Feb '08

Hello, I am reading through the FFI doc. Any suggestions on enabling Haskell programmers to model ANSI C structs that will be passed down to C run-time? Vasili

4 3

Signature for non-empty filter
by Henning Thielemann 07 Feb '08

07 Feb '08

Is Haskell's type system including extensions strong enough for describing a function, that does not always return a trivial value? E.g. (filter (\x -> x==1 && x==2)) will always compute an empty list. Using an appropriate signature for the function it shall be rejected at compile time, because it is probably a mistake - probably (filter (\x -> x==1 || x==2) xs) was meant. I assume that the type must contain somehow an example input for which the function value is non-trivial. If Haskell's type system is not strong enough, what about dependently typed languages like Cayenne or Epigram? (I know, theorem provers have no problem with such types.)

7 23

Two Lectureships in Nottingham
by Graham Hutton 07 Feb '08

07 Feb '08

Dear all, We are advertising two new Lectureships (Assistant Professorships) in Computer Science at the University of Nottingham in England. Applications in the area of functional programming are particularly welcome. Further details are available from: http://jobs.nottingham.ac.uk/vacancies.aspx?cat=160#j2797 The closing date for applications is 22nd Feburary 2008 Best wishes, Graham Hutton +-----------------------------------------------------------------+ | Dr Graham Hutton Email : gmh(a)cs.nott.ac.uk | | School of Computer Science | | University of Nottingham Web : www.cs.nott.ac.uk/~gmh | | Jubilee Campus, Wollaton Road | | Nottingham NG8 1BB, UK Phone : +44 (0)115 951 4220 | +-----------------------------------------------------------------+ This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.

1 0

FP and Quality
by PR Stanley 07 Feb '08

07 Feb '08

Hi folks I'm thinking of writing a little essay arguing the case for the advantages of FP for producing quality software. Can the list recommend any papers/articles which I can use as sources of my argument? I have access to the IEEE database too although earlier I couldn't find anything on the subject. Thanks, Paul

3 2