On Mon, Aug 20, 2007 at 03:39:28PM -0700, Dan Piponi wrote: > On 8/20/07, David Ritchie MacIver <[EMAIL PROTECTED]> 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.
Stefan
signature.asc
Description: Digital signature
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
