[Haskell-cafe] "Tying the knot" with unknown keys

ajb at spamcop.net ajb at spamcop.net
Tue Aug 21 03:51:42 EDT 2007


G'day all.

Quoting David Ritchie MacIver <david.maciver at gmail.com>:

> I was playing with some code for compiling regular expressions to
> finite state machines and I ran into the following problem. I've solved
> it, but I'm not terribly happy with my solution and was wondering if
> someone could come up with a better one. :-)

Doing structural induction is quite viable, as you noted.

However, there are advantages to implementing explicit indirection.
The main one is memory usage.  Explicit indirection is much less
leak-prone, and you can easily share structures thanks to hash consing.

At any rate, I'm extremely curious as to how your code compares with
mine, performance-wise:

    http://www.ninebynine.org/Software/HaskellRDF/Dfa/Dfa.lhs

Cheers,
Andrew Bromage


More information about the Haskell-Cafe mailing list