Предоставляют ли функции высшего порядка больше возможностей для функционального программирования?

Я задал похожий вопрос на cstheory.SE .

Согласно этому ответу на Stackoverflow существует алгоритм, который на не ленивом чисто функциональном языке программирования имеет сложность , тогда как тот же алгоритм в императивном программировании - Ω ( n ) . Добавление ленивости к языку FP сделало бы алгоритм Ω ( n ) .$\Omega(n \log n)$$\Omega(n)$$\Omega(n)$

Существуют ли какие-либо эквивалентные отношения, сравнивающие язык FP с функциями высшего порядка и без них? Это все еще Тьюринг завершен? Если это так, делает ли Высший Порядок недостатком FP ​​язык менее «мощным» или эффективным?

В достаточно мощном функциональном языке программирования (например, с типами данных для реализации замыканий ) вы можете исключить все виды использования более высокого порядка путем преобразования нефункционализации . Поскольку этот метод используется для компиляции такого рода языка, вы можете разумно предположить, что это не влияет на производительность и что в этом параметре более высокий порядок не делает язык менее мощным. Однако это влияет на то, как писать код.

Однако, если язык недостаточно силен, то да, высший порядок обеспечивает выразительную силу. Рассмотрим лямбда-исчисление: без какой-либо функции высшего порядка он действительно ничего не может сделать, в основном потому, что самые основные типы данных (целые, логические) реализованы с использованием функций.

В заключение, это действительно зависит от языка.

---

Выше мой ответ. Ниже комментарий об обычном предположении о императивных языках.

об алгоритме, который на неленивом функциональном языке программирования имеет сложность , тогда как тот же алгоритм в императивном программировании - Ω ( n ) . Добавление ленивости к языку FP сделало бы алгоритм Ω ( n ) .$\Omega(n \log n)$$\Omega(n)$$\Omega(n)$

Я хотел бы видеть эту ссылку. Обычное предположение состоит в том, что доступ к массиву длины в ОЗУ осуществляется за время O ( 1 ), а эквивалент в чистой FP - за время O ( log n ) . Это не совсем верно: время доступа в RAM находится в O ( log m ), где m - размер памяти. Конечно, m ≥ n . На практике доступ к элементу массива намного быстрее. Причиной может быть то, что m ограничено, но ... как и n !$n$$O(1)$$O(\log n)$$O(\log m)$$m$$m≥n$$m$$n$

$O(1)$

Это зависит от того, что вы подразумеваете под выразительностью.

Вот аргумент, что высший порядок что-то добавляет: с языками первого порядка примитивная рекурсия недостаточна для выражения функции Аккермана . Однако при наличии функций высшего порядка примитивной рекурсии достаточно:

$$\begin{array}{lcl} \textit{Ackermann} \ 0 & = & \lambda x. x+1 \\ \textit{Ackermann} \ ( m+1 ) & = & \textit{Iter}\ ( \textit{Ackermann}\ m ) \\ \textit{Iter}\ f\ 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}$$k$$\textit{Iter}$$(\mathbb{N} \rightarrow \mathbb{N}) \rightarrow (\mathbb{N} \rightarrow \mathbb{N})$