questa implementazione di merge sort è buona?

Question

Ho appena iniziato a imparare Haskell la scorsa notte e non ho mai usato un linguaggio di programmazione funzionale prima. Voglio solo sapere se la mia implementazione di merge sort è buona o cattiva e cosa è esattamente buono o cattivo. Forse è anche sbagliato - Beh, funziona, ma forse l'Algorithm non è quello che penso sia l'unire sort.

Dimmi solo tutto quello che potrei migliorare qui. Da solo penso che sia un'implementazione abbastanza chiara e semplice. Grazie per i vostri consigli, ecco il codice :)

merge [] ys = ys 
merge xs [] = xs 
merge xs ys = sorted : merge left right 
       where 
        sorted = if head(xs) < head(ys) then head(xs) else head(ys) 
        left = if head(xs) <= head(ys) then tail(xs) else xs 
        right = if head(xs) > head(ys) then tail(ys) else ys 

msort [] = [] 
msort [x] = [x] 
msort xs = merge (msort left) (msort right) 
      where 
       left = take (div (length xs) 2) xs 
       right = drop (div (length xs) 2) xs 

Answer 1

Beh, prima di tutto, possiamo riscrivere merge per essere un po 'più elegante utilizzando pattern matching

merge [] ys = ys 
merge xs [] = xs 
merge xs@(x:xs1) ys@(y:ys1) 
    | x <= y = x : merge xs1 ys 
    | otherwise = y : merge xs ys1 

In generale si dovrebbe evitare di utilizzare head e tail poiché sono un po 'non sicuri (generano un errore per la lista vuota) e usano la corrispondenza del modello quando possibile.

L'implementazione di msort è praticamente azzeccata, tranne che possiamo dividere l'elenco in un modo più efficiente. Questo perché length xs - richiede O (N) per completare. Il compilatore potrebbe salvarti e memorizzare nella cache il risultato della chiamata length in modo che la seconda chiamata a length non attraversi nuovamente l'elenco. Ma lo take e lo drop causeranno praticamente altri due attraversamenti, dividendo così la lista con 3 attraversamenti che possono rivelarsi costosi. Siamo in grado di fare meglio suddividendo la lista in due liste - la prima contenente gli elementi sulle posizioni dispari e il secondo elenco con gli elementi posti su posizione pari, in questo modo:

msort [] = [] 
msort [x] = [x] 
msort xs = merge (msort first) (msort second) 
    where 
     (first, second) = splitInHalves xs 
     splitInHalves [] = ([], []) 
     splitInHalves [x] = ([x], []) 
     splitInHalves (x:y:xs) = 
      let (xs1, ys1) = splitInHalves xs 
      in (x:xs1, y:ys1) 

In questo modo si ottiene la stessa Unisci Ordina in tempo O (NlogN). Sembra diverso perché probabilmente lo implementerai sul posto (modificando la lista originale) in un linguaggio imperativo come C. Questa versione è leggermente più costosa sulla memoria, ma ha i suoi vantaggi - è più facile ragionare su , quindi è più manutenibile, ed è anche molto semplice per parallelize senza preoccuparsi di nient'altro che dell'algoritmo stesso - che è esattamente ciò che un buon linguaggio di programmazione dovrebbe fornire agli sviluppatori che lo usano.

EDIT 1:

Se la sintassi è un po 'troppo, ecco alcune risorse:

• Pattern Matching - il bit con il simbolo @ è chiamato un come-modello. Lo troverai lì
• let è una parola chiave utilizzata per dichiarare una variabile da utilizzare nell'espressione che la segue (mentre where associa una variabile nell'espressione che lo precede).Altro su sintassi Haskell, tra cui guardie (le cose con | condition = value) può essere trovato qui, in questo capitolo della Learn You a Haskell

EDIT 2:

@ is7s hanno proposto una versione molto più concisa della splitInHalves utilizzando il foldrfunction:

splitInHalves = foldr (\x (l,r) -> (x:r,l)) ([],[]) 

EDIT 3:

012.351.

Ecco un'altra risposta che fornisce un'implementazione alternativa di merge sort, che ha anche la proprietà di essere stable:

Lazy Evaluation and Time Complexity

Spero che questo aiuti e benvenuti nel meraviglioso mondo della programmazione funzionale!