74

関数型プログラミング[FP]（Scalaを使用）を紹介しています。私の最初の学習から得られた1つのことは、FPが再帰に大きく依存しているということです。また、純粋なFPでは、反復的な処理を実行する唯一の方法は、再帰関数を作成することであるように思われます。

また、再帰が多用されているため、FPが次に心配しなければならないことはStackoverflowExceptions、通常、再帰呼び出しが長く曲がりくねっていることによるもののようです。これは、いくつかの最適化（スタックフレームの保守における末尾再帰関連の最適化と@tailrecScala v2.8以降の注釈）を導入することで対処されました。

関数型プログラミングのパラダイムにとって再帰が非常に重要である理由を誰かに教えてもらえますか？関数型プログラミング言語の仕様に、繰り返し作業を行うと「違反」するものはありますか？もしそうなら、私もそれを知りたがっています。

PS：私は関数型プログラミングの初心者なので、既存のリソースが私の質問を説明/回答する場合は、遠慮なく指摘してください。また、特にScalaが反復的な処理もサポートしていることを理解しています。

4

9 に答える 9

54

チャーチチューリングの論文は、異なる計算可能性モデル間の同等性を強調しています。

再帰を使用すると、問題を解決するときに可変状態は必要ありません。これにより、セマンティクスをより簡単な用語で指定できます。したがって、形式的な意味で、ソリューションはより単純になります。

Prologは、関数型言語よりも再帰の有効性（反復がない）と、それを使用するときに遭遇する実際的な制限を示していると思います。

于 2012-09-30T08:07:39.703 に答える
41

純粋関数型プログラミングとは、副作用のないプログラミングを意味します。つまり、たとえばループを作成する場合、ループの本体は副作用を生成できません。したがって、ループで何かを実行したい場合は、前の反復の結果を再利用して、次の反復のために何かを生成する必要があります。したがって、ループの本体は関数であり、前の実行の結果をパラメーターとして受け取り、それ自体を呼び出して、独自の結果を次の反復に使用します。これには、ループの再帰関数を直接記述するよりも大きな利点はありません。

些細なことをしないプログラムは、ある時点で何かを繰り返す必要があります。関数型プログラミングの場合、これはプログラムが再帰関数を使用する必要があることを意味します。

于 2012-09-30T08:03:49.047 に答える
25

再帰的に物事を行うという要件をもたらす機能は、不変の変数です。

リストの合計を（擬似コードで）計算するための単純な関数を考えてみましょう。

fun calculateSum(list):
    sum = 0
    for each element in list: # dubious
        sum = sum + element # impossible!
    return sum

これでelement、リストの各反復でが異なりますforeachが、ラムダ引数を持つ関数を使用してこの問題を取り除くようにこれを書き直すことができます。

fun calculateSum(list):
    sum = 0
    foreach(list, lambda element:
        sum = sum + element # impossible!
    )
    return sum

それでも、sumラムダを実行するたびに変数の値を変更する必要があります。これは不変の変数を持つ言語では違法であるため、状態を変更しない方法で書き直す必要があります。

fun calculateSum([H|T]):
    return H + calculateSum(T)

fun calculateSum([]):
    return 0

さて、この実装では、コールスタックへのプッシュとコールスタックからのポップが多く必要になり、すべての小さな操作でこれを実行するプログラムは、それほど速く実行されません。したがって、末尾再帰になるように書き直して、コンパイラが末尾呼び出しの最適化を実行できるようにします。

fun calculateSum([H|T], partialSum):
    return calculateSum(T, H + partialSum)

fun calculateSum([], partialSum):
    return partialSum

fun calculateSum(list):
    return calculateSum(list, 0)

もちろん、無期限にループしたい場合は、末尾再帰呼び出しが絶対に必要です。そうしないと、スタックオーバーフローが発生します。

Scalaの@tailrecアノテーションは、どの関数が末尾再帰であるかを分析するのに役立つツールです。「この関数は末尾再帰です」と主張すると、コンパイラはあなたが間違っているかどうかを教えてくれます。これは、Scalaで実行されるマシン、JVMが末尾呼び出しの最適化を適切にサポートしていないため、他の関数型言語と比較してScalaで特に重要です。したがって、Scalaで末尾呼び出しの最適化を取得することはできません。他の関数型言語で。

于 2012-09-30T08:50:09.013 に答える
8

TL; DR ：再帰は、遍在する帰納的に定義されたデータを処理するために使用されます。

より高いレベルの抽象化で操作する場合、再帰は自然です。関数型プログラミングは、関数を使ったコーディングだけではありません。それは、自然に関数を使用する、より高いレベルの抽象化を操作することです。関数を使用する場合、意味のあるコンテキストから、同じ関数を再利用する（再度呼び出す）のは自然なことです。

世界は、類似/同じビルディングブロックの繰り返しによって構築されます。生地を2つに切ると、生地が2つになります。数学的帰納法は数学の中心です。私たち人間は数えます（1,2,3 ...のように）。帰納的に定義されたもの（たとえば、{1からの数}は{1であり、2からの数}）は、それが定義/構築されたのと同じケースに従って、再帰関数によって処理/分析するのが自然です。

再帰はどこにでもあります。反復ループはとにかく変装した再帰です。なぜなら、そのループに再び入ると、同じループに再び入るからです（おそらく異なるループ変数を使用して）。つまり、コンピューティングに関する新しい概念を発明するのではなく、基盤を発見してそれを明示的にするようなものです。

したがって、再帰は自然です。問題に関するいくつかの法則、（関数がコヒーレントに定義されているという仮定の下で）不変条件を保持する定義中の関数を含む方程式、簡略化された用語で問題を再指定する、そして出来上がり！解決策があります。

例、リストの長さを計算する関数（帰納的に定義された再帰データ型）。それが定義されていると仮定し、当然のことながら、リストの長さを返します。それが従わなければならない法律は何ですか？問題をどのように単純化しても、どの不変条件が保持されますか？

最も直接的なのは、リストをそのヘッド要素に分解し、残りの部分（別名、リストのテール）を分解することです（リストの定義/構築方法による）。法律は、

length (x:xs) = 1 + length xs

えっ！しかし、空のリストはどうですか？それはそれでなければなりません

length [] = 0

では、どのようにそのような関数を書くのでしょうか？...待ってください...私たちはすでにそれを書いています！（Haskellでは、関数適用が並置で表現されているのか疑問に思っている場合、括弧はグループ化のためだけに使用され、最初の要素と残りの要素(x:xs)を含むリストです）。xxs

このようなスタイルのプログラミングを可能にするために必要な言語は、TCO（そしておそらく少し贅沢な TRMCO）を備えていることだけなので、スタックの爆発はなく、準備は整っています。

もう1つは、純度です。コード変数やデータ構造（レコードのフィールドなど）の不変性です。

これにより、何がいつ変化するかを追跡する必要がなくなるだけでなく、「変化する」可変変数/データに隠れるのではなく、コードで時間を明示的に明らかにすることができます。これからは、命令型コードで変数の値を「変更」することしかできません。過去にその値をうまく変更することはできませんね。

そのため、記録された変更履歴のリストが作成され、変更はコードで明示的に示されます。代わりに、x := x + 2を記述しlet x2 = x1 + 2ます。それはコードについての推論をとても簡単にします。

TCOを使用した末尾再帰のコンテキストでの不変性に対処するには、lengthアキュムレータ引数パラダイムの下での上記の関数のこの末尾再帰の書き換えを検討してください。

length xs = length2 0 xs              -- the invariant: 
length2 a []     = a                  --     1st arg plus
length2 a (x:xs) = length2 (a+1) xs   --     the length of 2nd arg

ここで、TCOは、直接ジャンプに加えて、呼び出しフレームの再利用を意味します。したがって、の呼び出しチェーンはlength [1,2,3]、関数のパラメーターに対応する呼び出しスタックフレームのエントリを実際に変更していると見なすことができます。

length [1,2,3]
length2 0 [1,2,3]       -- a=0  (x:xs)=[1,2,3]
length2 1 [2,3]         -- a=1  (x:xs)=[2,3]
length2 2 [3]           -- a=2  (x:xs)=[3]
length2 3 []            -- a=3  (x:xs)=[]
3

値を変更するプリミティブがない純粋な言語では、変更を表現する唯一の方法は、更新された値を引数として関数に渡し、さらに処理することです。それ以降の処理が以前と同じである場合、当然のことながら、同じ関数を呼び出して、更新された値を引数として渡す必要があります。そして、それは再帰です。

そして、以下は、引数リストの長さを計算する履歴全体を明示的にします（そして必要に応じて再利用できるようにします）：

length xs = last results
  where
     results = length3 0 xs
     length3 a []     = [a]
     length3 a (x:xs) = a : length3 (a+1) xs

Haskellでは、これはガード付き再帰またはコアカーションとしてさまざまに知られています（少なくとも私はそう思います）。

于 2012-09-30T15:24:22.633 に答える
6

副作用を回避することは、関数型プログラミングの柱の1つです（もう1つは、高階関数を使用することです）。

突然変異に依存せずに命令型フロー制御をどのように利用できるか想像してみてください。出来ますか？

もちろんfor (var i = 0; i < 10; i++) ...、突然変異に依存します（i++）。実際、条件付きループ構造はすべてそうです。はwhile (something) ...、somethingいくつかの可変状態に依存します。もちろん、ミューテーションwhile (true) ...は使用しません。ただし、そのループから抜け出したい場合は、が必要になりますif (something) break。本当に、突然変異に依存しない再帰以外の（無限ではない）ループメカニズムを考えてみてください。

どうfor (var x in someCollection) ...ですか？今、私たちは関数型プログラミングに近づいています。は、ループ本体のパラメーターとx考えることができます。名前を再利用することは、値を再割り当てすることと同じではありません。おそらく、ループの本体で、（突然変異なし）という観点からの式として値を使用しています。yield returnx

まったく同じように、forループの本体を関数の本体に移動し、高階関数を使用してfoo (x) ...それをマップすることができます-ループ構造をのようなものに置き換えます。someCollectionMap(foo, someCollection)

では、ライブラリ関数はどのようMapにミューテーションなしで実装されるのでしょうか。もちろん、再帰を使用します。それはあなたのために行われます。高階関数の2番目のピラールを使用してループ構造を置き換え始めると、再帰関数を自分で実装する必要が少なくなります。

さらに、末尾呼び出しの最適化では、再帰的定義は反復プロセスと同等です。このブログ投稿もお楽しみいただけます：http：//blogs.msdn.com/b/ashleyf/archive/2010/02/06/recursion-is-the-new-iteration.aspx

于 2012-09-30T16:54:53.543 に答える
6

関数型プログラミングに不可欠だと私が考える2つの特性があります。

  1. 関数はファーストクラスのメンバーです（有用にするために2番目のプロパティが必要なため、関連するだけです）

  2. 関数は純粋です。つまり、同じ引数で呼び出された関数は同じ値を返します。

ここで、命令型でプログラムする場合は、代入を使用する必要があります。

forループについて考えてみましょう。インデックスがあり、反復ごとにインデックスの値が異なります。したがって、このインデックスを返す関数を定義できます。その関数を2回呼び出すと、異なる結果が得られる可能性があります。したがって、原則2を破る。

原則2を破ると、関数の受け渡し（原則1）は非常に危険になります。これは、関数の結果が、関数が呼び出されるタイミングと頻度に依存する可能性があるためです。

于 2012-09-30T08:33:01.190 に答える
6

再帰には「特別な」ものは何もありません。これは、プログラミングや数学で広く使用されているツールであり、それ以上のものではありません。ただし、関数型言語は通常最小限です。それらは、パターンマッチング、型システム、リスト内包表記などの多くの凝った概念を導入しますが、それは非常に一般的で非常に強力な、しかし単純で原始的なツールの構文糖衣にすぎません。このツールは、関数の抽象化と関数の適用です。言語コアの単純さがそれについての推論をはるかに容易にするので、これは意識的な選択です。また、コンパイラの作成も簡単になります。このツールの観点からループを説明する唯一の方法は再帰を使用することです。したがって、命令型プログラマーは、関数型プログラミングは再帰に関するものであると考えるかもしれません。そうではない、gotoステートメントであり、それは彼らが最初に固執したことの1つです。

（間接的である可能性がある）再帰が必要なもう1つのポイントは、再帰的に定義されたデータ構造の処理です。最も一般的な例はlistADTです。FPでは、通常、このように定義されdata List a = Nil | Branch a (List a)ます。ここでのADTの定義は再帰的であるため、その処理関数も再帰的である必要があります。繰り返しになりますが、ここでの再帰はとにかく特別なものではありません。このようなADTを再帰的に処理することは、命令型言語と関数型言語の両方で自然に見えます。リストのようなADTの場合でも命令型ループを採用できますが、ツリーのような構造が異なる場合は採用できません。

したがって、再帰には特別なことは何もありません。これは単に別のタイプの関数アプリケーションです。ただし、最新のコンピューティングシステムには制限があるため（デファクトスタンダードのクロスプラットフォームアセンブラーであるC言語での設計上の決定が不十分なため）、関数呼び出しは末尾呼び出しであっても無限にネストすることはできません。そのため、関数型プログラミング言語の設計者は、許可された末尾呼び出しを末尾再帰（scala）に制限するか、トランポーリング（古いghc codegen）などの複雑な手法を使用するか、asm（最新のghc codegen）に直接コンパイルする必要があります。

TL; DR：FPの再帰には特別なことはなく、少なくともIPにすぎません。ただし、JVMの制限により、scalaで許可される末尾呼び出しのタイプは末尾再帰だけです。

于 2012-09-30T08:49:52.800 に答える
2

前回関数型言語（Clojure）を使用したときは、再帰を使用することすら誘惑されませんでした。最終結果に到達するまで、すべてが一連の物として扱われ、ある機能が適用されて部品製品が取得され、別の機能が適用されました。

再帰は、任意のgを処理するために通常処理する必要がある複数のアイテムを処理するための唯一の方法であり、必ずしも最も明確な方法ではありません。

于 2012-10-04T23:27:25.663 に答える
1

新しいFP学習者のために、2セントを追加したいと思います。いくつかの回答で述べたように、再帰は不変の変数を利用することですが、なぜそれを行う必要があるのでしょうか。複数のコアでプログラムを並行して実行するのが簡単になるためですが、なぜそれが必要なのですか？シングルコアで実行して、いつものように幸せになれませんか？いいえ。処理するコンテンツは日々増加しており、CPUクロックサイクルはコアを追加するよりも大幅に増やすことはできません。過去10年間で、消費者向けコンピューターのクロック速度は最大2.7GHzから3.0GHzであり、チップ設計者はますます多くのトランジスタを搭載することに問題を抱えています。また、FPは非常に長い間使用されてきましたが、そうではありませんでした。

于 2016-03-26T16:40:23.863 に答える