[Haskell-cafe] Spine-lazy "multiqueue"
Luke Palmer
lrpalmer at gmail.com
Wed Oct 22 14:34:39 EDT 2008
On Wed, Oct 22, 2008 at 3:14 AM, Ryan Ingram <ryani.spam at gmail.com> wrote:
> Here's an infinite structure with logarithmic access time with natural
> numbers for keys.
>
> It's not particularily efficient for a sparse map, but if the maximum
> used key is linear in the size of your problem, it gives log(n) access
> time.
>
> However, an infinite fold of insert is still _|_; you have to
> construct with "fromAscList" if you want to initialize the map with
> some infinite data. This is because otherwise there is no way to know
> that we are "done" with the head of the map; some later value in the
> list might replace it. The use of the ascending list lets us know
> after we've passed key n, we can construct the map up to at least n.
Well, actually the infinite fold of inserts is possible, since:
lookup k (insert k x (insert k y)) = x
So the "earlier" one overwrites the "later" one in a right fold.
>
> *NatMap> lookup (fromAscList [(v,v) | v <- [0..]]) 42
> Just 42
>
>> module NatMap where
>> import Prelude hiding (lookup)
>
>> data NatMap v = NatMap (Maybe v) (NatMap v) (NatMap v)
Thanks for the ideas and inspiration everybody. I was so locked into
the Ord constraint that I didn't see the obvious trie alternative.
I ended up going with something very similar to Ryan's suggestion.
module NatTrie (NatTrie, uniform, modify, lookup, union) where
import Prelude hiding (lookup)
data NatTrie v = NatTrie { ntVal :: v, nt0 :: NatTrie v, nt1 :: NatTrie v }
uniform x = let r = NatTrie x r r in r
modify = go . bits
where
go [] ~(NatTrie x l r) = NatTrie (f x) l r
go (False:xs) ~(NatTrie x l r) = NatTrie x (go xs l) r
go (True;xs) ~(NatTrie x l r) = NatTrie x l (go xs r)
lookup = go . bits
where
go [] = ntVal
go (False:xs) = go xs . nt0
go (True:xs) = go xs . nt1
union f (NatTrie x l r) (NatTrie x' l' r')
= NatTrie (F x x') (union f l l') (union f r r')
bits x
| x < 0 = error "negative key"
| otherwise = natBits x
natBits 0 = []
natBits x = toBool r : natBits q
where
(q,r) = quotRem x 2
toBool = (== 1)
This does supports the infinite fold. I put the main four operations
in class with a fundep for the key, but I'm not totally happy with it.
In particular, I couldn't even write SumTrie (with Eithers as keys)
without undecidable instances. Ideas for how to make such tries
composable would encourage me to release a hackage module :-)
Thanks everybody!
Luke
More information about the Haskell-Cafe
mailing list