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!!!
