2 
let rec f n =
    match n with
    | 0 | 1 | 2 -> 1
    | _ -> f (n - 2) + f (n - 3)

CPS やメモ化がなければ、どのように末尾再帰を行うことができるでしょうか?

4

3 に答える 3

4 
let f n = Seq.unfold (fun (x, y, z) -> Some(x, (y, z, x + y))) (1I, 1I, 1I)
          |> Seq.nth n

またはさらに良い：

let lambda (x, y, z) = x, (y, z, x + y)
let combinator = Seq.unfold (lambda >> Some) (1I, 1I, 1I)
let f n = combinator |> Seq.nth n

ここで何が起こっているかを知るには、このスニペットを参照してください。それはフィボナッチアルゴリズムを定義し、あなたのものは非常に似ています。

UPDここには3つのコンポーネントがあります。

  1. -番目の要素を取得するラムダ。i
  2. 再帰を実行するコンビネータi; と
  3. 実行全体を開始してから値を取得するラッパー（@Tomasのコードのようにトリプルから）。

あなたは末尾再帰コードを要求しましたが、実際には2つの方法があります。@ Tomasが行ったように独自のコンビネータを作成するか、Seq.unfold確かに末尾再帰である既存のコンビネータを利用します。letコード全体をステートメントのグループに分割できるため、2番目のアプローチを選択しました。

于 2012-09-17T19:47:12.447 に答える
4

@bytebuster による解決策は素晴らしいですが、彼はそれをどのように作成したかを説明していないため、この特定の問題を解決している場合にのみ役立ちます。ちなみに、数式はフィボナッチに少し似ていますが (完全ではありません) 、ループなしで分析的に計算できます(に隠されたループなしでもSeq.unfold)。

次の関数から始めました。

let rec f0 n = 
  match n with 
  | 0 | 1 | 2 -> 1 
  | _ -> f0 (n - 2) + f0 (n - 3)

この関数はf0引数n - 2と を呼び出すためn - 3、これらの値を知る必要があります。秘訣は動的プログラミング(メモ化を使用して実行できます) を使用することですが、メモ化を使用したくなかったので、手動で記述できます。

f1 nの現在値と 2 つの過去の値を含む 3 要素のタプルを返すを書くことができますf0。これは次のことを意味しf1 n = (f0 (n - 2), f0 (n - 1), f0 n)ます。

let rec f1 n = 
  match n with 
  | 0 -> (0, 0, 1)
  | 1 -> (0, 1, 1)
  | 2 -> (1, 1, 1)
  | _ -> 
    // Here we call `f1 (n - 1)` so we get values
    //   f0 (n - 3), f0 (n - 2), f0 (n - 1)
    let fm3, fm2, fm1 = (f1 (n - 1))
    (fm2, fm1, fm2 + fm3)

この関数は末尾再帰ではありませんが、自分自身を再帰的に 1 回だけ呼び出します。つまり、accumulator パラメーター パターンを使用できます。

let f2 n =
  let rec loop (fm3, fm2, fm1) n = 
    match n with 
    | 2 -> (fm3, fm2, fm1)
    | _ -> loop (fm2, fm1, fm2 + fm3) (n - 1)
  match n with
  | 0 -> (0, 0, 1)
  | 1 -> (0, 1, 1)
  | n -> loop (1, 1, 1) n

引数を処理する必要があり0、1特に の本体でfc. 他の入力については、最初の 3 つの値 (つまり(f0 0, f0 1, f0 2) = (1, 1, 1)) から開始し、指定された再帰ステップを実行して 2 に到達するまで n 回ループします。再帰loop関数は、@bytebuster のソリューションが を使用して実装するものSeq.unfoldです。

したがって、関数の末尾再帰バージョンがありますが、それは単に過去 3 つの値をタプルに保持できるからです。一般に、必要な以前の値を計算するコードがより複雑な処理を行う場合、これは不可能な場合があります。

于 2012-09-17T20:51:14.787 に答える
3

末尾再帰アプローチよりも優れているのは、行列の乗算を利用して、そのような繰り返しを O(log n ) 操作を使用するソリューションに減らすことです。正しさの証明は、読者の演習として残しておきます。

module NumericLiteralG =
    let inline FromZero() = LanguagePrimitives.GenericZero
    let inline FromOne() = LanguagePrimitives.GenericOne

// these operators keep the inferred types from getting out of hand
let inline ( + ) (x:^a) (y:^a) : ^a = x + y
let inline ( * ) (x:^a) (y:^a) : ^a = x * y

let inline dot (a,b,c) (d,e,f) = a*d+b*e+c*f
let trans ((a,b,c),(d,e,f),(g,h,i)) = (a,d,g),(b,e,h),(c,f,i)
let map f (x,y,z) = f x, f y, f z

type 'a triple = 'a * 'a * 'a
// 3x3 matrix type
type 'a Mat3 = Mat3 of 'a triple triple with
    static member inline ( * )(Mat3 M, Mat3 N) = 
        let N' = trans N
        map (fun x -> map (dot x) N') M
        |> Mat3
    static member inline get_One() = Mat3((1G,0G,0G),(0G,1G,0G),(0G,0G,1G))
    static member (/)(Mat3 M, Mat3 N) = failwith "Needed for pown, but not supported"

let inline f n =
    // use pown to get O(log n) time
    let (Mat3((a,b,c),(_,_,_),(_,_,_))) = pown (Mat3 ((0G,1G,0G),(0G,0G,1G),(1G,1G,0G))) n
    a + b + c

// this will take a while...
let bigResult : bigint = f 1000000
于 2012-09-18T00:18:13.230 に答える