Ich lese gerade das Buch „Programming in Haskell“ und habe verschiedene Wege ausprobiert, um zu überprüfen, ob eine Liste aufsteigend sortiert ist.
Die einfachste und eleganteste Art, das zu überprüfen, ist es, die Liste zu sortieren und diese mit der ursprünglichen Liste zu vergleichen. Sind beide gleich, dann muss die ursprüngliche Liste logischerweise schon sortiert gewesen sein.
|
1 2 3 |
import Data.List (sort) mysorted :: Ord a => [a] -> Bool mysorted xs = xs == sort xs |
Eine andere Methode habe ich aus dem o.g. Buch entnommen. Sie benutzt List Comprehensions und erzeugt eine Liste von Tupeln mit jeweils dem ersten und dem folgenden Element und vergleicht diese miteinander.
Wenn z.B. die Liste [1, 2, 3, 4] mit zip bearbeitet wird, dann entsteht folgende Liste von Tupeln: [(1, 2), (2, 3), (3,4)]. Dann werden einfach die Tupelelemente verglichen und die Ergebnisse der Vergleiche and-verknüpt.
|
1 2 |
mysorted2 :: Ord a => [a] -> Bool mysorted2 xs = and [f <= s | (f, s) <- zip xs (tail xs)] |
Diese Lösung finde ich sehr interessant und einfallsreich.
Ich habe mich gefragt, ob man das auch anders machen kann, so ähnlich wie man es in anderen Programmiersprachen machen würde. Das ist dabei herausgekommen.
|
1 2 3 4 |
mysorted3 :: Ord a => [a] -> Bool mysorted3 (x : xs) | null xs = True | otherwise = (x <= head xs) && mysorted3 xs |
Hier benutze ich Guards (die Zeilen mit dem | (Pipesymbol). Wenn der Rest xs eine leere Liste ist (null xs) dann ist die Liste sortiert. Sonst ist die Liste sortiert, wenn das jeweils erste Element x kleiner oder gleich dem ersten Element der Restliste ist und wenn die Restliste auch sortiert ist (Rekursion).
Zu guter Letzt habe ich mich gefragt, ob man auch foldl benutzen kann, um die Sortiert-Eigenschaft einer Liste zu überprüfen. Man kann, aber es ist mir nur eine hässliche Lösung eingefallen.
|
1 2 |
mysorted4 :: Ord a => [a] -> Bool mysorted4 xs = fst (foldl (\(a, b) c -> (a && (b <= c), c)) (True, head xs) xs) |
Foldl befeuert eine Funktion (hier Lambda) mit 2 Werten: zuerst mit dem Akkumulator und dann mit dem jeweiligen nächsten Listenelement. Die Herausforderung war hier, irgendwie das boolesche Ergebnis des Vergleichs und das vorherige Listenelement in den Akkumulatorwert zu packen. Ich mache das hier mit einem Tupel (Bool, Ord) und hole das Ergebnis mit fst ab.
Was hältst Du davon? Über Kommentare würde ich mich sehr freuen.
Und hier das ganze Programm zum Ausprobieren:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import Data.List (sort) mysorted :: Ord a => [a] -> Bool mysorted xs = xs == sort xs mysorted2 :: Ord a => [a] -> Bool mysorted2 xs = and [f <= s | (f, s) <- zip xs (tail xs)] mysorted3 :: Ord a => [a] -> Bool mysorted3 (x : xs) | null xs = True | otherwise = (x <= head xs) && mysorted3 xs mysorted4 :: Ord a => [a] -> Bool mysorted4 xs = fst (foldl (\(a, b) c -> (a && (b <= c), c)) (True, head xs) xs) main :: IO () main = do print $ mysorted [1] print $ mysorted [1, 2, 3] print $ mysorted [1, 2, 5, 3] print $ mysorted2 [1] print $ mysorted2 [1, 2, 3] print $ mysorted2 [1, 2, 5, 3] print $ mysorted3 [1] print $ mysorted3 [1, 2, 3] print $ mysorted3 [1, 2, 5, 3] print $ mysorted4 [1] print $ mysorted4 [1, 2, 3] print $ mysorted4 [1, 2, 5, 3] |