== Notes on the implementation of rewrite RULEs in GHC == === Looking through lets === We recently made the rule-matcher able to "look through" lets, thus {{{ RULE f (g x) = rhs Expression: f (let v = e in g v) }}} The rule will still match, giving {{{ let v = e in rhs[v/x] }}} === Dictionaries === Suppose we have {{{ RULE f (g x) = rhs f :: Ord a => a -> a foo :: Int -> Int foo x = f (g x) }}} Then we tend to get {{{ f_79 :: Int -> Int f_79 = f Int dOrdInt foo :: Int -> Int foo = \x -> f_79 (g x) }}} Lo, the f/g RULE cannot fire. Current solution: use {{{-fno-method-sharing}}} to get {{{ foo :: Int -> Int foo = \x -> f Int dOrdInt (g x) }}} But we found other examples where this wasn't enough. Code is below. The solution is: use {{{-fdicts-cheap}}}, which makes dictionary construction look really cheap. Example of when -fno-method-sharing isn't enough. {{{ module Foo where data UArr a = UArr [a] class UA a where ua :: [a] -> [a] instance UA Int where ua xs = xs class DT a where foo :: a -> a bar :: a -> a instance DT Int where foo x = x bar x = x instance (DT a, DT b) => DT (a,b) where foo x = x bar x = x instance UA a => DT (UArr a) where foo x = x bar x = x data Dist a = Dist a mapD :: (DT a, DT b) => (a -> b) -> Dist a -> Dist b {-# INLINE [1] mapD #-} mapD f (Dist x) = Dist (f x) zipWithD :: (DT a, DT b, DT c) => (a -> b -> c) -> Dist a -> Dist b -> Dist c {-# INLINE zipWithD #-} zipWithD f (Dist x) (Dist y) = mapD (uncurry f) (Dist (x,y)) splitD :: UA a => UArr a -> Dist (UArr a) {-# INLINE [1] splitD #-} splitD x = zipWithD const (Dist x) (Dist x) joinD :: UA a => Dist (UArr a) -> UArr a {-# INLINE [1] joinD #-} joinD (Dist x) = x {-# RULES "split/join" forall x. splitD (joinD x) = x #-} ------ module Bar where import Foo foo :: Dist (UArr Int) -> Dist (UArr Int) foo = splitD . joinD ------ Compared to the previous version, the important differences are - the class UA and the instance DT (UArr a) which builds a DT dictionary from an UA one, - splitD . joinD instead of splitD (joinD x) in foo. With this, we get ------ 15 splitD :: UA a => UArr a -> Dist (UArr a) {- Arity: 1 HasNoCafRefs Strictness: A Inline: [1] Unfolding: (__inline_me (\ @ a \$dUA :: UA a -> let { \$dDT :: DT (UArr a) = \$f1 @ a \$dUA } in \ x :: UArr a -> zipWithD @ (UArr a) @ (UArr a) @ (UArr a) \$dDT \$dDT \$dDT (GHC.Base.const @ (UArr a) @ (UArr a)) (Dist @ (UArr a) x) (Dist @ (UArr a) x))) -} ------ and the rule doesn't fire. Nor does it with foo x = splitD \$ joinD x But it *does* fire with foo x = splitD (joinD x) despite the arity of splitD. Very strange... Roman }}}