Hey all,<br><br>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.<br>
<br>A function that I call extract/extractWith/extractWithKey:<br><br>extractWithKey :: Alternative f => (k -> a -> f (z, Maybe a)) -> Map k a -> f (z, Map k a)<br><br>which is actually defined as follows:<br>
<br>> extractWithKey f (Bin n kx x l r) = fmap (\ (z, l') -> (z, Bin n kx x l' r)) (extractWithKey f l) <|><br>> 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)<br>
> extractWithKey f Nil = empty<br><div style="margin-left: 40px;"><br></div>If m is fromList [(k1, x1), (k2, x2), ..., (kn, xn)], then <br><br>> fst <$> extractWithKey (\ k a -> pure (f k a, <whatever>)) m == f k1 x1 <|> f k2 x2 <|> ... <|> f kn xn<br>
<br>and then the second component is obtained by modifying a single element accordingly and taking the alternative over every element to choose from.<br><br>A few observations: with an appropriate Alternative instance for Data.Monoid.First and Data.Monoid.Last,<br>
> extractWithKey (\ k a -> return ((k, a), Nothing)) m == First (minViewWithKey m)<br><br>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,<br>
<br>> extractWithKey (\ k a -> if p k a then pure ((k, a), Nothing) else empty)<br><br>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,<br>
<br>> mapPermK :: Int -> Map k a -> [[(k, a)]]<br>> mapPermK 0 m = [[]]<br>> mapPermK (n+1) m = do ((k1, a1), m') <- extractWithKey (\ k a -> return ((k, a), Nothing)) m<br>> liftM ((k1, a1) :) (mapPermK n m)<br>
<br>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.)<br>
<br>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,<br><br>about :: Alternative f => (k -> a -> f z) -> Map k a -> f z<br>
modify :: Alternative f => (k -> a -> f (Maybe a)) -> Map k a -> f (Map k a)<br><br>Finally, I'll define neighborhood. Internally, neighborhood has the signature<br><br>neighborhood :: Ord k => k -> Map k a -> (Last (k, a), Maybe a, First (k, a))<br>
<br>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))<br>
<br>is defined as follows:<br><br>neighborhood k Tip = (empty, empty, empty)<br>neighborhood k (Bin _ kx x l r) = case compare k kx of<br><div style="margin-left: 40px;">LT -> case neighborhood k l of<br><div style="margin-left: 40px;">
(lb, v, ub) -> (lb, v, ub <|> pure (kx, x))<br></div>EQ -> (Last (fmap fst (maxViewWithKey l)), Just x, First (fmap fst (minViewWithKey r)))<br><div style="margin-left: 40px;">-- we can also use the *about* generalization here, since we only need the minimum and maximum associations<br>
</div>GT -> case neighborhood k r of<br><div style="margin-left: 40px;">(lb, v, ub) -> (pure (kx, x) <|> lb, v, ub)<br></div></div><div style="margin-left: 40px;"><div style="margin-left: 40px;"><br></div></div>
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.<br><br clear="all">Louis Wasserman<br>
<a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br><a href="http://profiles.google.com/wasserman.louis">http://profiles.google.com/wasserman.louis</a><br>