October 2002 - Haskell-Cafe

Expander2
by Prof. Dr. Peter Padawitz 08 Oct '02

08 Oct '02

Expander2: A Formal Methods Presenter and Animator ================================================== Expander2 has been designed as a multi-purpose workbench for interactive logical inference, constraint solving, data flow analysis and other procedures building up proofs or computation sequences. Moreover, several interpreters translate expressions into tailor-made two-dimensional representations that range from trees and term graphs to tables, fractals or other turtle-system-generated pictures. Expander2 has been implemented in O'Haskell}, an extension of Haskell with object-oriented features for reactive programming and a typed interface to Tcl/Tk for developing GUIs. Besides a comfortable GUI the design goals of Expander2 were to integrate testing, proving and visualizing deductive methods, to admit several degrees of interaction and to keep the system open for extensions or adaptations of individual components to changing demands. Proofs and computations performed with Expander2 follow the rules and the semantics of swinging types (ls5-www.cs.uni-dortmund.de/~peter/Swinging.html). Swinging types combine constructor-based visible types with state-based hidden types and have unique (Herbrand) models, which interpret relations as the least or greatest solutions of their axioms. All features of the system and their use are described in the manual ls5-www.cs.uni-dortmund.de/~peter/Expander2/Expander2.html (sorry, this is still a big file, it will be splitted soon; PostScript version: ../Expander2/Expander2.ps.gz). The paper ../Expander2/Chiemsee.ps.gz concentrates on the prover features. Download everything with ../Expander2.tar.gz. Please email comments, bugs, etc. to peter.padawitz(a)udo.edu. Peter

1 0

Re: need help optimizing a function
by Zdenek Dvorak 08 Oct '02

08 Oct '02

Hello, > > p.s., I sense your next question is going to be something like "why > > can't the compiler detect that the array can be updated in place > > instead of copied" and the answer, from what i can tell, is simply > > that it doesn't try. > >And one might argue that it should not try [snip] and the other answer is that the result would not be worth the effort usually. The idea seems nice, but the laziness is where I see the problem; see the following code: do_something::Array Int Int->(Array Int Int, Result) do_something a = (a'',res) where a' = a // [(summon_index, summon_int)] w = a' ! 4 res = do_some_work w a'' = a' // [(summon_other_index, summon_other_int)] Seems like nice candidate for update-in-place? But the problem is, that in general you cannot say when w will be evaluated -- so you simply cannot destroy a' before then. This is also reason why DiffArray (from hslibs) does not have to be very useful, unless you have a good control on when things are evaluated -- it may (and it also happened to me) have quadratic behavior in cases like this. To solve this, '!' would have to produce a new array too; but then you must pass it everywhere and effectively you are doing the work monads would do for you. So in general you must choose -- either your programs will be nice and functional, but you will have to use structures with (some kind of) logarithmic slowdown (FiniteMap, Trie), or some of their parts will be embedded in monads. Zdenek Dvorak _________________________________________________________________ MSN Photos is the easiest way to share and print your photos: http://photos.msn.com/support/worldwide.aspx

1 0

Graphics output
by Gerhard Navratil 08 Oct '02

08 Oct '02

I would like to write line graphics into a file (e.g. contour lines calculated by a Haskell function) and access the data from standard programs. For the output I need a Library. Since I do not to write the output I would like to know if there is a library writing graphics in a standard format like dxf or PostScript. I have not found anything on the Web so this is my last chance. Thanks in advance! Gerhard ==================================== Gerhard Navratil Teaching- And Research-Assistant Vienna University of Technology, Austria Institute for Geoinformation Gusshausstr. 27-29 1040 Vienna Tel.: ++43 (0) 1 / 58 801 - 12721 Fax.: ++43 (0) 1 / 58 801 - 12799 Cel.: ++43 (0) 699 / 197 44 761 http://www.geoinfo.tuwien.ac.at

3 2

how to debug?
by David Roundy 07 Oct '02

07 Oct '02

How does one debug in haskell? I have a function that I could swear should behave differently than it does, and after tracking down bugs for many hours, I'm wondering if there's any way to step through the evaluation of a haskell function? The other way I would be debugging in an imperative language would be to sprinkle printfs around. Is there any way to do something like that cleanly in haskell? The only thing I can think of would be to modify every function to accept an additional parameter, which seems like it's more likely to introduce bugs than remove them... For what it's worth I'm using ghc, and the only debugging options it seems to have are for debugging the compiler itself. I would be happy to install and use hugs for debugging if it has some nicer debugging mode. I have already isolated my bug within one function, but that function has somewhat funky recursion, and uses an array (which I'm none too familiar with in haskell), and there aren't any smaller parts that I can see to test. :( -- David Roundy http://civet.berkeley.edu/droundy/

3 3

Re: how to debug?
by Zdenek Dvorak 06 Oct '02

06 Oct '02

Hello, >How does one debug in haskell? I have a function that I could swear should >behave differently than it does, and after tracking down bugs for many >hours, I'm wondering if there's any way to step through the evaluation of a >haskell function? > >The other way I would be debugging in an imperative language would be to >sprinkle printfs around. Is there any way to do something like that >cleanly in haskell? The only thing I can think of would be to modify every >function to accept an additional parameter, which seems like it's more >likely to introduce bugs than remove them... > >For what it's worth I'm using ghc, and the only debugging options it seems >to have are for debugging the compiler itself. I would be happy to install >and use hugs for debugging if it has some nicer debugging mode. > >I have already isolated my bug within one function, but that function has >somewhat funky recursion, and uses an array (which I'm none too familiar >with in haskell), and there aren't any smaller parts that I can see to >test. :( aside from (useful) general advices already given, just few tips that I found useful when I needed to debug: -- to print debug dumps, you may use 'trace' function from IOExts (but beware, it may affect behavior of your program if used incorrectly) -- other way (safer, but slower to learn and use) is to use Hood library -- if your program fails with some really informative error message of type '*** Exception: Maybe.fromJust: Nothing', compiling it with profiling (-prof -auto-all) and running with +RTS -xc will give you a stack dump (pretty useful, well hidden feature :-) Zdenek Dvorak _________________________________________________________________ Chat with friends online, try MSN Messenger: http://messenger.msn.com

2 1

Re: how to debug?
by D.Wakeling＠exeter.ac.uk 06 Oct '02

06 Oct '02

David Roundy <droundy(a)jdj5.mit.edu> writes: > How does one debug in haskell? I have a function that I could swear should > behave differently than it does, and after tracking down bugs for many > hours, I'm wondering if there's any way to step through the evaluation of a > haskell function? The best place to start would be with the nhc98 compiler and the Hat tracing system developed by the Functional Programming Group at the University of York. See http://www.cs.york.ac.uk/fp/nhc98 David ------------------------------------------------------------------------------- Dr. David Wakeling, School of Engineering and Computer Science Harrison Building, University of Exeter, Exeter, Devon, EX4 4QF. unofficial web page: http://www.dcs.ex.ac.uk/~dwakelin -------------------------------------------------------------------------------

1 0

Boxed versus Unboxed
by Shawn P. Garbett 03 Oct '02

03 Oct '02

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I've been reading on this list about boxed/unboxed structures. I'm not quite clear what this terminology means. Is there a good paper that covers this topic in detail, or a book reference? -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (GNU/Linux) iEYEARECAAYFAj2a8OEACgkQDtpPjAQxZ6DUSgCeIRgAl3dpOPavJhrmwFxal5O1 Y8IAnRDzmdag9lyljlacKtE4aZMujfiG =h2Zn -----END PGP SIGNATURE-----

3 2

Performance question
by ketil＠ii.uib.no 02 Oct '02

02 Oct '02

At the moment, I have a user defined data type on which I have defined some operations, instantiated (not derived) Eq and so on. However, for efficiency I'm storing the actual data in UArrays of Word8. In order for everything to work, I need functions 'toW8' and 'fromW8' to map between the data type and its representation in the array. I gather it is impossible to hide the 'Eq' instance of Word8 and/or redefine it, but could this be circumvented by instead of data Foo = F | G instance Eq Foo where F == _ = True _ == _ = False defining something like newtype Foo = F Word8 f, g, h :: Foo f = F 0 g = F 1 and using the same instance declaration? And will it still fit into a UArray? (It is of course possible that, while profiling indicates otherwise, the conversion functions have little impact in practice; i.e. the optimizer will do away with them.) -kzm -- If I haven't seen further, it is by standing in the footprints of giants

2 1

question about 'sort' algorithm
by David Roundy 02 Oct '02

02 Oct '02

I was wondering if anyone knows what sort of algorithm the 'sort' function in the List module actually uses? In "The Haskell 98 Library Report", they give an insertion sort implementation, but I find it hard to believe that the library actually uses insertion sort. Basically, I need O(n log n) sorting, and this is a bit awkward to accomplish efficiently with lists. I would have thought that this awkwardness should be dealt with in the standard library, but seeing an O(n^2) algorithm in the description troubles me. -- David Roundy http://civet.berkeley.edu/droundy/

2 1