17

わかりました、F#だけで、これが私が今それを理解している方法です:

  • 一部の問題は本質的に再帰的であり(1つだけ名前を付けるためにツリー構造を構築または読み取る)、再帰を使用します。このような場合は、末尾再帰を使用してスタックにブレークを与えることが望ましいです。

  • 一部の言語は純粋関数であるため、問題が本質的に再帰的でない場合でも、whileループの代わりに再帰を使用する必要があります

だから私の質問:F#は命令型パラダイムもサポートしているので、自然に再帰的な問題ではない問題に対してF#で末尾再帰を使用しますか?特に私が読んだので、コンパイラは末尾再帰を認識し、とにかくそれをwhileループで変換しますか?

もしそうなら:なぜ?

4

5 に答える 5

32

最良の答えは「どちらでもない」です。:)

whileループと末尾再帰の両方に関連する醜さがいくつかあります。

ループには可変性とエフェクトが必要ですが、特にローカル関数のコンテキストでカプセル化されている場合は、これらを適度に使用することに反対はありませんが、単にループにエフェクトを導入し始めると、プログラムが乱雑になったり醜くなったりするように感じることがあります。 。

末尾再帰には、多くの場合、追加のアキュムレータパラメータまたは継続渡しスタイルが必要になるという欠点があります。これにより、関数の起動条件をマッサージするための追加の定型文でプログラムが乱雑になります。

最善の答えは、whileループも再帰も使用しないことです。ここでは、高階関数とラムダ、特にマップとフォールドが救世主です。再利用可能なライブラリにそれらをカプセル化して、計算の本質を単純かつ宣言的に述べることができるのに、なぜループのための厄介な制御構造をいじくり回すのですか?

ループ/再帰を使用するのではなく、頻繁にmap / foldを呼び出す習慣があり、導入した新しいツリー構造のデータ型とともにfold関数を提供する場合は、はるかに効果的です。:)

F#のフォールドについて詳しく知りたい方は、このトピックに関するシリーズの最初の 3つの ブログ投稿をチェックしてみませんか?

于 2009-11-25T14:35:37.213 に答える
21

好みと一般的なプログラミングスタイルの順に、次のようにコードを記述します。

利用可能な場合はマップ/フォールド

let x = [1 .. 10] |> List.map ((*) 2)

そのちょうど便利で使いやすいです。

非末尾再帰関数

> let rec map f = function
    | x::xs -> f x::map f xs
    | [] -> [];;

val map : ('a -> 'b) -> 'a list -> 'b list

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

ほとんどのアルゴリズムは、末尾再帰なしで読み、表現するのが最も簡単です。これは、あまり深く再帰する必要がない場合に特に効果的であり、多くの並べ替えアルゴリズムやバランスの取れたデータ構造でのほとんどの操作に適しています。

log 2 (1,000,000,000,000,000)〜= 50であることを忘れないでください。したがって、末尾再帰のないlog(n)操作はまったく怖いものではありません。

アキュムレータを使用した末尾再帰

> let rev l =
    let rec loop acc = function
        | [] -> acc
        | x::xs -> loop (x::acc) xs
    loop [] l

let map f l =
    let rec loop acc = function
        | [] -> rev acc
        | x::xs -> loop (f x::acc) xs
    loop [] l;;

val rev : 'a list -> 'a list
val map : ('a -> 'b) -> 'a list -> 'b list

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

それは機能しますが、コードは不器用であり、アルゴリズムの優雅さはわずかに曖昧です。上記の例は読むのにそれほど悪くはありませんが、ツリーのようなデータ構造に入ると、それは本当に悪夢になり始めます。

継続渡しで末尾再帰

> let rec map cont f = function
    | [] -> cont []
    | x::xs -> map (fun l -> cont <| f x::l) f xs;;

val map : ('a list -> 'b) -> ('c -> 'a) -> 'c list -> 'b

> [1 .. 10] |> map id ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

このようなコードを見るたびに、「これは巧妙なトリックです!」と自分に言い聞かせます。読みやすさを犠牲にして、非再帰関数の形状を維持し、バイナリツリーへの末尾再帰挿入にとって非常に興味深いことがわかりました。

おそらくここで話す私のモナド恐怖症、あるいはLispのcall / ccに精通していないという私の本質的な欠如ですが、CSPが実際にアルゴリズムを単純化する機会はほとんどないと思います。反例はコメントで歓迎されています。

whileループ/forループ

シーケンスの理解を除けば、F#コードでwhileループやforループを使用したことは一度もないと思います。とにかく...

> let map f l =
    let l' = ref l
    let acc = ref []
    while not <| List.isEmpty !l' do
        acc := (!l' |> List.hd |> f)::!acc
        l' := !l' |> List.tl
    !acc |> List.rev;;

val map : ('a -> 'b) -> 'a list -> 'b list

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

その事実上、命令型プログラミングのパロディーです。代わりに宣言することで少し健全性を維持できるかもしれませんがlet mutable l' = l、重要な関数では。を使用する必要がありますref

于 2009-11-25T16:02:25.167 に答える
6

正直なところ、ループで解決できる問題は、どちらも最終的に(通常は条件付きの)ジャンプに変換できるため、すでに自然に再帰的な問題です。

明示的なループを作成する必要があるほとんどすべての場合に、末尾呼び出しを使用する必要があると思います。それはもっと用途が広いです:

  • whileループでは、ループ本体が1つに制限されますが、末尾呼び出しでは、「ループ」の実行中に多くの異なる状態を切り替えることができます。
  • whileループは、終了をチェックするための1つの条件に制限します。末尾再帰を使用すると、制御フローを別の場所にシャントするのを待機する任意の複雑な一致式を使用できます。
  • 末尾呼び出しはすべて有用な値を返し、有用なタイプエラーを生成する可能性があります。whileループは何も返さず、副作用に依存して作業を行います。
  • whileループはファーストクラスではありませんが、末尾呼び出しのある関数(またはwhileループ)はファーストクラスです。ローカルスコープの再帰的バインディングは、そのタイプを調べることができます。
  • 末尾再帰関数は、末尾呼び出しを使用して必要な順序で相互に呼び出す部分に簡単に分割できます。これにより、読みやすくなり、ループの途中から始めたい場合に役立ちます。これは、whileループには当てはまりません。

全体として、F#のwhileループは、関数本体内で、特定の条件が満たされるまで同じことを繰り返し実行する可変状態で作業する場合にのみ価値があります。ループが一般的に有用または非常に複雑な場合は、他のトップレベルのバインディングにループを除外することをお勧めします。データ型自体が不変である場合(多くの.NET値型は不変です)、とにかくそれらへの可変参照を使用してもほとんど利益が得られない可能性があります。

whileループが仕事に最適で、比較的短いニッチなケースでは、whileループにのみ頼るべきだと思います。多くの命令型プログラミング言語では、whileループは、caseステートメントで繰り返し駆動するなど、不自然な役割にねじれることがよくあります。このようなことは避け、末尾呼び出しを使用できるかどうか、さらには高階関数を使用して同じ目的を達成できるかどうかを確認してください。

于 2011-03-31T09:59:36.587 に答える
5

多くの問題には再帰的な性質がありますが、長い間必然的に考えていたために、これを見ることができないことがよくあります。

一般に、私は関数型言語で可能な限り関数型手法を使用します-ループは副作用のみに依存しているため、ループは決して関数型ではありません。したがって、命令型のコードやアルゴリズムを扱う場合は、ループを使用するのが適切ですが、機能的なコンテキストでは、ループはあまり優れているとは見なされません。

関数手法は、再帰を意味するだけでなく、適切な高階関数を使用することも意味します。

したがって、リストを合計する場合、forループも再帰関数もありませんが、afoldは、車輪の再発明を行わずにわかりやすいコードを作成するためのソリューションです。

于 2009-11-25T14:42:12.843 に答える
2

自然に再帰的な問題ではない問題の場合..とにかくwhileループで変換するだけです

あなたはこれに自分で答えました。再帰的な問題には再帰を使用し、本質的に機能しないものにはループを使用します。常に考えてみてください。どちらがより自然に感じられ、どちらがより読みやすくなります。

于 2009-11-25T14:34:57.083 に答える