domingo, 3 de abril de 2016

¡Quicksort en Haskell!



Me estoy robando un pedazo de código de : http://aprendehaskell.es/content/Recursion.html que es un excelente libro. No digan nada...

Básicamente me tiene obnubilado quicksort en Haskell, decir si les cuento lo que hace o leen el código, es lo mismo porque el código pinta exactamente el algoritmo, sin agregar nada.

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

Si no lo entendes por que andas flojo de Haskell te lo explico, las primera linea declara la función.

quicksort :: (Ord a) => [a] -> [a]

En la segunda dice, si viene una lista vacía ya fue, el resultado es una lista vacía.

quicksort [] = []

En la tercera linea utiliza pattern matching, para separar el primer elemento del resto. Es decir, lo que esta diciendo es: si no es vacía, separala en el primer elemento "x" y el resto "xs".

quicksort (x:xs) =

En las 2 lineas siguientes define 2 listas la de menores y mayores, para esto utiliza listas por comprensión:

 [a | a <- xs, a <= x]

Es decir, aquí se esta diciendo: a tal que a pertenezca a xs (es decir al resto)  y  que a sea menor o igual que x. De la misma forma define el mayor pero con mayor (y claro!)

Y estas listas las ordena con el algoritmo quicksort utilizando recursividad.

Definidas estas listas devuelve la concatenación de la lista de elementos menores a x (ordenada), x  y los mayores a x. Por lo que devuelve la lista ordenada.

Y listo!!!