これは少し遅れていることを私は知っています、そして答えはすでに受け入れられました。ただし、末尾再帰を作成するための適切なステップバイステップガイドは、OPまたはその他の人にとって興味深いものになる可能性があると思います。これが確かに私を助けてくれたいくつかの秘訣です。他の人が述べているように、素数を生成するためのより良い方法があるので、私は素数生成以外の単純な例を使用するつもりです。
いくつかからカウントダウンする整数のリストを作成するcount関数の素朴な実装を考えてみましょうn
。このバージョンは末尾再帰ではないため、長いリストの場合、スタックオーバーフロー例外が発生します。
let rec countDown = function
| 0 -> []
| n -> n :: countDown (n - 1)
(* ^
|... the cons operator is in the tail position
as such it is evaluated last. this drags
stack frames through subsequent recursive
calls *)
これを修正する1つの方法は、パラメーター化された関数を使用して継続渡しスタイルを適用することです。
let countDown' n =
let rec countDown n k =
match n with
| 0 -> k [] (* v--- this is continuation passing style *)
| n -> countDown (n - 1) (fun ns -> n :: k ns)
(* ^
|... the recursive call is now in tail position *)
countDown n (fun ns -> ns)
(* ^
|... and we initialize k with the identity function *)
次に、このパラメーター化された関数を特殊な表現にリファクタリングします。関数countDown'
が実際にカウントダウンしていないことに注意してください。これは、継続がいつ構築され、いつn > 0
評価されるかというアーティファクトですn = 0
。最初の例のようなものがあり、それを末尾再帰にする方法がわからない場合は、2番目の例を記述してから、それを最適化して関数パラメーターを削除することをお勧めしますk
。それは確かに読みやすさを向上させます。これは、2番目の例の最適化です。
let countDown'' n =
let rec countDown n ns =
match n with
| 0 -> List.rev ns (* reverse so we are actually counting down again *)
| n -> countDown (n - 1) (n :: ns)
countDown n []