Data.Map.Internal does not export insertMin

[mniip]

I found myself reaching for the internals when implementing a Crosswalk instance for Map:

{- cabal:
build-depends: base, containers, these, semialign
-}
{-# LANGUAGE GHC2021, LambdaCase #-}
import Data.Map (Map)
import Data.Map.Internal qualified as Map
import Data.These
import Data.Semialign
import Data.Crosswalk

instance Crosswalk (Map k) where
  crosswalk :: Align f => (a -> f b) -> Map k a -> f (Map k b)
  crosswalk _ Map.Tip = nil
  crosswalk f (Map.Bin _ k v l r)
    = assemble k <$> (crosswalk f l `align` f v `align` crosswalk f r)

assemble :: k -> These (These (Map k a) a) (Map k a) -> Map k a
assemble k = \case
  This (This l) -> l
  This (That v) -> Map.singleton k v
  That r -> r

  These (That v) r -> Map.insertMin k v r -- ?
  This (These l v) -> Map.insertMax k v l
  These (This l) r -> Map.link2 l r

  These (These l v) r -> Map.link k v l r

The function assemble represents a general merging operation handling cases where left subtree, right subtree, and the bin's value may or may not be missing (although not all 3 missing simultaneously: empty maps follow an altogether different code path).

Data.Map.Internal has all the necessary functions for a straightforward and exact implementation of these merges (not doing extra work when a given part is missing), but for some reason insertMin is not exported.

Of course, there are plenty of ways to write this function differently, including:

• Using the fact that link k v Tip r = insertMin k v r
• Using only link and link2 by supplying Tip whenever the respective subtree is missing:

  import Data.These.Combinators
  import Data.Maybe
  
  assemble :: k -> These (These (Map k a) a) (Map k a) -> Map k a
  assemble k t = case justThere =<< justHere t of
    Nothing -> Map.link2 l r
    Just v -> Map.link k v l r
    where
      l = fromMaybe Map.empty (justHere =<< justHere t)
      r = fromMaybe Map.empty (justThere t)

• Not using Internal at all, but rather doing toAscList beforehand and fromDistinctAscList afterwards -- but I am not sure how well this performs in comparison.

  import Data.Functor.Compose
  
  instance Crosswalk (Map k) where
    crosswalk f m = Map.fromDistinctAscList . getCompose
      <$> crosswalk f (Compose $ Map.toAscList m)

[meooow25]

Seems odd that insertMax is exported but not insertMin.
For Set neither is exported.

I can certainly see these being useful when working with internals, maybe we should export them.
link k v Tip r is the next best thing, as you noted.

The last option is also worth considering if it is close enough in performance, then you're not tied to the library internals.