As funções de ordem superior fornecem mais poder à programação funcional?

Fiz uma pergunta semelhante no cstheory.SE .

De acordo com esta resposta no Stackoverflow, existe um algoritmo que em uma linguagem de programação funcional pura e não preguiçosa possui uma complexidade , enquanto o mesmo algoritmo na programação imperativa é . Adicionar preguiça à linguagem FP tornaria o algoritmo .$\Omega(n \log n)$$\Omega(n)$$\Omega(n)$

Existe alguma relação equivalente comparando uma linguagem FP com e sem funções de ordem superior? Ainda é Turing Complete? Se for, a falta de ordem superior no FP torna a linguagem menos "poderosa" ou eficiente?

Em uma linguagem de programação funcional suficientemente poderosa (por exemplo, com tipos de dados para implementar fechamentos ), você pode eliminar todos os usos de ordem superior pela transformação da defuncionalização . Como esse método é usado para compilar esse tipo de idioma, você pode razoavelmente supor que isso não afeta as performances e que , nessa configuração, a ordem superior não torna o idioma menos poderoso. No entanto, isso afeta como escrever código.

No entanto, se a linguagem não for suficientemente poderosa, sim, a ordem superior fornece um poder expressivo. Considere o cálculo lambda: sem nenhuma função de ordem superior, ela realmente não pode fazer nada, principalmente porque os tipos de dados mais básicos (números inteiros, booleanos) são implementados usando funções.

Em conclusão, isso realmente depende do idioma.

---

Acima está a minha resposta. Abaixo, um comentário sobre uma suposição usual sobre linguagens imperativas.

sobre um algoritmo que em uma linguagem de programação funcional não preguiçosa possui uma complexidade , enquanto o mesmo algoritmo na programação imperativa é Ω ( n ) . Adicionar preguiça à linguagem FP tornaria o algoritmo Ω ( n ) .$\Omega(n \log n)$$\Omega(n)$$\Omega(n)$

Eu gostaria de ver esta referência. A suposição usual é que um acesso a uma matriz de comprimento em uma RAM esteja no tempo O ( 1 ) e o equivalente em FP puro esteja no tempo O ( log n ) . Isso não é inteiramente verdade: o tempo de acesso em uma RAM está em O ( log m ), em que m é o tamanho da memória. Claro, m ≥ n . Na prática, acessar um elemento de uma matriz é muito mais rápido. Uma razão seria que m é limitado, mas ... o mesmo acontece com n !$n$$O(1)$$O(\log n)$$O(\log m)$$m$$m≥n$$m$$n$

EDIT: obrigado pelo link (o link para o artigo sobre preguiça não está disponível, aqui está outro ). Conforme publicado nos comentários e acima na minha resposta, o modelo de RAM é um pouco injusto para o FP puro, fornecendo pesquisas em tempo mesmo quando o tamanho de um endereço não é limitado. Ainda estou para entender como o truque preguiçoso funciona, mas acho importante notar que isso é apenas para esse problema específico.$O(1)$

Depende do que você quer dizer com expressividade.

Aqui está um argumento de que ordem superior acrescenta algo: nas linguagens de primeira ordem, a recursão primitiva não é suficiente para expressar a função Ackermann . No entanto, na presença de funções de ordem superior, a recursão primitiva é 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}$$

Isso define a função Ackermann usando apenas recursão primitiva.

$\textit{Iter}$$\textit{Iter}$$\mathbb{N}^k \rightarrow \mathbb{N}$$k$$\textit{Iter}$$(\mathbb{N} \rightarrow \mathbb{N}) \rightarrow (\mathbb{N} \rightarrow \mathbb{N})$