高阶功能是否为功能编程提供了更大的功能？

Question

我问了一个类似的问题 在cstheory.se上.

根据 这个答案在stackoverflow上 有一种算法是，在非懒惰的纯函数编程语言上具有$ omega（n log n）$复杂性，而命令编程中的相同算法为$ omega（n）$。在FP语言中增加懒惰将使算法$ omega（n）$。

是否有与具有高阶功能的FP语言进行比较的等效关系？图灵还完整吗？如果是这样，FP缺乏高级阶段是否会使语言降低“强大”或有效？

Answer 1

用功能强大的功能编程语言（例如，使用数据类型可以实现 关闭）您可以通过转换来消除高阶的所有用途 已解决. 。由于此方法用于编译这种语言，因此您可以合理地假设这不会影响性能，并且 在这种情况下 高级秩序不会使语言变得不那么强大。但是，它确实会影响如何编写代码。

但是，如果该语言不够强大，那么是的，高阶确实提供了表达能力。考虑lambda-calculus：没有任何高阶功能，它确实无能为力，主要是因为使用函数实现了最基本的数据类型（整数，布尔值）。

总之，这确实取决于语言。

---

上面是我的答案。下面，关于命令语言的通常假设的评论。

关于一种算法，即在非懒惰功能编程语言上具有$ omega（n log n）$复杂性，而命令编程中的相同算法为$ omega（n）$。在FP语言中增加懒惰将使算法$ omega（n）$。

我想看看这个参考。通常的假设是，对RAM中的长度$ n $的数组的访问时间为$ O（1）$，并且纯FP中的等效量在时间$ o（ log n）$中。事实并非完全正确：RAM中的访问时间在$ O（ log M）$中，其中$ m $是内存的大小。当然，$m≥n$。实际上，访问阵列的元素要快得多。原因是$ m $是有限的，但是... $ n $也是如此！

编辑：谢谢您的链接（有关懒惰的论文的链接， 这是另一个）。正如评论中及以上所示的正如我的回答中所述，RAM的模型对纯FP有点不公平，即使一个地址的大小不限制，也可以提供$ O（1）$ - 时间查找。我尚未了解懒惰的技巧是如何工作的，但我认为重要的是要注意，这仅适用于这个特定的问题。

Answer 2

这取决于您的表现力的含义。

这是一个论点，即高阶确实添加了一些东西：使用一阶语言，原始递归不足以表达 Ackermann功能. 。但是，在具有高阶函数的情况下，原始递归足够：

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

这仅使用原始递归来定义Ackermann函数。

请注意，$ textit {iter} $在常规递归理论中无法定义，因为$ textit {iter} $是高阶。在常规递归理论中，所有可定义的函数都具有$ mathbb {n}^k rightarrow mathbb {n} $的某些$ k $，而$ textIt {iter} $具有type $（ mathbb {n} rightarrow mathbb {n}） rightarrow（ mathbb {n} rightarrow mathbb {n}）$。