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、同じ実行でその本体に置き換えられ、($)インライン(.)化されるため、次の反復では、単純化器はfもう見えません2*(2*x)。これはルールに一致しません。

于 2012-02-13T00:04:44.267 に答える
3

これはデフォルトで機能すると思っていましたが、さらに 2 つの書き換えルールを追加して、./$ をラムダ/アプリケーションに減らして、これが常に一致するようにすることができます。

{-# 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 に答える