Do ordine superiore funzioni forniscono più potere di programmazione funzionale?

Question

ho chiesto una domanda simile su cstheory.SE .

questa risposta su StackOverflow c'è un algoritmo che su un puro linguaggio di programmazione funzionale non pigro ha un $ \ Omega (n \ log n) $ complessità, mentre lo stesso algoritmo di programmazione imperativa è $ \ Omega (n) $. Aggiunta di pigrizia alla lingua FP renderebbe l'algoritmo di $ \ Omega (n) $.

C'è un rapporto equivalente di confronto di un linguaggio di FP con e senza funzioni superiori di ordine? E 'ancora di Turing? Se lo è, fa la mancanza di ordine superiore sul FP rende il linguaggio meno "potente" o efficiente?

Answer 1

In un linguaggio di programmazione funzionale, che è abbastanza potente (per esempio, con i tipi di dati per implementare chiusure ) è possibile eliminare tutti gli usi di ordine superiore dalla trasformazione di defunzionalizzazione . Dal momento che questo metodo viene utilizzato per compilare questo tipo di linguaggio, si può ragionevolmente supporre che questo non pregiudica le prestazioni e che in questo ambiente di ordine superiore non rendere il linguaggio meno potenti. Tuttavia, non incide come scrivere il codice.

Tuttavia, se la lingua non è abbastanza potente, allora sì, di ordine superiore non fornisce potenza espressiva. Si consideri il lambda-calcolo:., Senza alcuna funzione di ordine superiore, in realtà non può fare nulla, soprattutto perché la maggior parte dei tipi di dati di base (interi, booleani) sono realizzati tramite le funzioni

In conclusione, in realtà dipende dalla lingua.

---

Sopra è la mia risposta. Qui di seguito, un commento su un assunto di consueto in linguaggi imperativi.

A proposito di un algoritmo che in un non-lazy linguaggio di programmazione funzionale ha un $ \ Omega (n \ log n) $ complessità, mentre lo stesso algoritmo di programmazione imperativa è $ \ Omega (n) $. Aggiunta di pigrizia alla lingua FP renderebbe l'algoritmo di $ \ Omega (n) $.

Mi piacerebbe vedere questo riferimento. Il presupposto comune è che l'accesso a un array di lunghezza $ n $ in una RAM è nel tempo $ O (1) $ e l'equivalente in puro FP è in in tempo $ O (\ log n) $. Questo non è del tutto vero: il tempo di accesso in una RAM è di $ O (\ log m) $ dove $ m $ è la dimensione della memoria. Naturalmente, $ m=n $. In pratica accesso ad un elemento di un array è molto più veloce. Una ragione potrebbe essere che $ m $ è delimitata ma ... così è $ n $!

EDIT: grazie per il link (link per la carta di pigrizia non è disponibile, qui è un altro ). Come scritto nei commenti e soprattutto nella mia risposta, il modello di RAM è un po 'ingiusto per pura FP fornendo $ O (1) $ - time look-up anche quando le dimensioni di un indirizzo non è limitato. Sono ancora capire come funziona il trucco pigro, ma penso che sia importante notare che questo è solo per questo particolare problema.

Answer 2

Dipende da cosa si intende per espressività.

Ecco un argomento che di ordine superiore non aggiungere qualcosa: con i linguaggi del primo ordine, la ricorsione primitiva non è sufficiente per esprimere la funzione di Ackermann . Tuttavia, in presenza di funzioni di ordine superiore, la ricorsione primitiva è sufficiente:

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

Questo definisce la funzione Ackermann utilizzando solo ricorsione primitiva.

Si noti che $ \ textit {Iter} $ non è definibile in teoria della ricorsione convenzionale, perché $ \ textit {Iter} $ è di ordine superiore. In teoria della ricorsione convenzionale tutte le funzioni definibili hanno digitare $ \ mathbb {N} ^ k \ rightarrow \ mathbb {N} $ per qualche $ k $, mentre $ \ textit {Iter} $ ha tipo $ (\ mathbb {N} \ rightarrow \ mathbb {N}) \ rightarrow (\ mathbb {N} \ rightarrow \ mathbb {N}) $.