July 2008 - Haskell-Cafe

vector vs uvector
by stefan kersten 14 Jul '08

14 Jul '08

hi, what's the difference between the vector [1] and uvector [2] packages? should one of those preferred over the other? thanks, <sk> [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ vector-0.1 [2] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ uvector-0.1.0.1

3 3

Human-friendly compiler errors for GHC
by Max Bolingbroke 14 Jul '08

14 Jul '08

I had some free time this afternoon so I put together an (experimental) patch for GHC that implements helpful errors messages. Have a look at this GHCi session to see what I mean: "" $ stage2/ghc-inplace --interactive -fhelpful-errors GHCi, version 6.9.20080711: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> let foo = 10 Prelude> foa <interactive>:1:0: Not in scope: `foa' Maybe you meant one of: `foo' `fst' `not' -- Maybe the matching threshold could stand to be tweaked a bit, e.g. scaled with identifier string length.. Prelude> let myIdentifier = 10 Prelude> myIdentfiier <interactive>:1:0: Not in scope: `myIdentfiier' Maybe you meant `myIdentifier' Prelude> "" The feature was inspired by the equivalent feature in the Boo programming language (http://boo.codehaus.org/) I use the restricted Damerau–Levenshtein distance to do the fuzzy match (http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance) What do you think about this feature? Would it be genuinely helpful or annoying? Max

10 15

Re: [Haskell-cafe] ANNOUNCE: vector 0.1 (efficient arrays with lots of fusion)
by Levi Stephen 14 Jul '08

14 Jul '08

On Sun, Jul 13, 2008 at 12:31 AM, Roman Leshchinskiy <rl(a)cse.unsw.edu.au> wrote: > Hi all, > > the vector library will eventually provide fast, Int-indexed arrays with a > powerful fusion framework. It's very immature at the moment (I haven't > tested most of the code) and implements just a few combinators but I > thought releasing early wouldn't hurt. Use at your own risk and expect > things to break horribly! > Sounds interesting. How does this compare to the uvector library? Thanks, Levi

3 2

Architecturally flawed
by Andrew Coppin 14 Jul '08

14 Jul '08

OK, so I just spent an entire day trying to write some code, and after hours of struggling I have something that's semi-working but very ugly and rather unreliable. My usual guideline for Haskell programming is "if it seems hard, you're doing it wrong"... After many hours of effort, I came up with these: data Writer x instance Monad Writer run_writer :: Writer () -> ByteString write1 :: Bool -> Writer () write8 :: Word8 -> Writer () write16 :: Word16 -> Writer () write32 :: Word32 -> Writer () write64 :: Word64 -> Writer () writeN :: Word8 -> Word32 -> Writer () data Reader x instance Monad Reader run_reader :: Reader x -> ByteString -> x is_EOF :: Reader Bool read1 :: Reader Bool read8 :: Reader Word8 read16 :: Reader Word16 read32 :: Reader Word32 read64 :: Reader Word64 readN :: Word8 -> Reader Word32 Notice that, unlike the Binary package, all of these are bit-aligned rather than byte-aligned. This is what took so much effort. I strived to make each operation as efficient as possible - by performing as few steps as possible. It would have been *far* easier to, say, implement read8 by calling read1 eight times and then packing the bits back into a byte. But that wouldn't be very fast. So actually read8 reads a pair of bytes, bit-shifts them as required, and then ANDs them together. And so on. (Note that the Writer monad uses Data.Binary.Builder (only) from the Binary package. I assume this is more efficient...) I even sat down and wrote a battery of QuickCheck properties because - as you can imagine - there's a hell of a lot to go wrong here! After many hours, I managed to get it to pass all tests... Next I decided to write an LZW compressor. Here's what I came up with: data EncodeLZW symbol eLZW_start :: (Ord symbol) => EncodeLZW symbol eLZW_encode :: (Ord symbol) => EncodeLZW symbol -> symbol -> Writer (EncodeLZW symbol) eLZW_end :: (Ord symbol) => EncodeLZW symbol -> Writer () data DecodeLZW symbol dLZW_start :: DecodeLZW symbol dLZW_decode :: DecodeLZW symbol -> Reader (DecodeLZW symbol, symbol) So each step of the encoder (possibly) writes some bits, and also returns a new encoder state. The decoder is similar. (At least one program bug was caused by the wrong version of the state being used somewhere!) Then I tried to run the code, and oh look, there's a bug somewhere. Emphasis "somewhere". At this point I have several KB of code and no idea how in hell to test it. What I *want* to do is single-step through the encoder algorithm, watch it write bits out and update state, and then single-step through the decoder watching it read bits in and update its state, etc. But I can't. All the encoder does is return a giant Writer object which you can't look inside, only run. And likewise for the decoder. I could try GHC's new debugger. But my experiences with it so far have shown that for all but the most trivial programs possible, it becomes intractably difficult to figure out what the debugger is actually showing you. I actually tried to debug a "normal" LZW implementation once - one that didn't involve two highly convoluted custom monads and a stateful execution model with manually threaded state. This is *not* my idea of a fun time... In a "normal" programming language, at this point you would sprinkle a few print statements around so you can see the intermediate steps the program is taking. But I can't. I'm in the wrong monad. Curses! In the end, the only solution I could come up with was to design a second, "hacked" version of the two monads. Instead of importing one module, you import another that provides the same interface. However, now Reader and Writer are aliases to IO. All write requests cause pretty-printed binary to be sent to stdout, and all read requests pop up a prompt for input from stdin. It worked reasonably well in that I could now add the vitally necessary print statements, and see intermediate values and so forth... It wasn't very pretty though. At this point I decided that lugging 5 individual functions around was silly, and I should write a class: class Encoder e where encoder_start :: e x encode :: e x -> x -> Writer (e x) encoder_end :: e x -> Writer () class Decoder d where decoder_start :: d x decode :: d x -> Reader (d x, x) 10 points to the first person to spot the fatal flaw in this plan... Yep, that's right. The type system won't accept this. The reason? x needs an Ord context. If you turn on multi-parameter type classes *and* flexible instances, apparently this works: class Encoder e x where... instance (Ord x) => Encoder EncodeLZW x where... (I haven't tried but I *presume* it means what I think it does...) Alternatively, you can avoid using dangerous type system extensions and just write class Encoder e where encode :: (Symbol x) => e x -> x -> Writer (e x) ... and make Symbol encompass everything any possible encoder could want. (In reality, x is almost always Word8 or something. But I dislike loss of generality just for the hell of it...) So at least I got that part fixed. Heh. But now I find myself worrying about yet *another* problem: is Writer lazy enough? I mean, the idea is that you can write a program that lazily reads from a file, pushes it through a Writer, and lazily writes the result back to another file. The thing should chug along reasonably fast and use a constant amount of RAM. But all this is only true of Writer is actually lazy enough. I have a horrible feeling that all the complicated Origami inside makes it too strict. And I have no way to check! Actually, thinking about it, is Reader lazy enough? You call run_reader and it hands over your data, but if that data is, say, a list, will run_reader build the entire damn list before it'll hand it over? Or will the monadic code by called as-needed to generate the list elements? Obviously I desire the latter, but I'm really not sure what the actual behaviour is... In summary, I've spent several days coding, and I still don't have a single algorithm working. I've spent all my time wrestling with the mundane details of infrastructure rather than the interesting algorithms I actually set out to implement. This makes me very sad. :-( If anybody can think of a better set of abstractions or another way to do debugging, I'd be interested to hear about it. (This would all be so trivial in an OO language. Just make an Encoder object that updates its own state internally and talks to a Source object and a Destination object for its data...)

8 11

Prime time for Haskell
by Janis Voigtlaender 14 Jul '08

14 Jul '08

It is really just a short discussion, but Haskell STM is featured in an article of this month's Communications of the ACM: http://doi.acm.org/10.1145/1364782.1364800 -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

3 3

Existential quantification problem
by Marco Túlio Gontijo e Silva 13 Jul '08

13 Jul '08

Hello, how do I unbox a existential quantificated data type? > {-# LANGUAGE ExistentialQuantification #-} > data L a = forall l. L (l a) > unboxL (L l) = l is giving me, in GHC: Inferred type is less polymorphic than expected Quantified type variable `l' escapes When checking an existential match that binds l :: l t The pattern(s) have type(s): L t The body has type: l t In the definition of `unboxL': unboxL (L l) = l Thanks. -- Marco Túlio Gontijo e Silva Página: http://marcotmarcot.googlepages.com/ Blog: http://marcotmarcot.blogspot.com/ Correio: marcot(a)riseup.net XMPP: marcot(a)jabber.org IRC: marcot(a)irc.freenode.net Telefone: 25151920 Celular: 98116720 Endereço: Rua Turfa, 639/701 Prado 30410-370 Belo Horizonte/MG Brasil

6 7

memoization
by Logesh Pillay 13 Jul '08

13 Jul '08

I know we can perform memoization in Haskell. The well known recursive Fibonacci example works v. well. f(10000) returns a virtually instant answer which would not be possible otherwise. My (probably naive) function to give the number of partitions of a number :- p = ((map p' [0 .. ]) !!) where p' 0 = 1 p' 1 = 1 p' n = sum [(((-1) ^ (k+1)) * ( p' (n-((k*(3*k-1)) `div` 2)) + p' (n-((k*(3*k+1)) `div` 2)))) | k <- [1 .. n]] It is an attempt to apply the Euler recurrence formula (no 11 in http://mathworld.wolfram.com/PartitionFunctionP.html ) It works but it is shockingly slow. It is orders of magnitude slower than the Python memoized version which runs very fast. parts = {0:1, 1:1} def P(n): if not n in parts: parts[n] = sum ([( ((-1) ** (k+1)) * ( P(n-((k*(3*k-1))//2)) + P(n-((k*(3*k+1))//2)) ) ) for k in xrange (1, n+1)]) return parts[n] Why? Its as if memoization is being ignored in the haskell version. How to fix?

4 3

confusion with fgl and ghc6
by David Bremner 13 Jul '08

13 Jul '08

I don't know whether this is a bug in fgl, in ghc, or I'm just confused. Any ideas? This is on debian/sid. GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude> import Data.Graph.Inductive.Example Prelude Data.Graph.Inductive.Example> star 6 <interactive>:1:0: Ambiguous type variable `gr' in the constraint: `Data.Graph.Inductive.Graph.Graph gr' arising from a use of `star' at <interactive>:1:0-5 Probable fix: add a type signature that fixes these type variable(s) Prelude Data.Graph.Inductive.Example>

2 1

ANNOUNCE: vector 0.1 (efficient arrays with lots of fusion)
by Roman Leshchinskiy 12 Jul '08

12 Jul '08

Hi all, the vector library will eventually provide fast, Int-indexed arrays with a powerful fusion framework. It's very immature at the moment (I haven't tested most of the code) and implements just a few combinators but I thought releasing early wouldn't hurt. Use at your own risk and expect things to break horribly! What it provides: * Boxed and unboxed arrays with a generic interface and a very basic set of combinators. * A powerful loop fusion framework. It is based on stream fusion but already goes beyond that (in particular, it can do some things in-place) and will be significantly extended in the future. * Extensibility. * Rudimentary documentation. * Bugs. The code is based on the DPH libraries but is much more generic and a *lot* simpler. This has only been made possible by the tremendous progress in GHC's simplifier in the recent months/years (thanks Simon!). Consequently, you'll need a recent development version of GHC to build this, 6.8 won't work. It might be able to compile the library but you'll get terrible code, much worse than with lists. If you want to try it out, compile with -O2 -fno-spec-constr-count and please don't forget to let me know about things that didn't work (or, miraculously, did). Grab it from http://hackage.haskell.org/cgi-bin/hackage-scripts/package/vector or darcs get http://darcs.haskell.org/vector Again, special thanks to Simon for doing such a wonderful job with the optimiser. Enjoy, Roman

4 4

Template Haskell and haskell-src-exts
by ChrisK 12 Jul '08

12 Jul '08

Hi, Can one represent the ''Type template Haskell syntax of $( makeMergeable ''FileDescriptorProto ) in haskell-src.exts Language.Haskell.Exts.Syntax ? And what are the HsReify data (e.g. HsReifyType and HsReifyDecl and HsReifyFixity )? I don't see any pretty print capability to produce the ''Type so I am wondering what else I might use...

3 2