2

私が理解しようとしている質問の一部には、これが含まれます。

twice (twice) f x , where twice == lambda f x . f (f x)

私はその置換を行う方法とそれが何を意味するのかを理解しようとしています。

私の理解では、(lambdaxy。x+ y)2 3 == 2 + 3 == 5. 2回(2回)が何を意味するのか、またはf(fx)がわかりません。

4

1 に答える 1

2

これを見る2つの方法。

ベータ削減の機械的応用

FX形式のサブタームを拡張するだけで、これを機械的に解決できtwiceます。このタームを使用すると、最終的に2回の出現をすべて排除できますが、間違いを避けるためにラムダ計算の構文木を本当に理解するように注意する必要があります。

twice2つの引数を取るので、式はに適用されるtwice (twice) f xredexです。(redexは、残りの用語とは関係なく削減できるサブ用語です)。twice (twice) fx

redexのの定義をtwice展開します:twice (twice) f x -> twice (twice f)

これを元の用語に置き換えてgetを取得します。これは、拡張して取得twice (twice f) xできる別のredexです(このステップの括弧に注意してください)。twicetwice f (twice f x)

twiceここで展開できる2つのredexeがあります。角かっこ内の1つを展開すると、少し簡単になります。twice f (f (f x))これを再び展開して、を与えることができますf (f (f (f x)))

抽象化による2回の意味論

高階コンビネータ、関数合成用の「○」インフィックスコンビネータにアピールすることで、より直感的なレベルで何が起こっているかを確認できます。

f ○ g = lambda x. f (g x)

両方が同じ正規形に拡張されることを確認するのは簡単です。つまり、twice f x拡張性によって、次のようになります。(f ○ f) xf (f x),

twice f = f ○ f

これを使用すると、非常に簡単に拡張できます。最初twiceに、構成コンビネータを優先して削除します。

twice (twice) f x
= (twice ○ twice)  f x
= (twice (twice f)) x         /* expand out '○' */
= (twice (f ○ f)) x
= ((f ○ f) ○ (f ○ f)) x

次に「○」を展開します。

= (f ○ f) ((f ○ f) x)
= (f ○ f) (f (f x))
= (f (f (f (f x))))

最初に「○」演算子を含む用語に展開し、次にこれらの演算子を展開するため、これはより多くの拡張ステップですが、ステップはより単純で直感的なものであり、実行していることを誤解する可能性が低くなります。「○」はHaskellで広く使用されている標準的な演算子であり、慣れる価値があります。

于 2012-12-30T17:00:53.147 に答える