Sortiere(Haskell)

Aus IT074-Wiki

Rekursion

Das Prinzip ist dem der rekursiven Sort-Funktion in Python sehr ähnlich:

• ermittle das Minimum der aktuellen Liste
• verkette es mit dem Ergebnis der Sortierung der Liste ohne dieses Minimum

sort []     = []
sort (x:xs) = filter(==foldl min x xs)(x:xs) ++ sort(filter(/=foldl min x xs)(x:xs))
 
-- Wie ich später festgestellt habe, gibt es zwei Listenfunktionen, die den Quelltext noch etwas reduzieren:
-- foldl1 und minimum
 
-- sort mit foldl1:
sort [] = []
sort xs = filter(==foldl1 min xs)xs ++ sort(filter(/=foldl1 min xs)xs)
 
-- sort mit minimum:
sort [] = []
sort xs = filter(==minumum xs)xs ++ sort(filter(/=minumum xs)xs)

Legende:

• [] ist die leere Liste
• a:L fügt das Element a der Liste L hinzu (immer linksseitig: 1:2:3:4:[] == [1,2,3,4])
• x:xs bedeutet daher: x (erstes Element der übergebenen Liste) xs (Restliste)
• ++ verkettet Listen
• foldl & foldl1: Erklärung folgt demnächst

Zum Ausprobieren empfehle ich den Glasgow Haskell Compiler, der auch über eine interaktive Umgebung verfügt, wie in folgendem Screenshot zu sehen ist: