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)
I found myself reaching for the internals when implementing a
Crosswalk
instance forMap
: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 reasoninsertMin
is not exported.Of course, there are plenty of ways to write this function differently, including:
link k v Tip r = insertMin k v r
Using only
link
andlink2
by supplyingTip
whenever the respective subtree is missing:Not using Internal at all, but rather doing
toAscList
beforehand andfromDistinctAscList
afterwards -- but I am not sure how well this performs in comparison.