Generic tries (long)
apfelmus at quantentunnel.de
Sun Jun 22 07:10:04 EDT 2008
Adrian Hey wrote:
> For the Data.Map clone I wrote something like this ..
> -- An "open" map (this is abstract)
> data OMap k a = OMap k (Maybe a) (Map k a) Int#
> -- This is just a lookup that encodes the path taken as an unboxed Int
> open :: Ord k => k -> Map k a -> OMap k a
> -- Get the current associated value (if any)
> read :: OMap k a -> Maybe a
> -- Change the current associated value and close the new map
> -- This is v.fast. No comparisons, and no balance checking or
> -- rebalancing either if this is a substitution rather than an
> -- insertion.
> write :: a -> OMap k a -> Map k a
> -- Delete the current association (if any) and close the new map
> -- This is nop if there is no current association
> delete :: OMap k a -> Map k a
> -- Not really needed if original map is still in scope
> close :: OMap k a -> Map k a
> I think it depends if this can be implemented without burning
> significant extra heap in either focus or the resulting g function.
> Generally zippers do require quite a bit of heap (proportional to
> trie/tree depth).
The OMap type is like a zipper, the Int# encodes the path. I don't know
whether the Int# (which should be a !Int with an UNPACK pragma) really
gains anything compared to a list, only benchmarks can tell. Fretting
about it seems like an irrelevant micro-optimization to me.
In any case, focus can easily be implemented in terms of OMap :
focus :: k -> map a -> (Maybe a, Maybe a -> map a)
focus k m = (read z, maybe (delete z) (`write` z))
where z = open k m
So any efficient implementation for OMap gives an efficient
implementation for focus . And vice-versa
type OMap k a = (Maybe a, Maybe a -> Map k a)
open = focus
read = fst
write x = ($ Just x ) . snd
delete = ($ Nothing) . snd
More information about the Libraries