¿Las funciones de orden superior proporcionan más potencia a la programación funcional?

He hecho una pregunta similar sobre cstheory.SE .

De acuerdo con esta respuesta en Stackoverflow, existe un algoritmo que en un lenguaje de programación funcional puro no perezoso tiene una complejidad , mientras que el mismo algoritmo en la programación imperativa es Ω ( n ) . Agregar pereza al lenguaje FP haría que el algoritmo Ω ( n ) .$\Omega(n \log n)$$\Omega(n)$$\Omega(n)$

¿Existe alguna relación equivalente al comparar un lenguaje FP con y sin funciones de orden superior? ¿Sigue siendo Turing completo? Si es así, ¿la falta de un orden superior en FP hace que el lenguaje sea menos "poderoso" o eficiente?

En un lenguaje de programación funcional que sea lo suficientemente potente (por ejemplo, con tipos de datos para implementar cierres ), puede eliminar todos los usos de orden superior mediante la transformación de la desfuncionalización . Dado que este método se utiliza para compilar este tipo de lenguaje, puede suponer razonablemente que esto no afecta el rendimiento y que, en este contexto, un orden superior no hace que el lenguaje sea menos poderoso. Sin embargo, sí afecta cómo escribir código.

Sin embargo, si el lenguaje no es lo suficientemente poderoso, entonces sí, el orden superior proporciona poder expresivo. Considere el cálculo lambda: sin ninguna función de orden superior, realmente no puede hacer nada, principalmente porque los tipos de datos más básicos (enteros, booleanos) se implementan utilizando funciones.

En conclusión, realmente depende del idioma.

---

Arriba está mi respuesta. A continuación, un comentario sobre una suposición habitual sobre los idiomas imperativos.

acerca de un algoritmo que en un lenguaje de programación funcional no perezoso tiene una complejidad , mientras que el mismo algoritmo en la programación imperativa es Ω ( n ) . Agregar pereza al lenguaje FP haría que el algoritmo Ω ( n ) .$\Omega(n \log n)$$\Omega(n)$$\Omega(n)$

Me gustaría ver esta referencia. La suposición habitual es que un acceso a una matriz de longitud en una RAM está en el tiempo O ( 1 ) y el equivalente en FP puro está en el tiempo O ( log n ) . Eso no es del todo cierto: el tiempo de acceso en una RAM está en O ( log m ) donde m es el tamaño de la memoria. Por supuesto, m ≥ n . En la práctica, acceder a un elemento de una matriz es mucho más rápido. Una razón sería que m está acotado pero ... también lo es n !$n$$O(1)$$O(\log n)$$O(\log m)$$m$$m≥n$$m$$n$

EDITAR: gracias por el enlace (el enlace para el documento sobre la pereza no está disponible, aquí hay otro ). Como se publicó en los comentarios y más arriba en mi respuesta, el modelo de RAM es un poco injusto para FP puro al proporcionar búsquedas de tiempo incluso cuando el tamaño de una dirección no está limitado. Todavía no entiendo cómo funciona el truco vago, pero creo que es importante tener en cuenta que esto es solo para este problema en particular.$O(1)$

Depende de lo que quieras decir con expresividad.

Aquí hay un argumento de que el orden superior agrega algo: con los lenguajes de primer orden, la recursividad primitiva no es suficiente para expresar la función de Ackermann . Sin embargo, en presencia de funciones de orden superior, la recursividad primitiva es suficiente:

$$\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}$$

Esto define la función de Ackermann utilizando solo la recursividad primitiva.

Tenga en cuenta que $\textit{Iter}$ no es definible en la teoría de recursión convencional, porque $\textit{Iter}$Es de orden superior. En la teoría de recursión convencional, todas las funciones definibles tienen tipo$\mathbb{N}^k \rightarrow \mathbb{N}$ para algunos $k$, mientras $\textit{Iter}$ tiene tipo $(\mathbb{N} \rightarrow \mathbb{N}) \rightarrow (\mathbb{N} \rightarrow \mathbb{N})$.