- Haskell-Cafe - Haskell.org

ANN: A Functional Implementation of the Garsia-Wachs Algorithm
by Nicolas Pouillard 23 Sep '08

23 Sep '08

Hi All, Here is an Haskell implementation of an algorithm that builds a binary tree with minimum weighted path length from weighted leaf nodes given in symmetric order. This can be used to build optimum search tables, to balance a 'ropes' data structure in an optimal way. This module a direct translation from OCaml of a functional pearl by Jean-Christophe Filliâtre yesterday on ML Workshop 2008. There was an interesting point to porting it to Haskell, indeed there is a crucial use of first-class references used only locally. A good reason to show the power of the ST monad and it's runST function! Here is the hackage URL: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/garsia-wachs And the darcs 2 URL: http://darcs.feydakins.org/garsia-wachs -- Nicolas Pouillard aka Ertai

3 3

Re: ANNOUNCE: protocol-buffers-0.2.9 for Haskell is ready
by Chris Kuklewicz 23 Sep '08

23 Sep '08

I am cross-posting this message to several lists. I had learned the trick before the documentation was updated. It seems I have used a very unreliable trick. And the "use castToSTUArray" suggested alternative is a really poor one since I am not using arrays at all. Who can suggest a way to cast from Float to Word32 and Double to Word64 using ghc? The actual task is that I need to write out the Float as a little endian sequence of four bytes and also be able to read it back in. The writing and reading are done in Put and Get monads to ByteString (from the "binary" package). The alloca/poke/peek work around I have looks like castWord32ToFloat :: Word32 -> Float castWord32ToFloat x = unsafePerformIO $ alloca $ \p -> poke p x >> peek (castPtr p) castFloatToWord32 :: Float -> Word32 castFloatToWord32 x = unsafePerformIO $ alloca $ \p -> poke p x >> peek (castPtr p) The unsafeCoerce trick that is no longer working looks like: castWord64ToDouble :: Word64 -> Double castWord64ToDouble (W64# w) = D# (unsafeCoerce# w) castDoubleToWord64 :: Double -> Word64 castDoubleToWord64 (D# d) = W64# (unsafeCoerce# d) Any ideas? Or is the alloca trick the only way to do this? Chris Ian Lynagh wrote: > Hi Chris, > > On Sun, Sep 21, 2008 at 05:37:33PM +0100, Chris Kuklewicz wrote: >> Also, I tried two tricks: >> (D# x) <-> (W64# x) which works fine >> (F# x) <-> (W32# x) which produced garbage, so I had to replace it with >> alloca/poke/peek. > > This isn't supported, and I suspect is the cause of the -fasm problems. > > Please see > http://hackage.haskell.org/trac/ghc/ticket/2209 > for more details and suggested alternative. > > > Thanks > Ian >

4 3

hGetContents and lazyness
by Max Vasin 23 Sep '08

23 Sep '08

Hello, haskellers! Suppose we have function (it filters package filenames from apt Packages file): > getPackageList :: FilePath -> IO [FilePath] > getPackageList packageFile = withFile packageFile ReadMode $ > \h -> do c <- hGetContents h > return $ map (drop 10) $ filter (startsWith "Filename:") $ lines c -- (1) > where startsWith [] _ = True > startsWith _ [] = False > startsWith (x:xs) (y:ys) | x == y = startsWith xs ys > | otherwise = False When, I apply it to a Packages file I (surely) get an empty list. This is an expected result due to lazyness of hGetContents. I tried changing line (1) to > return $ map (drop 10) $ filter (startsWith "Filename:") $! lines c or > return $ map (drop 10) $! filter (startsWith "Filename:") $! lines c with no success. Chaning it to > return $! map (drop 10) $ filter (startsWith "Filename:") $ lines c makes getPackageList function return several (but not all) filenames. What I'm missing? And how can I fix my code? -- WBR, Max Vasin.

2 3

"piping" to system call
by Janis Voigtlaender 23 Sep '08

23 Sep '08

Hi, assume I have a program taking input from stdin. How do I call it from Haskell while feeding to it a string as input. That is, I want a function like system' :: String -> String -> IO ExitCode such that system' cmd inp would be equivalent to first writing inp to a file, say "temp", and then calling system (cmd ++ " < temp") Of course, without actually creating that temporary file and having to clean it up afterwards. Does such a system' exist? Thanks, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

5 7

Re[10]: [Haskell-cafe] Climbing up the shootout...
by Bulat Ziganshin 23 Sep '08

23 Sep '08

Hello Donnie, Tuesday, September 23, 2008, 7:16:04 PM, you wrote: > I don't understand why you are willing to criticize GHC, but > unwilling to help improve GHC. Personally, I think it is a waste of > everyone's time for you to just complain about GHC without offering > suggestions on how to improve GHC -- What is the point? i don't criticize nor complain. haskell is much more higher-level language than C and that's the reason why it's slower. i just cold down heroes that lie to novices saying that Haskell is as fast or even faster than C. if i will say that Ford is slower than F1 cars, is it complaints or critics? :) when i worked on high-speed Haskell libs, i helped GHC team a bit by showing concrete cases. now i just don't work in this area so i have a little to offer ps: xposted to cafe -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0

XML (HXML) parsing :: GHC 6.8.3 space leak from 2000
by Lev Walkin 23 Sep '08

23 Sep '08

Recently I had to process some multi-megabyte XML files. Tried a few Haskell XML parsers (HaXML, HXT, HXML) but all of them were exhibiting very pronounced space leaks, and all but HXML were too strict for my input. Judging by the code and stated objectives, Joe English's HXML (0.2, circa 2003) looked more promising for hacking around so I tried to figure out the space leak problem. It wasn't too long to find out the source of a problem, the buildTree function in TreeBuild.hs. In fact, the very annotation to that function reads as follows: -- %%% There is apparently a space leak here, but I can't find it. -- %%% Update 28 Feb 2000: There is a leak, but it's fixed -- %%% by a well-known GC implementation technique. Hugs 98 happens -- %%% not to implement this technique, but STG Hugs (and most other -- %%% Haskell systems) do implement it. -- %%% Thanks to Simon Peyton-Jones, Malcolm Wallace, Colin Runcinman -- %%% Mark Jones, and others for investigating this. And there's some more in the accompanying documentation: + Under Hugs 98 only, suffers a serious space fault. I wondered why would a contemporary GHC 6.8.3 exhibit such a leak? After all, the technique was known in 2000 (and afir by Wadler in '87) and one would assume Joe English's reference to "most other Haskell systems" ought to mean GHC. But here we are, in 2008 I still can't get HXML to not to leak like a hose while lazily parsing my file. In fact, I can't get my 45-megabyte file parsed on my 1GB RAM system without swapping. So I went ahead and extracted the code and stripped all XML related junk to reproduce the problem with a minimal test case. Attached please find a single tree.hs module which is just sufficient to demonstrate a memory leak. Here's a culprit function: data TreeEvent = Start String -- Branch off a new subtree | Stop -- Stop branching and return 1 level | Leaf String -- A simple leaf without children deriving Show -- Lazily build a tree out of a sequence of tree-building events build :: [TreeEvent] -> ([UnconsumedEvent], [Tree String]) build (Start str : es) = let (es', subnodes) = build es (spill, siblings) = build es' in (spill, (Tree str subnodes : siblings)) build (Leaf str : es) = let (spill, siblings) = build es in (spill, Tree str [] : siblings) build (Stop : es) = (es, []) build [] = ([], []) In fact, the attached module implements almost verbatim the code from an old Joe's request (circa 2000): http://www.cse.unsw.edu.au/~dons/haskell-1990-2000/msg06086.html but my version is a bit more self-sufficient for the new folks who'd like to quickly test it on their system. Am I really ignorant of some important GHC optimization options (tried -O2/-O3), or is this indeed a serious problem to tackle? -- Lev Walkin vlm(a)lionet.info module Main where -- A simple tree to hold hierarchial XML-like data structure data Tree a = Tree a [Tree a] deriving Show -- A member of the event sequence which attempts to build a tree. -- For example, the following sequence -- [Start "top", Leaf "leaf", Start "sub", Stop, Stop] -- should correspond to the following tree: -- Tree "top" [Tree "leaf" [], Tree "sub" []] data TreeEvent = Start String -- Branch off a new subtree | Stop -- Stop branching and return 1 level | Leaf String -- A simple leaf without children deriving Show -- Lazy printing of an infinite tree building process main = print . snd . build $ Start "top" : cycle [Leaf "sub"] -- Convert a stream of tree building events -- into a list of unconsumed events and a constructed tree body. type UnconsumedEvent = TreeEvent -- Alias for program documentation build :: [TreeEvent] -> ([UnconsumedEvent], [Tree String]) build (Start str : es) = let (es', subnodes) = build es (spill, siblings) = build es' in (spill, (Tree str subnodes : siblings)) build (Leaf str : es) = let (spill, siblings) = build es in (spill, Tree str [] : siblings) build (Stop : es) = (es, []) build [] = ([], []) -- Stricter version of build, never terminates on infinite input, -- but exhibits no space leaks whatsoever. build' f (Start str : es) = let (es', subnodes) = build' id es in build' ((Tree str subnodes) :) es' build' f (Leaf str : es) = build' ((Tree str []) :) es build' f (Stop : es) = (es, f []) build' f [] = ([], f [])

4 7

how do i use quickcheck in the IO monad?
by Anatoly Yakovenko 23 Sep '08

23 Sep '08

If i have functions in the IO monad, is there a way to use quickcheck to test them? I have a bunch of C bindings that unfortunately are not "safe". But i would like to be able to use QuickCheck to test them. Thanks, Anatoly

4 3

Re: [Haskell-cafe] Updated formlets sample?
by Martin Huschenbett 23 Sep '08

23 Sep '08

Hi Chris, you're absolutely right. The mistake was in the where-part of withForm. The function handleOk' gets an environment d as argument but uses an extractor that was created without passing d to runFormState. I've put a corrected version on hpaste [1] and also posted it to the wiki on haskell.org [2]. Hope this is ok for you? Regards, Martin. [1] http://hpaste.org/10568#a1 [2] http://haskell.org/haskellwiki/Formlets Chris Eidhof schrieb: > That means that you don't have input0 in your environment, maybe you're > passing in an empty environment? > > -chris > > On 21 sep 2008, at 12:11, Martin Huschenbett wrote: > >> Hi Chris, >> >> thanks for the updated example. Compiling works now. But when I try to >> run it I alway get error messages like >> >> ["input0 is not in the data","input1 is not in the data"] >> >> Regards, >> >> Martin. >> >> Chris Eidhof schrieb: >>> Hey Martin, >>> On 19 sep 2008, at 04:14, Martin Huschenbett wrote: >>>> I found a blog post concerning formlets [1] in the web. Since looks >>>> very interesting I tried to compile the sample code with recent >>>> versions of HAppS and formlets from hackage. But this didn't work as >>>> the API of formlets has changed since this post. >>>> >>>> I tried to adopt the code to the new API but I was unable to finish >>>> this since there is a new monadic context I don't know to handle in >>>> the right way. >>>> >>>> So my question is, is there an updated version of this sample code >>>> in the web or has anybody tried to adopt it and can send me the >>>> results? >>> Yes, I'm sorry for that. The API is still very immature and due to >>> changes, that's also why it hasn't been officially announced yet. >>> I've just put an updated example at http://hpaste.org/10568, hope >>> that'll work for you. I guess we should build a small homepage / >>> wikipage that always has an up-to-date example. >>> -chris

2 1

Re: [Haskell-cafe] Bird-style and blank lines
by Ryan Ingram 23 Sep '08

23 Sep '08

Oops, meant to send this to the whole list. > You can add "-optL -q" to your ghc command line to disable that > behavior; blank lines will no longer be required. -- ryan

2 1

Live twittering from ICFP
by Don Stewart 22 Sep '08

22 Sep '08

ICFP is on now, for those wondering why the list is a bit quiet :) http://www.icfpconference.org/icfp2008/schedule.html I'm doing live updates of events at ICFP/Haskell Symposium here in Canada. http://twitter.com/galoisinc So you can follow events remotely. Cheers, Don

1 0