9

为什么 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

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

4

2 回答 2

13

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

{-# INLINE [1] f #-}

规则

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

应该针对所有这些情况触发（在此处使用 7.2.2 和 7.4.1）。

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

于 2012-02-13T00:04:44.267 回答
3

我原以为这在默认情况下会起作用，但是您可以添加另外两个重写规则以使 ./$ 减少到 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]
于 2012-02-12T23:49:24.567 回答