2

私は関数型プログラミング、Haskell、継続渡しスタイルを1つの大きなブロブで理解しようとしてきましたが、構造化/OOPのバックグラウンドが苦労しています。

これによると、私は次のことがCPSスタイルの階乗の正しい定義であるべきだと理解しています。

factorial n = fact n id where id = \x -> x
    fact 0 cont = cont n
    fact (n+1) cont = fact n * (n + 1)

しかし、最後の「*（n + 1）」の部分についてはよくわかりません-それは正しいですか？

4

1 に答える 1

6

それは完全には正しくありません（そして私のためにコンパイルされません）。値n+1は正しいですが、まったく正しい方法で使用されていません。多分あなたはオペレーターセクションを使うつもりでしたか？

factorial n' = fact n' id
 where
  id = \x -> x
  fact 0 cont = cont 1
  fact (n+1) cont = fact n (cont . (* (n+1)))

これは、次のものと同じです（ただし、より鈍感です）。

factorial n' = fact n' id
 where
  id = \x -> x
  fact 0 cont = cont 1
  fact (n+1) cont = fact n (\ret -> cont (ret * (n+1)) )

ここで変更することがいくつかあります。まず、idこれは標準関数なので、再定義する必要はありません。次に、これらの例では「n + kパターン」を使用しています。これは、GHCではデフォルトでIIRCが使用できなくなりました。「n+kパターン」の代わりに、通常のパターン変数を使用できます。1ベースケースに使用したことに注意してください。これは、からカウントダウンするかどうかを推論するのが簡単nであり、継続関数は計算内の各ステップで適用する必要があります（誘導ステップから削除しました）。これらを念頭に置いて、あなたは書くことができます

factorial n' = fact n' id
 where
  fact 0 cont = cont 1
  fact n cont = fact (n-1) (cont . (* n))

これは多かれ少なかれ慣用的だと思います。

編集：私は個人的にn + kパターンが好きではありませんが、それらを説明するのに少し時間がかかると思いました。ベースケースと帰納法のステップを使った数学的帰納法を考えると、わかりやすいと思います。基本ケースはfact 0 ...です。次に、基本ステップから進んで他の値を定義します。「いずれの場合も、この関係によってfact n k決定します。」fact (n+1) kこれは、私が通常のパターン変数を考える方法とは異なります。つまり、ここでのボトムアップではなくトップダウンですが、それは動機と、一部の人々がスタイルを好む理由を説明していると思います。

n + kパターンが気に入らない理由は、定義が雑然としているからですが、YMMVです。

于 2011-01-23T14:16:38.253 に答える