Programmazione funzionale per algoritmi di base

Question

Quanto è utile la programmazione funzionale "pura" per le implementazioni di routine di base, ad es. elenca l'ordinamento, la corrispondenza delle stringhe, ecc.?

È comune implementare tali funzioni di base nell'interprete di base di qualsiasi linguaggio funzionale, il che significa che verranno scritte in un linguaggio imperativo (c/C++). Sebbene ci siano molte eccezioni ..

Almeno, vorrei chiedere: quanto è difficile emulare lo stile imperativo mentre si codifica in un linguaggio funzionale "puro"?

Answer 1

Come bene è 'pura' di programmazione funzionale per base di routine implementazioni, ad esempio, lista di ordinamento, corrispondenza di stringhe, ecc.?

Molto. Farò i tuoi problemi in Haskell, e sarò un po 'prolisso a riguardo. Il mio scopo non è quello di convincerti che il problema può essere fatto in 5 caratteri (probabilmente in J!), Ma piuttosto per darti un'idea dei costrutti.

import Data.List -- for `sort` 
stdlistsorter :: (Ord a) => [a] -> [a] 
stdlistsorter list = sort list 

Ordinamento di un elenco utilizzando la funzione sort da Data.List

import Data.List -- for `delete` 
selectionsort :: (Ord a) => [a] -> [a] 
selectionsort [] = [] 
selectionsort list = minimum list : (selectionsort . delete (minimum list) $ list) 

implementazione Selezione sorta.

quicksort :: (Ord a) => [a] -> [a] 
quicksort [] = [] 
quicksort (x:xs) = 
    let smallerSorted = quicksort [a | a <- xs, a <= x] 
     biggerSorted = quicksort [a | a <- xs, a > x] 
    in smallerSorted ++ [x] ++ biggerSorted 

Implementazione rapida.

import Data.List -- for `isInfixOf` 
stdstringmatch :: (Eq a) => [a] -> [a] -> Bool 
stdstringmatch list1 list2 = list1 `isInfixOf` list2 

corrispondenza String utilizzando isInfixOf funzione dal Data.list

E 'comune per attuare tali fondamentali funzioni all'interno l'interprete di base di qualsiasi linguaggio funzionale, che significa che saranno scritti in un imperativo linguaggio (c/C++). Anche se ci sono molte eccezioni ..

Depends. Alcune funzioni sono espresse in modo più naturale imperativamente. Tuttavia, spero di averti convinto che alcuni algoritmi sono espressi naturalmente in modo funzionale.

Almeno, vorrei chiedere: come difficile è di emulare lo stile imperativo durante la codifica in 'puro' linguaggio funzionale?

Dipende da quanto sia difficile trovare Monads in Haskell. Personalmente, trovo molto difficile da capire.

Answer 2

Funziona piuttosto bene, al contrario, emulazione funzionale con stile imperativo.

Ricordare che l'interno di un interprete o di un VM VM è così vicino al metallo e le prestazioni critiche che si dovrebbe anche considerare di andare a livello di memoria e contare i cicli di clock per ogni istruzione (come Smalltalk Dophin lo sta facendo e i risultati sono impressionanti). Le CPU sono indispensabili.

Ma non c'è alcun problema a fare tutte le implementazioni di base dell'algoritmo - quelle che menzioni sono NON a basso livello - sono fondamentali.

Answer 3

Quasi tutti i linguaggi di programmazione funzionale hanno alcuni costrutti per consentire la codifica imperativa (come do in Haskell). Esistono molti domini problematici che non possono essere risolti con la programmazione funzionale "pura". Uno di questi è i protocolli di rete, ad esempio dove è necessario una serie di comandi nell'ordine corretto. E tali cose non si prestano bene alla pura programmazione funzionale.

Devo concordare con Lothar, tuttavia, che l'ordinamento dell'elenco e la corrispondenza delle stringhe non sono davvero degli esempi che è necessario risolvere imperativamente. Esistono algoritmi noti per queste cose e possono essere implementati in modo efficiente nei linguaggi funzionali già.

Answer 4

Penso che gli "algoritmi" (ad esempio i corpi dei metodi e le strutture di dati di base) siano dove la programmazione funzionale è la migliore. Supponendo che nulla di completamente IO/dipendente dallo stato, la programmazione funzionale eccelle sono algoritmi di authoring e strutture dati, spesso risultanti in un codice più breve/più semplice/più pulito di quello che otterresti con una soluzione imperativa. (Non emulare uno stile imperativo, lo stile FP è migliore per la maggior parte di questi tipi di attività.)

A volte è necessario disporre di elementi imperativi per gestire l'I/O o le prestazioni di basso livello e si desidera OOP per il partizionamento di alto livello design e architettura di un grande programma, ma "nel piccolo" dove scrivi la maggior parte del tuo codice, FP è una vittoria.

Vedi anche

How does functional programming affect the structure of your code?

Answer 5

Non so su lista ordinamento, ma si sarebbe difficile per bootstrapp una lingua senza un qualche tipo di corrispondenza stringa nel compilatore o runtime. Quindi hai bisogno di quella routine per creare la lingua. Dato che non c'è una grande quantità di punti che scrivono lo stesso codice due volte, quando si crea la libreria per le stringhe corrispondenti all'interno della lingua, si chiama il codice scritto in precedenza. Il grado in cui ciò accade nelle versioni successive dipenderà dal modo in cui l'hosting automatico della lingua è, ma a meno che non si tratti di un forte obiettivo di progettazione non ci sarà alcun motivo per cambiarlo.

Answer 6

1) Buono in base a quale standard? Quali proprietà desideri?

Elenco ordinamento? Facile.Facciamolo Quicksort in Haskell:

sort [] = [] 
sort (x:xs) = sort (filter (< x) xs) ++ [x] ++ sort (filter (>= x) xs) 

Questo codice ha il vantaggio di essere estremamente facile da capire. Se la lista è vuota, è ordinata. Altrimenti, chiama il primo elemento x, trova gli elementi minori di x e ordinali, trova elementi maggiori di x e ordinali. Quindi concatena le liste ordinate con x nel mezzo. Prova a rendere questo aspetto comprensibile in C++.

Ovviamente, Mergesort è molto più veloce per l'ordinamento di elenchi collegati, ma il codice è anche 6 volte più lungo.

2) È estremamente facile implementare lo stile imperativo pur rimanendo puramente funzionale. L'essenza dello stile imperativo è il sequenziamento delle azioni. Le azioni sono sequenziate in un contesto puro usando le monadi. L'essenza delle monadi è la funzione di legante:

(Monad m) => (>>=) :: m a -> (a -> m b) -> m b 

Questa funzione esiste in C++, e si chiama ;.

una sequenza di azioni a Haskell, per esempio, è scritto così:

putStrLn "What's your name?" >>= 
    const (getLine >>= \name -> putStrLn ("Hello, " ++ name)) 

po 'di zucchero sintassi è a disposizione per rendere questo look più imperativa (ma si noti che questo è il esattamente lo stesso codice):

do { 
    putStrLn "What's your name?"; 
    name <- getLine; 
    putStrLn ("Hello, " ++ name); 
}