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 Regards, apfelmus