Add `spanAntitoneM`

[masaeedu]

spanAntitone :: (k -> Bool) -> Map k a -> (Map k a, Map k a) is a handy way to "bisect" arbitrary data in the git bisect sense. Just stick your data in a Map, then use spanAntitone to find the crossover point.

Sometimes the antitone predicate cannot be defined purely though (maybe it involves interactivity, or consulting a database, or whatever), and in such cases I feel like it'd be handy to have this slight variation:

spanAntitoneM :: Monad m => (k -> m Bool) -> Map k a -> m (Map k a, Map k a)

The rule for the predicate can still be specified as j < k implies (>=) <$> p j <*> p k == f True, for some f :: forall x. x -> m x (roughly, (>=) <$> p j <*> p k always "resolves" to True).

[masaeedu]

Without having any understanding of the implications for "pure performance", but being reasonably confident it evaluates the predicate as frugally as spanAntitone does, here is a cargo-culted implementation of spanAntitoneM:

spanAntitoneM :: Monad m => (k -> m Bool) -> Map k a -> m (Map k a, Map k a)
spanAntitoneM p0 m = toPair <$> go p0 m
  where
    go _ Tip = pure $ Tip :*: Tip
    go p (Bin _ kx x l r) = do
      test <- p kx
      if test
        then do
          u :*: v <- go p r
          pure $ link kx x l u :*: v
        else do
          u :*: v <- go p l
          pure $ u :*: link kx x v r

[treeowl]

This looks like a valuable utility. If we were to add it, I'd want it to be from some sort of Unsafe module. The issue is that the specific actions performed would depend on how the tree happens to be balanced.

[masaeedu]

The issue is that the specific actions performed would depend on how the tree happens to be balanced.

I would expect as much, but I can see how mileage may vary. Would the Data.Map.Internal module work for this, or would this warrant a new module entirely?

[treeowl]

I personally think it would be nice to have a more "public" unsafe module, both for this and other similarly abstraction-breaking operations.