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

Stefan O'Rear stefanor at cox.net
Mon Aug 20 18:53:30 EDT 2007

On Mon, Aug 20, 2007 at 03:39:28PM -0700, Dan Piponi wrote:
> 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...

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 r $ 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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070820/b56ebaa4/attachment.bin

More information about the Haskell-Cafe mailing list