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

On Mon, Aug 20, 2007 at 03:39:28PM -0700, Dan Piponi wrote:

On 8/20/07, David Ritchie MacIver 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...

You could also just build the map lazily. data Map k a = Fork k a (Map k a) (Map k a) | Leaf ... insertMany (Fork k v l r) xs = Fork k v (insertMany l $ filter (k) xs) insertMany Leaf [] = Leaf insertMany Leaf ((k,v):xs) = insertMany (Fork k v Leaf Leaf) xs Unfortunately it's not at all clear how to add balancing, other than access-time mutation. Stefan