1

私は最近 F# を使い始め、エラトステネスのふるいを表す非常に基本的な再帰関数を実装しました。私は次の作業コードを思いつきました：

static member internal SieveOfEratosthenesRecursive sequence accumulator =
    match sequence with
    | [] -> accumulator
    | head::tail -> let rest = tail |> List.filter(fun number -> number % head <> 0L)
                    let newAccumulator = head::accumulator
                    Prime.SieveOfEratosthenesRecursive rest newAccumulator

この関数は実際にはメモリ効率が悪いので、変数「rest」と「newAccumulator」を削除しようとしました。次のコードを思いつきました

static member internal SieveOfEratosthenesRecursive sequence accumulator =
    match sequence with
    | [] -> accumulator
    | head::tail -> tail    |> List.filter(fun number -> number % head <> 0L) 
                            |> Prime.SieveOfEratosthenesRecursive (head::accumulator)

私が読んだチュートリアルを理解している限り、Prime.SieveOfEratosthenesRecursive は、フィルタリングされたテールを最初のパラメーターとして呼び出し、 head::accumulatorで構成されるリストを 2 番目のパラメーターとして呼び出します。ただし、変数の使用量を減らしてコードを実行しようとすると、プログラムが無限ループに陥ります。なぜこれが起こっているのですか？

4

2 に答える 2

1

私が読んだチュートリアルを理解している限り、Prime.SieveOfEratosthenesRecursive はtail、最初のパラメータとしてフィルタリングされ、2 番目のパラメータとして構成されるリストで呼び出されますhead::accumulator。

あなたはこれを逆に持っています。

rest最初のバージョンでは、次に渡しますnewAccumulator。newAccumulator2 番目のバージョンでは、実質的にthenを渡していますrest。つまり、引数を転置しました。

Prime.SieveOfEratosthenesRecursive (head::accumulator)(head::accumulator)は、最初の引数 ( sequence)として適用する部分関数適用です。この部分関数適用は、コードの最初のバージョンで呼び出されたものaccumulatorを ( 経由で) 渡す単項関数 ( を期待) を生成します。|>rest

の引数の順序を変更SieveOfEratosthenesRecursiveするのが最も簡単な解決策ですが、次の慣用句のようなものも検討します。

static member internal SieveOfEratosthenesRecursive sequence accumulator =
    match sequence with
    | [] -> accumulator
    | head::tail ->
        tail
        |> List.filter(fun number -> number % head <> 0L) 
        |> Prime.SieveOfEratosthenesRecursive <| (head::accumulator)

また

static member internal SieveOfEratosthenesRecursive sequence accumulator =
    let inline flipzip a b = b, a
    match sequence with
    | [] -> accumulator
    | head::tail ->
        tail
        |> List.filter(fun number -> number % head <> 0L) 
        |> flipzip (head::accumulator)
        ||> Prime.SieveOfEratosthenesRecursive

FWIW、ここで名前付き変数を削除restしても、メモリ使用量には少しも影響しません。newAccumulator

于 2012-06-07T21:53:58.127 に答える
1

2 番目の関数の最後の呼び出しは、次と同等です。

Prime.SieveOfEratosthenesRecursive newAccumulator rest

2つのパラメーターの位置を切り替える場所。newAccumulator再帰呼び出しのたびに大きくなるため、空のリストの基本ケースに到達することはありません。

経験則では、最も頻繁に変化するパラメーターを最後に置きます。

let rec sieve acc xs =
    match xs with
    | [] -> acc
    | x::xs' -> xs' |> List.filter (fun y -> y % x <> 0L) 
                    |> sieve (x::acc)

上記の関数は、functionキーワードを使用して短縮できます。

let rec sieve acc = function
    | [] -> acc
    | x::xs' -> xs' |> List.filter (fun y -> y % x <> 0L) 
                    |> sieve (x::acc)

pipe ( |>) 演算子を使用すると、関数が読みやすくなるだけで、メモリ使用量にはまったく影響しません。

于 2012-06-07T22:06:16.323 に答える