高次関数は機能的なプログラミングにより多くの力を提供しますか？

Question

同様の質問をしました csheory.se.

によると StackoverFlowに関するこの答え 怠zyな純粋な機能プログラミング言語には、$ omega（n log n）$の複雑さがあり、命令プログラミングの同じアルゴリズムは$ omega（n）$です。 FP言語に怠zy性を追加すると、アルゴリズム$ omega（n）$が作成されます。

高次関数との有無にかかわらず、FP言語を比較する同等の関係はありますか？まだチューリングが完了していますか？もしそうなら、FPの高次の欠如により、言語の「強力」または効率的になりますか？

Answer 1

十分に強力な機能的なプログラミング言語で（たとえば、実装するデータ型を使用して 閉鎖）あなたは、の変換によって高次のすべての使用を排除することができます 官能化. 。この方法はこの種の言語をコンパイルするために使用されるため、これはパフォーマンスに影響を与えず、 この設定で 高次では、言語の強力なものではありません。ただし、コードの書き方に影響します。

ただし、言語が十分に強力でない場合、はい、高次は表現力を提供します。 Lambda-Calculusを考えてみましょう。高次関数がなければ、最も基本的なデータ型（整数、ブール科）が機能を使用して実装されているため、実際には何もできません。

結論として、それは本当に言語に依存します。

---

上記は私の答えです。以下に、命令言語に関する通常の仮定に関するコメント。

非怠惰な機能プログラミング言語には$ omega（n log n）$の複雑さがありますが、命令プログラミングの同じアルゴリズムは$ omega（n）$です。 FP言語に怠zy性を追加すると、アルゴリズム$ omega（n）$が作成されます。

このリファレンスを見たいです。通常の仮定は、RAMの長さ$ n $の配列へのアクセスが時間内に$ o（1）$であり、純粋なfpの等価物は時間$ o（ log n）$にあることです。それは完全に真実ではありません：RAMのアクセス時間は$ o（ log m）$です。ここで、$ m $はメモリのサイズです。もちろん、$m≥n$。実際には、配列の要素にアクセスすることははるかに高速です。理由は、$ m $が境界線になっているからですが... $ n $もそうです！

編集：リンクをありがとう（怠inessについての論文のリンクは利用できません、 これが別のものです）。コメントと私の回答の上に投稿されているように、RAMのモデルは、1つのアドレスのサイズが制限されていない場合でも、$ o（1）$のルックアップを提供することにより、純粋なFPに対して少し不公平です。私はまだ怠zyなトリックがどのように機能するかをまだ理解していませんが、これはこの特定の問題のためだけのものであることに注意することが重要だと思います。

Answer 2

それはあなたが表現力によって何を意味するかに依存します。

これは、高次が何かを追加するという議論です。一次言語では、原始的な再帰は表現するのに十分ではありません アッカーマン関数. 。ただし、高次関数の存在下では、原始的な再帰で十分です。

$$ begin {array} {lcl} textit {ackermann} 0＆=＆ lambda x。 x+1 textit {ackermann} （m+1）＆=＆ textit {iter} （ textit {ackermann} m） 0＆=＆f 1 textit {iter} f （n+1）＆=＆f （ textit {iter} f n） end {array} $$

これは、原始的な再帰のみを使用してアッカーマン関数を定義します。

$ textit {iter} $は、従来の再帰理論では定義できないことに注意してください。$ textit {iter} $は高次であるためです。従来の再帰理論では、すべての定義可能な関数はタイプ$ mathbb {n}^k rightarrow mathbb {n} $ for $ k $、$ textit {iter} $はタイプ$（ mathbb {n} rightArrow mathbb {n}） rightArrow（ mathbb {n} rightarrow mathbb {n}）$。