Haskell 重写规则和函数组合

Question

为什么 haskell 根据函数组合技术和长度需要多个重写规则？有办法避免这种情况吗？

例如，给定以下代码...

{-# RULES
"f/f" forall a. f ( f a ) = 4*a
  #-}
f a = 2 * a

这适用于

test1 = f ( f 1 )

但是我们需要添加一个规则

test2 = f . f $ 1

并

test3 = f $ f 1

留下以下规则

{-# RULES
"f/f1" forall a. f ( f a ) = 4 * a
"f/f2" forall a. f . f $ a  = 4 * a
"f/f3" forall a. f $ f $ a  = 4 * a
   #-}

但是，当我们将它们串在一起或使用某些其他形式的组合时，规则不会触发。

test4 = f . f . f $ 1
test5 = f $ f $ f $ 1
test6 = f $ 1

这是为什么呢？我是否必须为每种可能的实现编写重写规则？

Answer 1

在许多情况下，规则不会触发，因为非常简单的函数 f 在规则有机会触发之前被内联。如果您延迟内联，

{-# INLINE [1] f #-}

则应在所有这些情况下触发该规则

{-# RULES "f/f" forall a. f (f a) = 4*a #-}

（此处适用于 7.2.2 和 7.4.1）。

原因是规则匹配器并不过分复杂，它只匹配具有规则语法形式的表达式（不完全正确，规则主体也经历了一些规范化）。表达式 f $ f 3 或 f 。 f$4 与规则的语法形式不匹配。为了使规则匹配，必须进行一些重写，在规则与表达式匹配之前必须内联 ($) 和 (.) 。但是，如果您不阻止 f 在简化器的第一阶段内联，它会在与 ($) 和 相同的运行中被其主体替换(.) 是内联的，因此在下一次迭代中，简化器不再看到 f，它只看到 2*(2*x)，这不符合规则。

Answer 2

我本以为这在默认情况下会起作用，但是您可以添加两个以上的重写规则来使 ./$ 简化为 lambdas/application，以便这将始终匹配：

{-# RULES
"f/f" forall a. f ( f a ) = 4*a

"app" forall f x. f $ x = f x
"comp" forall f g. f . g = (\x -> f (g x))
  #-}

f a = 3 * a -- make this 3*a so can see the difference

测试：

main = do
    print (f . f $ 1)
    print (f (f 1))
    print (f $ f 1)
    print (f $ f $ 1)
    print (f $ f $ f $ f $ 1)
    print (f . f . f . f $ 1)
    print (f $ f $ f $ 1)
    print (f . f . f $ 1)
    print (f $ 1)

输出：

4
4
4
4
16
16
12
12
3

这也适用于某些（但是由于其他重写规则，并非全部）更模糊的情况。例如，所有这些都将起作用：

mapf x = map f $ map f $ [x]
mapf' x = map (f.f) $ [x]
mapf'' x = map (\x -> f (f x)) $ [x]