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

[Dan Piponi]

On 8/20/07, David Ritchie MacIver <david.maciver at gmail.com> wrote:
> I was playing with some code for compiling regular expressions to finite
> state machines and I ran into the following problem.

I've met exactly the same problem myself and you got me interested in it again.

I think the tricky part isn't so much the knot-tying, but the fact
that you need a high performance Map-like datastructure that doesn't
die the way Data.Map.fromList would if you gave it an infinite list as
argument.

One approach might be to replace Map k a with something like a

data UltraLazyMap k a = ULM (Map k a) [(k,a)]

The idea is that the Map part is built only as needed and the list
part represents the elements not yet inserted into the tree. When you
come to perform a lookup you first look in the Map part. If you don't
find what you want there you start looking through the list (assuming
that when you come to do lookups, every key you need eventually
appears at least once in the list). Each time you look at a list
element you remove it from the list and insert it into the tree. That
way you never try to build an "infinite" tree and instead grow it as
needed. This would have a similar amortised performance as a regular
Map, but the price is that lookups change the structure and so you
need mutable state. But that's OK, you just stick all of your code in
a State monad.

I don't know if that State monad would ultimately mess up any attempt
to eventually tie your knots, and I probably won't have time to try
coding this up at lest until the weekend. So take all of this with a
pinch of salt :-)

Good luck! :-)

And if that doesn't work, I also have another approach I'm thinking about...
--
Dan