June 2009 - Haskell-Cafe

Parsing .dot files?
by Lee Pike 25 Jun '09

25 Jun '09

Hi, Does anybody know of a Haskell library for parsing .dot graph files? (I know Andy Gill wrote dotgen for *generating* .dot files <http://hackage.haskell.org/package/dotgen >.) Thanks, Lee -- <http://www.cs.indiana.edu/~lepike/>

3 2

Can you determine a constructor's arity using Data.Typeable and Data.Data?
by David Fox 25 Jun '09

25 Jun '09

Is it possible to determine the arity of a value's constructor? Suppose I have a value x of type data A = B Int | C They typeOf function returns its TypeRep, which contains its type constructor, but I don't see how to decide whether that constructor's arity is 0 or 1. If the type has field names I can look at those using Data.Data.conFields and count them, but if it doesn't I don't see how to do it. -david

2 2

Using unsafePerformIO safely
by gladstein＠gladstein.com 25 Jun '09

25 Jun '09

Regarding how to make the show instructions cause printout as soon as they are executed: If you write your interpreter to return a list of printout lines (strings), you get this behavior for free. Haskell's laziness enables the printing to start right away, while in an imperative language the list of strings wouldn't be returned until it was complete. To see this in action, try this program: main = mapM putStrLn myList myList = ["first", "second", loop, "third"] loop = loop Despite the infinite loop, "first" and "second" print out.

1 0

Another question about unsafePerformIO
by Matthias Görgens 25 Jun '09

25 Jun '09

I have a program that optimizes train schedules. It employs an external solver for Integer Linear Programs. The solve function has the following type: > solve :: Constraints -> IO (Maybe Solution) And this works. However, my external solver also behaves like a pure function from input to output. I wonder whether this guarantee should be reflected in the type system. I'd also appreciate if the compiler would be able to eliminate some calls to the solver. > solvePure :: Constraints -> Maybe Solution > solvePure = unsafePerformIO . solve Is this a good idea?

4 4

How to fork a process?
by Magicloud Magiclouds 25 Jun '09

25 Jun '09

Hi, In many language, both thread and process are supported. But in haskell's document, the only thing I could find called fork is to make a thread. So how to fork the program itself, like fork () in C? Thanks. -- 竹密岂妨流水过山高哪阻野云飞

2 1

Code walking off the right edge of the screen
by Deniz Dogan 25 Jun '09

25 Jun '09

I (too) often find myself writing code such as this: if something then putStrLn "howdy there!" else if somethingElse then putStrLn "howdy ho!" else ... I recall reading some tutorial about how you can use the Maybe monad if your code starts looking like this, but as you can see, that doesn't really apply here. "something" and "somethingElse" are simply booleans and each of them have different actions to take if either of them is True. So how do I make code like this prettier? Thanks, Deniz Dogan

14 16

Using unsafePerformIO safely
by Hector Guilarte 25 Jun '09

25 Jun '09

Thanks for answering so fast. Yes, GCL == Guarded Command Language... It is for an assigment I have in my Languages and Machines Course. About the nicer/Haskellier solution you proposed: If there is a way of printing right in the moment the Interpreter finds the show instruction then I don't think the teacher is gonna like this soluttion (I would bet on that) so, can you (or somebody) explain a little bit better how would the ugly solution be? As I said earlier, I'm no expert in monads, actually the truth is that I know almost nothing about monads, so please, explain it to me as if you are explaining it to a Monads newbie... Also, can somebody explain me how would it be using the Writer Monad? remember is for a Monads newbie... Thanks a lot! Hector Guilarte On Thu, Jun 25, 2009 at 6:04 PM, Jochem Berndsen <jochem(a)functor.nl> wrote: > Hector Guilarte wrote: > > I made a GCL compiler using Alex and Happy and now I'm making the > > interpreter to that program. Here's the deal: > > > > > First of all, I'm no expert in the usage of monads. Now: > > > > Whenever a "show" instruction is found in any GCL program while the > > interpretation is being done it is supposed to print on the stdout the > > string or the aritmetic expresion it was called with, so I guessed I need > to > > run an IO operation and continue the interpretation of my program. I > managed > > to do this using unsafePerformIO and `seq` like is shown below. My > question > > is: Is it safe to use it this way? So far it is working great, but I need > to > > be sure I'm using it in a "safe" way. Like I said, I'm no expert in > monads > > and the System.IO.Unsafe documentation says: > > > > " > > *unsafePerformIO* :: > > IO< > http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html#t… > >a > > -> a > > This is the "back door" into the > > IO< > http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html#t… > >monad, > > allowing > > IO< > http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html#t… > >computation > > to be performed at any time. For this to be safe, the > > IO< > http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html#t… > >computation > > should be free of side effects and independent of its > > environment. > > " > > > > I don't know if the IO computation I'm doing is free of side effects and > > independent of its enviroment :s. (is just hPutStr stdout ....) > > Well, writing to the standard output is certainly a side effect. (This > does not mean that you cannot use unsafePerformIO. The compiler, > however, may assume that any value is free from side effects. This means > that you could get, in theory, less or more output from your program > than you want. In this sense it is not "safe".) > > > Also I've read something about my code not being executed for sure or > > something like that. Can somebody check the code and tell me if I'm > "safe" > > with it? > > It's "safe" in the sense that it probably won't blow up your computer. > It may also work. On the other hand, I would not recommend using > unsafePerformIO in this way. > > I see two possibilities for resolving this issue: > * (ugly) run your GCL (Guarded Command Language?) interpreter in the IO > monad, and using "print"/"putStr"/... whenever you encounter a 'show' > statement in the GCL program. > * (nicer/Haskellier) adapt your interpreter such that it returns a list > of Strings to output. You have then a purely functional interpreter, and > in the main function of your program you can print this list. This will > be lazily evaluated as the GCL program runs. You now have a very nice > separation of clean, pure code, and impure code in the IO monad (your > "main" function, which can be pretty small in your case). To avoid > boilerplate, you can use the Writer monad, for example, but others may > have better suggestions. > > Kind regards, > > -- > Jochem Berndsen | jochem(a)functor.nl > GPG: 0xE6FABFAB >

5 8

Error in array index.
by Jason Dusek 25 Jun '09

25 Jun '09

I'm using tuples to index into a `UArray` created like this: fromList :: [(Word16, Word16)] -> UArray (Word16, Word16) Bool fromList list = runSTUArray $ do arr <- empty return arr empty :: ST s (STUArray s (Word16, Word16) Bool) empty = newArray ((0,0), (0xFFFF,0xFFFF)) False You'll notice this example doesn't do much; I'm not able to get much mileage so far. For example: > Array16Bit.fromList [(1,2), (2,3)] array ((0,0),(65535,65535)) [((0,0),*** Exception: Error in array index What do I need to do to debug this? -- Jason Dusek

6 13

Re: [Haskell] ANNOUNCE: jhc 0.6.1
by David Barton 24 Jun '09

24 Jun '09

Switching to Haskell Cafe; I hope you read that list, John, since it seems more suitable to this kind of question. John Meacham wrote: > Hi, this is to announce the release of jhc 0.6.1. The jhc homepage with > distribution information is at http://repetae.net/computer/jhc/ > > The main new feature in this release is a much simplified > cross-compilation mechanism. While cross-compilation was always possible > with jhc, it used to involve manually copying the C file and calling gcc > with the right options on it, now this is taken care of by jhc. > > A (popular) example would be setting up an iPhone cross compilation > target. For instance with the SDK setup I have, I would simply add the > following to a file ~/.jhc/targets.ini > > [iphone] > cc=arm-apple-darwin > cflags+=-I/usr/local/arm-apple-darwin/include > merge=le32 > > then you can compile iphone binaries with > > ; jhc --cross -miphone HelloWorld.hs > > the targets mechanism is extensible at run-time and I have included > native unix, win32, osx-intel and osx-powerpc targets. But certainly > many more interesting ones are possible. Some I have tested have been a > nokia N770 as a target and an atheros MIPS based router running dd-wrt. Maximum coolness! When you were targeting the nokia, how did you handle the radically different user interface? Did you have to establish a mapping from one of the Haskell UI packages to the Nokia equivalents? If so, which one did you pick, and how much time did it take? I'd love it if I could get this working for the Palm.... Dave Barton (soon to be) University of Toronto

2 1

Optimizing spelling correction program
by Kamil Dworakowski 24 Jun '09

24 Jun '09

Hi all, I want to learn how to optimize Haskell code on the Norvig's spelling correction program [1]. Peter Norvig has written the program in Python, quite a literate translation to Haskell (thanks to Grzegorz Chrupala) [2] was also available. Both versions are about 23 LOCs, and Haskell version is four times slower, 2m25s versus 36s. All the numbers I give come from running the program on a list of 806 misspellings, Haskell version compiled with - O2 and -fforce-recomp flags. I started with trial and error approach. Just preventing a repetitive call to keysSet brought the running time down to 1m48s. I also restructured the edits1 function and dropped all uses of sets, which haven't been pulling their own weight. This brought the running time down to 55s. Not quite there yet but close. Reading the Profiling chapter in the RWH book enabled me to do some more informed optimizing. At this point the GC time was about 2% of the overall runnig time, Grzegorz has done a good job of using strict versions of functions where necessary. The timing per expression however showed something useful, 70% of the time was being spent around determining membership in the known words dictionary (Data.Map). There are about 30 000 items in the dictionary. Right... Python uses hashtables while here I have a tree with log n access time. I did not want to use the Data.HashTable, it would pervade my program with IO. The alternative is an ideal hashmap that never gets changed. This program creates a dictionary at start which then is only being used to read from: an ideal application for the Data.PerfectHash by Mark Wotton available on Hackage [3]. The PerfectHash is a dictionary keyed by ByteStrings, so I had to migrate the program to use these instead of Strings. Sadly it increased the running time to 59s. Adding PerfectHash brought the running time down to 39s. I have done some code restructuring with the view to publishing it, which brought the running time up to 45s. The code is available on patch-tag [4] for anyone to scrutinize and hopefully point out mistakes (it uses big.txt and misspellings file which are linked to from Norvig's page [1]). At this point [5] I don't know how to proceed. The program is still slower than Python. The -ddump-simpl dump does not give me any clues, there is too much of it and I don't understand most of it. The GC time is about 10% of the total, and according to the profiler almost half the time is spent in the member function, and almost all the rest in edits1. Shouldn't it run much faster than the interpreted Python? Frankly, I am not impressed with the PerfectHash performance; It looks as if it is only two times faster than Data.Map. Is this because of the number of elements? 1. http://www.norvig.com/spell-correct.html 2. http://pitekus.blogspot.com/2007/04/norvigs-spelling-corrector-in-haskell.h… 3. http://hackage.haskell.org/package/PerfectHash 4. http://patch-tag.com/r/spellcorrect/ 5. http://patch-tag.com/r/spellcorrect/snapshot/hash/20090621192727-a99e5-fed4…

8 23