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

[David Ritchie MacIver]

ajb at spamcop.net wrote:
> 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

I'd be astonished if yours didn't beat mine hands down. I'm just putting 
this together as an exercise to help me figure out some of the areas 
where my Haskell knowledge is extremely weak. It's totally unoptimised.