Rewrite rules for Data.Map.Merge.Lazy interface

[endgame]

There are some obvious specialisations for Data.Semialign.Diff.diff and Data.Semialign.Diff.diffNoEq, using the high-perfomance interface in Data.Map.Merge.Lazy:

diffMap
  :: ( AsEmpty p
     , At p
     , Eq a
     , Index p ~ k
     , IxValue p ~ Maybe a
     , Ord k
     )
  => Map k a
  -> Map k a
  -> p

diffMapToMap :: (Ord k, Eq a) => Map k a -> Map k a -> Map k (Maybe a)

And some rewrite rules:

{-# NOINLINE [0] diff #-}
{-# RULES

"diff/MapToMap" [2]
  forall (m :: Ord k => Map k a) n.
  diff m n = diffMapToMap m n

"diff/Map" [1]
  forall (m :: Ord k => Map k a) n.
  diff m n = diffMap m n

#-}

Using inspection-testing and this code:

test :: Map String (Maybe Int)
test = diff (Map.fromList [("a", 1), ("b", 2)]) (Map.fromList [("a", 3), ("c", 4)])

$(inspect $ coreOf 'test)

It appears that neither rewrite rule is firing.

There are likely similar rules available for patching maps using maps, if I can get them to fire.

[jwaldmann]

Interesting problem! I was trying

{-# RULES "diff/MapToMap"  diff = diffMapToMap  #-}

(expecting it to fire when the types match) but ghc says

rules.hs:9:35: error:
    • Could not deduce (Ord i) arising from a use of ‘diffMapToMap’
      from the context: (Control.Lens.Indexed.FoldableWithIndex
                           i (Map i),
                         semialign-1:Data.Semialign.Internal.Semialign (Map i), Eq a,
                         Control.Lens.Empty.AsEmpty (Map i (Maybe a)), At (Map i (Maybe a)),
                         Index (Map i (Maybe a)) ~ i, IxValue (Map i (Maybe a)) ~ Maybe a)
        bound by the RULE "diff/MapToMap" at rules.hs:9:11-46
      Possible fix:
        add (Ord i) to the context of the RULE "diff/MapToMap"

How can I even change "the context of the rule"? I cannot write a type for the rule - only for variables used in the rule?

[jwaldmann]

Note that this rule does fire (for your test case mentioned above)

"diff/Map@String" 
  forall (m :: Map String a) n .
  diff m n = diffMap m n

I think the problem is discussed here https://stackoverflow.com/questions/19745038/ghc-rewrite-rule-specialising-a-function-for-a-type-class

[endgame]

Thanks for lending a hand. Following this other SO question, GHC seems to accept it if I add a context to the type variable like this:

"diff/MapToMap"
  forall (m :: Ord k => Map k a) n.
  diff m n = diffMapToMap m n

However, I don't think it is firing. This could be because:

1. I'm reading the outputs incorrectly (how are you verifying rewrite rule firings? This is a new area for me);
2. Something else goes wrong when we try to go polymorphic; or
3. I got the phase annotations completely wrong in my earlier attempt.

I'd appreciate any more help you can offer.

[jwaldmann]

how are you verifying rewrite rule firings?

"-ddump-rule-firings" etc., see https://downloads.haskell.org/~ghc/8.8.1/docs/html/users_guide/glasgow_exts.html#rewrite-rules

[endgame]

That SO question is good reading material, thanks for the link. I think that specialisation happens before the polymorphic rewrite rule gets a look-in. This might be why the monomorphic rewrite rule works.

The SO question referenced the ifcxt library. It looks promising but doesn't compile for me on newer GHC, so it might be time to do some yak-shaving.