[algorithm] Efficienza della programmazione puramente funzionale


Answers

Esistono infatti numerosi algoritmi e strutture dati per le quali non è nota alcuna soluzione puramente funzionale asintoticamente efficiente (quella implementabile nel calcolo lambda puro), anche con la pigrizia.

  • La summenzionata unione-trova
  • Tabelle hash
  • Array
  • Alcuni algoritmi grafici
  • ...

Tuttavia, assumiamo che nelle lingue "imperative" l'accesso alla memoria sia O (1) mentre in teoria non può essere così asintoticamente (cioè per le dimensioni dei problemi illimitate) e l'accesso alla memoria all'interno di un enorme set di dati è sempre O (log n) , che può essere emulato in un linguaggio funzionale.

Inoltre, dobbiamo ricordare che in realtà tutti i linguaggi funzionali moderni forniscono dati mutabili, e Haskell lo fornisce senza sacrificare la purezza (la monade ST).

Question

Qualcuno sa qual è il peggior rallentamento asintotico possibile che può accadere quando si programma puramente funzionalmente rispetto all'imperativo (cioè permettendo effetti collaterali)?

Chiarimento dal commento di itowlson : c'è qualche problema per il quale l'algoritmo non distruttivo più noto è asintoticamente peggiore dell'algoritmo distruttivo più noto e, in caso affermativo, di quanto?




"Funzionale" è un insieme di funzionalità diverse, ognuna delle quali è indipendentemente utile, e la sua trovata è più utile per guardarle individualmente.

Immutabilità

Ora che mi è familiare, ogni volta che riesco a farla franca restituendo un risultato immutabile, cerco sempre di farlo anche in un programma orientato agli oggetti. È più semplice ragionare sul programma se si dispone di dati di tipo valore.

Funziona come un primo tipo di classe

Qualunque cosa tu voglia chiamarla, passando per delegati, azioni o funzioni, è un modo davvero pratico per risolvere un'intera classe di problemi del mondo reale, come il "buco nel modello centrale".

Essere in grado di comporre le funzioni (ad esempio, trasformare Action in solo Action è anche molto utile in alcuni scenari.

Dovremmo anche notare la sintassi Lambda qui, perché si ottiene solo la sintassi Lambda quando si promuovono le funzioni in tipi di prima classe. La sintassi Lambda può essere molto espressiva e concisa.

monadi

Questo è un costrutto sottile ma molto potente. È potente quanto la parola chiave yield utilizzata per creare classi IEnumerable in C #. Essenzialmente sta costruendo una macchina di stato per te sotto le coperte, ma la tua logica sembra lineare.

Valutazione e ricaduta pigra

Li ho messi insieme perché, mentre sono sempre concentrati come funzionalità di programmazione funzionale, si sono fatti strada così velocemente in linguaggi altrimenti imperativi che è difficile chiamarli più funzionali.

S-Espressioni

Immagino di non essere sicuro di dove metterlo, ma la possibilità di trattare il codice non compilato come un oggetto (e controllarlo / modificarlo), come Lisp S-Expressions o LINQ Expressions, è, in qualche modo, lo strumento più potente della programmazione funzionale. La maggior parte delle nuove interfacce "fluenti" .NET e DSL utilizzano una combinazione di sintassi lambda e LINQ Expressions per creare alcune API molto concise. Per non parlare di Linq2Sql / Linq2Nhibernate in cui il codice C # è "magicamente" eseguito come SQL anziché come codice C #.




Con un limite superiore fisso sull'utilizzo della memoria, non dovrebbero esserci differenze.

Schermata di prova: dato un limite superiore fisso sull'utilizzo della memoria, si dovrebbe essere in grado di scrivere una macchina virtuale che esegue un insieme di istruzioni imperativo con la stessa complessità asintotica come se si stesse effettivamente eseguendo su quella macchina. Questo perché è possibile gestire la memoria mutabile come una struttura di dati persistente, dando O (log (n)) in lettura e scrittura, ma con un limite superiore fisso sull'utilizzo della memoria, è possibile avere una quantità fissa di memoria, causando questi a decadimento a O (1). Quindi l'implementazione funzionale può essere la versione imperativa in esecuzione nell'implementazione funzionale della VM, e quindi entrambi dovrebbero avere la stessa complessità asintotica.




Related