Data.Map/Data.IntMap additional features

[Louis Wasserman]

Hey all,

Amid the discussion of inconsistencies between Data.IntMap and Data.Map, I
thought I'd throw in some more ideas.  I've been working on a rather
thorough generalized trie map implementation, which has done nothing if not
force me to make really very generalized signatures for every method offered
by Data.Map, etc.  Some of these generalizations are, I think, independently
useful, and I wanted to throw them out for discussion before creating a
ticket.

A function that I call extract/extractWith/extractWithKey:

extractWithKey :: Alternative f => (k -> a -> f (z, Maybe a)) -> Map k a ->
f (z, Map k a)

which is actually defined as follows:

> extractWithKey f (Bin n kx x l r) = fmap (\ (z, l') -> (z, Bin n kx x l'
r)) (extractWithKey f l) <|>
>      fmap (\ (z, x') -> (z, maybe (glue l r) (\ xx -> bin kx xx l r) x'))
(f kx x) <|> fmap (\ (z, r') -> (z, Bin n kx x l r')) (extractWithKey f r)
> extractWithKey f Nil = empty

If m is fromList [(k1, x1), (k2, x2), ..., (kn, xn)], then

> fst <$> extractWithKey (\ k a -> pure (f k a, <whatever>)) m == f k1 x1
<|> f k2 x2 <|> ... <|> f kn xn

and then the second component is obtained by modifying a single element
accordingly and taking the alternative over every element to choose from.

A few observations:  with an appropriate Alternative instance for
Data.Monoid.First and Data.Monoid.Last,
> extractWithKey (\ k a -> return ((k, a), Nothing)) m == First
(minViewWithKey m)

so this generalizes minViewWithKey and maxViewWithKey according to the First
Alternative instance.  (Note that the extractWithKey implementation is also
O(log n), because the natural First Alternative instance will ignore the
irrelevant pathways lazily,

> extractWithKey (\ k a -> if p k a then pure ((k, a), Nothing) else empty)

in the First Alternative instance, will extract the first element of the map
that satisfies p, or will return Nothing if there is no such element, and
will take O(i) time to do so if the first satisfying element is at index i,

> mapPermK :: Int -> Map k a -> [[(k, a)]]
> mapPermK 0 m = [[]]
> mapPermK (n+1) m = do    ((k1, a1), m') <- extractWithKey (\ k a -> return
((k, a), Nothing)) m
>                                         liftM ((k1, a1) :) (mapPermK n m)

returns a list of all permutations of k distinct associations from the map
m, and does it exactly as lazily as one might hope.  (Generating
combinations efficiently is somewhat harder, and I'm not sure this approach
grants much in the way of additional efficiency beyond a couple other
approaches I can think of.)

In any event, you get the idea: this is a preposterously general method,
albeit difficult to describe.  It is moderately easier to describe the
individual projections, which I name arbitrarily,

about :: Alternative f => (k -> a -> f z) -> Map k a -> f z
modify :: Alternative f => (k -> a -> f (Maybe a)) -> Map k a -> f (Map k a)

Finally, I'll define neighborhood.  Internally, neighborhood has the
signature

neighborhood :: Ord k => k -> Map k a -> (Last (k, a), Maybe a, First (k,
a))

where neighborhood k m = (sup [(k', a) | k' < k], lookup k m, inf [(k', a) |
k' > k]) == case splitLookup k m of (mL, v, mR) -> (fmap fst (maxViewWithKey
mL), v, fmap fst (minViewWithKey mR))

is defined as follows:

neighborhood k Tip = (empty, empty, empty)
neighborhood k (Bin _ kx x l r) = case compare k kx of
LT -> case neighborhood k l of
(lb, v, ub) -> (lb, v, ub <|> pure (kx, x))
EQ -> (Last (fmap fst (maxViewWithKey l)), Just x, First (fmap fst
(minViewWithKey r)))
-- we can also use the *about* generalization here, since we only need the
minimum and maximum associations
GT -> case neighborhood k r of
(lb, v, ub) -> (pure (kx, x) <|> lb, v, ub)

Using MonadPlus or Alternative instances for First and Last are rather
elegant here, and I strongly support adding their Applicative, Alternative,
Monad, and MonadPlus instances to base.

Louis Wasserman
wasserman.louis at gmail.com
http://profiles.google.com/wasserman.louis
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20091103/2589a99f/attachment.html