Haskell：Continuation Passing Styleで階乗を完全に定義する問題

Question

Functional Programming、Haskell、Continuation Passing Styleを1つの大きなブロブに追加しようとしていました。

thisによると、私は次の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）」の部分についてはよく分かりません- あれは正しいですか？

Answer 1

かなり正確ではありません（私にとってはコンパイルされません）。値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))) 

次

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

これは、同一の（しかし、より鈍角）であるが、私はここに変化するであろういくつかのものがあります。まず、idは標準関数なので、再定義する必要はありません。第2に、これらの例では、「n + kパターン」を使用しています。このパターンは、GHCではデフォルトでは使用できません。 「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です。