March 2010 - Haskell-Cafe

ANN: Progression-0.3 (supporting benchmarking in Haskell)
by Neil Brown 02 Mar '10

02 Mar '10

Hi all, I've just uploaded the new version of my Progression benchmarking library to Hackage (http://hackage.haskell.org/package/progression) Progression is a utility built on top of Criterion that helps you record benchmark times for several different versions of your code and then draw graphs to compare them. The latest version adds: support for normalisation of benchmark times, support for drawing bar charts, and allows for more detailed configuration of how the data is arranged before plotting. I've written in more detail about the changes in a blog post (http://chplib.wordpress.com/2010/03/02/progression-0-3-bar-charts-and-norma…) which also has an example of a normalised bar chart generated with the new version. Thanks, Neil.

1 0

Multiple Interpretations for a monad?
by Günther Schmidt 02 Mar '10

02 Mar '10

Hi everyone, in my attempts to remove boilerplate and thus to do more "abstraction" I come across a number of interesting things and suggestions. Especially blog posts from Dan Piponi and also Heinrich Apfelmus. I think what they both are saying is that you can construct / implement some sort of 2 layered monad which can then have more than one interpretation. In the responses to one of my posts on DSLs Dan Piponi also points out that he considers monads also to be DSLs. It didn't click with me when he said it, but reading more of his blog posts made me remember that. Now I know this is probably something obvious to most haskellers, but to me it's not. Did I understand this correctly so far? Günther

4 3

haskelldb problem
by Immanuel Normann 02 Mar '10

02 Mar '10

Hi, I have problems with the usage of the DBSpec module. The following used to work a year ago: testDB :: DBInfo testDB = makeDBSpec "testDB" (DBOptions False) [t1] t1 :: TInfo t1 = makeTInfo "t1" [c1,c2] c1 :: CInfo c1 = makeCInfo "c1" (IntT,False) c2 :: CInfo c2 = makeCInfo "c2" (StringT,False) Now the problem is type error in (DBOptions False): Couldn't match expected type `DBOptions' against inferred type `Database.HaskellDB.DBSpec.PPHelpers.MakeIdentifiers So my precise problem is the usage of that "MakeIdentifiers": MakeIdentifiers moduleName :: String -> String identifier :: String -> String toType :: String -> String Could someone please demonstrate how to use MakeIdentifiers reasonably e.g. for the above testDB? And more general: I cannot find uptodate documentation on haskelldb. Is there something around? Thanks Immanuel

2 2

Gtk2hs on Snow Leopard: "Failed to load interface for `System.Glib.UTFString'"
by Michael Goy 02 Mar '10

02 Mar '10

Hi, I am very close to suicide or similar acts of pure desperation... Since weeks, I am trying different approaches to get gtk2hs running on my Snow Leopard MacBook Pro... no success, you guess it... My current GHC is 6.10.4 (but I also tried 6.10.3 before) when I try to make GTK2HS from Source GTK2HS-0.10.1 I get the following error: Failed to load interface for `System.Glib.UTFString' It seems to be a glib problem; I attached a log of make with everything disabled except glib. BTW: I am interested in ANY hints how to get gtk2hs running on Snow Leopard: Is there any known solution for this problem that i wasn't able to find via google? Best regards Mitch

1 0

What are "free" Monads?
by Günther Schmidt 02 Mar '10

02 Mar '10

Hello, I see the term "free monad" quite a lot, but don't really see an explanation what a free monad is. What sets a monad free and why in this day and age are there unfree monads? Günther

6 7

Linear programming in Haskell
by Louis Wasserman 01 Mar '10

01 Mar '10

Is there a nice package out there somewhere with a linear programming implementation? Preferably with a nicely functional interface? Kthxbai, Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

10 20

Optimizing hash array mapped tries
by Edward Z. Yang 01 Mar '10

01 Mar '10

Hello all, I spent this weekend attempting to impement Phil Bagwell's Hash Array Mapped Tries in Haskell. You can view the fruits of this work at this repository: http://github.com/ezyang/hamt Unfortunately, I'm getting pretty abysmal performance out of the implementation I wrote, so I'm hoping to get some performance tuning insights here. My cost centers look about like this: time% alloc% i-Full-update HAMT 29.1 31.4 lookup' HAMT 13.7 4.3 main Main 12.8 19.7 subkey HAMT 11.5 10.0 i-Bitmap HAMT 9.4 12.0 i-Full HAMT 8.1 12.9 insert' HAMT 5.1 0.6 popCount PopCount 4.7 1.0 And my GC stats look like: ./HAMTTest 256000 +RTS -t 275576630962922 <<ghc: 410718260 bytes, 788 GCs, 19646424/46880276 avg/max bytes residency (9 samples), 138M in use, 0.00 INIT (0.00 elapsed), 1.14 MUT (1.13 elapsed), 1.88 GC (2.00 elapsed) :ghc>> + 0:03.16 ./IntMapTest 256000 +RTS -t -710684043813 <<ghc: 172126372 bytes, 329 GCs, 5552955/10483896 avg/max bytes residency (9 samples), 31M in use, 0.00 INIT (0.00 elapsed), 0.51 MUT (0.51 elapsed), 0.62 GC (0.67 elapsed) :ghc>> + 0:01.18 IntMap is included for comparison. The HAMT does about x3-5 worse than IntMap, and uses about x4 more memory (and gets correspondingly penalized when garbage collection occurs). My observations/suspicions are as such: * i-Full-update essentially copies a 32-size vector, with a change to one element. I think I am getting brutally punished for this, in terms of both memory usage as well as runtime. What I'm curious is whether or not this is intrinsic to the algorithm, or if it's something special that GHC is doing. * Bagwell suggests that each node in the Array-Mapped Trie should take only two words. I think I'm losing another two words to storing bounds information in vector, as well as the costs of boxing (though I can't tell if GHC is boxing or not). I've done some playing around with the data declaration, but it's current form seems to result in the fastest implementation. I wonder if this is what is causing the x4 ballooning of memory, or if it's something else. I haven't tried rewriting the code to use GHC's arrays. * Increasing the heap size seems to generally improve the performance the HAMT; a 1G heap on a 512K sample set reduces the difference to about x1.5-2 slower. It's hard to tell if the memory allocation system is working for or against me. What bothers me is even if I could magically wave away all GC time in HAMT, it would only barely win against IntMap. Maybe the algorithm is simply not as good as a good ole' Patricia Trie; but then again, maybe not. Comments and suggestions greatly appreciated. Thanks, Edward

4 8

Performance of Knight's Tour
by Artyom Kazak 01 Mar '10

01 Mar '10

Hi! I'm learning Haskell, and now I'm trying to make framework for solving searching problems, such as Knight's Tour. For small boards it answers instantly. For 7x8 board - 23 seconds. For 8x8 board - more than 30 minutes (it hasn't finished yet). Where is the root of the evil? --program module Main where import Data.List import Data.Array.Unboxed import qualified Data.Array.IArray as IArr import Data.Ix data SResult = Good | GoodProcess | Process | Bad data SDPSearch a p r = SDPSearch (a -> p -> [a]) --expand (p -> p) --update (a -> p -> SResult) --sort ([a] -> r) --result runSDPSearch :: SDPSearch a c b -> [a] -> c -> b runSDPSearch (SDPSearch e u s r) list p = r (rec list params) where params = iterate u p rec [] _ = [] rec (l:lp) pr@(n:np) = case s l n of Good -> l : rec lp pr GoodProcess -> l : (rec (e l n) np) ++ (rec lp pr) Process -> (rec (e l n) np) ++ (rec lp pr) Bad -> rec lp pr main = do (a, b) <- (break (== ' ')) `fmap` getLine print (knightTour (read a) (read b)) knightTour :: Int -> Int -> UArray (Int, Int) Int knightTour a b = runSDPSearch (SDPSearch e u s r) [((1, 1), sArray)] 2 where size = a * b range = ((1, 1), (a, b)) sArray = listArray range (1 : (replicate (size - 1) 0)) allTurns :: Array (Int, Int) [(Int, Int)] allTurns = IArr.listArray range [turns x y | x <- [1..a], y <- [1..b]] where shifts = [(1, 2),(1, -2),(2, 1),(2, -1),(-1, 2),(-1, -2),(-2, 1),(-2, -1)] turns x y = [(x+i, y+j) | (i, j) <- shifts, inRange range (x+i, y+j)] e ((x, y), arr) p = [(t, arr // [(t, p)]) | t <- changes] where changes = [t | t <- allTurns ! (x, y), arr ! t == 0] s el p | p == size = Good | otherwise = Process u = (+ 1) r l | not (null l) = snd (head l) | otherwise = error "No solutions!"

2 5

Cabal pre-compiled packages
by Diego Souza 01 Mar '10

01 Mar '10

Hi, currently when one install a cabal package it compiles it and then install generated binaries. I wonder whether or not it would be useful to have pre-compiled binaries as many package managers usually do (e.g. apt). I often think that would save some time on the expense of a busier hackage server capable of generating packages for many different platforms. I'm particularly thinking on the following scenario: suppose that you have code that is ready for production. If cabal supported pre-compiled binaries, there is no need to install ghc or eventually any other compiler, just runtime environment and eventually cabal. I must say that I have no experience in doing this in Haskell (just personal/small projects), so I suppose one have to generate binaries and use other sort of package manager to deploy code to production (which sounds reasonable as well). Thus, if the assumption is correct, cabal is a development tool, not something one could to only deploy runtime-only packages. I also would appreciate if others could share how usually this is managed. Best Regards, ~dsouza

5 5

Ghent Functional Programming Group: First Meeting on April 1, 2010
by Jeroen Janssen 01 Mar '10

01 Mar '10

Dear All, The results of the doodle are in, and the result is that the first meeting of the Ghent Functional Programming Group will be held on April 1, 2010 at 7pm in meeting room "Shannon" in the Technicum building (Sint-Pietersnieuwstraat 41, 9000 Gent) of Ghent University. The automatic doors will be closed at this time, but we will attach a notice with the telephone number of the meeting room at the front door in the outer left of the building, so you can call us to let you in. We would like to ask anyone even remotely considering to participate to fill in the following Google form: http://spreadsheets.google.com/viewform?formkey=dEtsR2ZIdVhqeVdRNkx6bmxCdF9… Filling in this form does not commit you to anything, but merely serves as an indication of the number of participants for our sake. We will also only be sending follow-up mails with the final program etc. to the persons that have registered. If you do not intend to come to this first meeting, but wish to be updated on our activities, you can follow us on Twitter: http://twitter.com/ghentfpg or you can sign-up for our Google group: http://groups.google.com/group/ghent-fpg Our current program already contains one talk by Tom Schrijvers entitled "Functional Pearl: The Monad Zipper", with the following abstract: "This pearl aims to demonstrate the application of Huet's zipper to the monad stack for the development of highly modular programs." Anyone willing to give a talk on a subject that fits the scope can e-mail us with a proposed topic, no matter what experience level you have, or no matter how short or long the talk will be. Kind Regards, Bart Coppens Jeroen Janssen

1 0