Incorrect order of Applicative actions in mergeA when using filterAMissing

[j6carey]

-- The documentation for 'mergeA' says, '...mergeA will first "align" these
-- maps by key...Next, it will perform the actions in the actions list in
-- order from left to right.'
--
-- In particular, it asserts that the order of
-- 'Applicative' actions is derived from key order.
--
-- However, the effect of 'mergeA' when using 'filterAMissing'
-- depends upon accidents of how the map is balanced, apparently
-- because the action for the key-value pair stored directly in
-- an internal node is sequenced before the actions for both the
-- left and right branches, instead of being sequenced between them.

import qualified Data.Map.Lazy as L
import qualified Data.Map.Strict as S
import qualified Data.Map.Merge.Lazy as ML
import qualified Data.Map.Merge.Strict as MS

main :: IO ()
main = do
  do
    let left1L = L.singleton 0 'a' <> L.singleton 1 'b'
        left2L = L.singleton 1 'b' <> L.singleton 0 'a'
        onlyLeftL = ML.filterAMissing (\k v -> ([(k, v)], False))
        onlyRightL = ML.dropMissing
        bothL = ML.zipWithMatched (\_ x _ -> x)
    putStrLn "======== Lazy:"
    print $ left1L == left2L
    print $ ML.mergeA onlyLeftL onlyRightL bothL left1L L.empty
    print $ ML.mergeA onlyLeftL onlyRightL bothL left2L L.empty
  do
    let left1S = S.singleton 0 'a' <> S.singleton 1 'b'
        left2S = S.singleton 1 'b' <> S.singleton 0 'a'
        onlyLeftS = MS.filterAMissing (\k v -> ([(k, v)], False))
        onlyRightS = MS.dropMissing
        bothS = MS.zipWithMatched (\_ x _ -> x)
    putStrLn "======== Strict:"
    print $ left1S == left2S
    print $ MS.mergeA onlyLeftS onlyRightS bothS left1S S.empty
    print $ MS.mergeA onlyLeftS onlyRightS bothS left2S S.empty

{- Output:

   ======== Lazy:
   True
   ([(0,'a'),(1,'b')],fromList [])
   ([(1,'b'),(0,'a')],fromList [])
   ======== Strict:
   True
   ([(0,'a'),(1,'b')],fromList [])
   ([(1,'b'),(0,'a')],fromList [])

-}

[treeowl]

Uh oh ... do you think you could open a PR?

[j6carey]

Suggested fix in PR 1005.

[treeowl]

Fixed in #1005

[j6carey]

@treeowl , thanks!