Haskell - Guida alla programmazione funzionale

Question

Cercare di avere un'idea di haskell. Sono un programmatore esperto con PHP, JAVA, VB e molte altre lingue, ma trovo haskell leggermente più difficile da seguire. Qualcuno mi può dare una inglese traduzione per la seguente funzione Haskell, per ottenerlo iniziato ...

quicksort []  = [] 
quicksort (x:xs) = quicksort [y | y <- xs, y<x ] 
        ++ [x] 
        ++ quicksort [y | y <- xs, y>=x] 

Un esempio di inglese traduzione è nei commenti qui sotto:

// --- FOR_LOOP -> 
// --- $abc goes from 1 to 10 -> 
// --- If $abc is even - print $abc is even -> 
// --- else if $abc is odd - print $abc is odd -> 
// --- END_FOR_LOOP 

for($abc = 1 ; $abc <= 10 ; $abc++){ 

    if($abc % 2 == 0){ 
    echo $abc . " is even"; 
    } 
    else{ 
    echo $abc . " is odd"; 
    } 
} 

La prima riga è abbastanza semplice, leggendo: "quicksort funzione su una lista vuota produce un elenco vuoto come il risultato" ... Se è possibile tradurre il resto dell'hashell in inglese t cappello sarebbe molto utile.

Answer 1

Il risultato di quicksorting della lista vuota è la lista vuota.

Il risultato di quicksorting una lista non vuota, dove chiamiamo il primo elemento della lista x ei restanti elementi xs è: Il risultato di quicksorting tutti gli elementi di xs che sono inferiori a x (*), seguita da x, seguito dal risultato di quicksorting di tutti gli elementi di x che sono maggiori di x.

(*) Per elaborare un bit: [y | y <- xs, y<x ] può essere letto come "l'elenco di tutti y y è in xs e y<x".

Answer 2

Questo non risponde direttamente alla tua domanda, ma hoogle può aiutare il tuo apprendimento in generale, puoi usarlo per cercare le librerie di API standard con il nome di una funzione, o con una firma di tipo approssimativa.

Ecco alcuni esempi di termini di ricerca che supporta:

map 
(a -> b) -> [a] -> [b]` 
Ord a => [a] -> [a] 
Data.Map.insert 

Answer 3

non l'hanno fatto dai tempi del college ...

E 'ricorsiva - la prima linea è il caso di un insieme vuoto.

quicksort []  = [] 

Le righe successive funzionano su un set non vuoto. La sintassi (x: xs) lo suddivide in un singolo elemento (x) e gli elementi rimanenti (xs).

quicksort (x:xs) = quicksort [y | y <- xs, y<x ] 
    ++ [x] 
    ++ quicksort [y | y <- xs, y>=x] 

La prima riga, quicksort [y | y < - xs, y < x], chiama quicksort rispetto all'insieme di tutti gli elementi da xs che sono minori di x (cioè ogni y da xs che è minore di x). Se xs è il set vuoto, quicksort [] restituirà [].

La riga centrale è semplicemente l'insieme contenente x.

L'ultima riga, quicksort [y | y < - xs, y > = x], chiama quicksort rispetto all'insieme di tutti gli elementi da xs maggiori o uguali a x (cioè ogni y da xs che è maggiore o uguale a x). Se xs è il set vuoto, quicksort [] restituirà [].

Il risultato finale è un set ordinato.

Answer 4

È un linguaggio dichiarativo, quindi leggi solo quello che vedi. sepp2k fa un buon esempio sopra.

Answer 5

Controlla http://learnyouahaskell.com/recursion#quick-sort spiega esattamente cosa fa quicksort.

Answer 6

Nel caso in cui il problema è stato in-familiarità con la list comprehension, ecco alcune versioni alternative che sono più o meno lo stesso:

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

quicksort []  = [] 
quicksort (x:xs) = 
    quicksort smaller ++ [x] ++ quicksort bigger 
    where 
    (smaller, bigger) = partition (< x) xs