[containers] Proposal: Add traverseKeys, traverseKeysWith, traverseKeysMonotonic to Data.Map

Akio Takano tkn.akio at gmail.com
Wed Mar 12 00:02:25 UTC 2014


On Tue, Mar 11, 2014 at 9:38 PM, Edward Kmett <ekmett at gmail.com> wrote:
> What does it mean to talk about a monotonic function with Applicative
> side-effects (a -> f b) in this setting?
> I'm not able to determine how laws for such a beast work.

Would a definition like the below help?

A function (m :: a -> f b) is monotonic iff for all finite (xs ::
[a]), the following two expressions are equivalent:

isMonotonic <$> traverse (\x -> (x,) <$> m x) xs
True <$ traverse (\x -> (x,) <$> m x) xs


isMonotonic :: (Ord a, Ord b) => [(a, b)] -> Bool
isMonotonic xs = and $ zipWith (<=) sorted (drop 1 sorted)
  where sorted = sortBy (compare `on` fst) xs

-- Takano Akio

More information about the Libraries mailing list