www.jammni.de

Gepostet:
05.03.2011 15:27

concat :: [[a ]] → [a ]

Und direkt die nächste Frage:

Concatenate a list of lists:
concat :: [[a ]] → [a ]

Meine Überlegung ist nun folgende:

Angenommen ich habe eine Liste von Listen:

[[1,2],[3,4],[5,6]]

Dann müsste ich diese doch folgendermaßen verbinden:

[1,2] ++ [3,4] ++ [5,6] ++ []

Warum funktioniert dann folgendes nicht:

concat' :: [[a]]->[a]
concat' [] = [] -- die leere Liste soll die leere Liste zurückgeben
concat' [x] = x -- concat' [[1,2]] soll [1,2] zurückgeben
concat' [(x:xs)] = x ++ concat' [xs] --concat' [[1,2],[3,4],[5,6]] soll [1,2] ++ concat' [[3,4],[5,6]] zurückgeben

Zum Seitenanfang

domjoe

Gepostet:
05.03.2011 15:35

Ich habs:

concat' :: [[a]]->[a]
concat' [] = []
concat' (x:xs) = x ++ concat' (xs)

einfach zu kompliziert gedacht!

Zum Seitenanfang

Landei

Gepostet:
05.03.2011 19:05

Das ist eine typische Anwendung für foldl. foldl erwartet 3 Argumente: Eine Operation zum "Zusammenfügen", einen Startwert, und eine Liste:


concat' xs = foldl (++) [] xs

-- oder kürzer
concat' = foldl (++) []

Erst wird der Startwert und das erste Listenelement über die gegebene Operation verknüft, dann das Ergebnis mit dem zweiten Listenelement, dann das Ergebnis mit dem dritten u.s.w.

Es gibt auch eine Variante, die die Liste von hinten (oder "rechts") aufdröselt und (wenig überraschend) foldr heißt.

Beim Herumspielen bin ich übrigens noch auf diese lustige Variante gestoßen:


concat' xss = do xs <- xss; xs

Natürlich alles bloß Tarnung: Die concat-Funktion ist für Monaden zur join-Funktion verallgemeinert worden, und obiger Schnippsel drückt join in do-Notation aus (äquivalent zu xss >>= id).

Zum Seitenanfang

domjoe

Gepostet:
06.03.2011 10:04

Das zweite Beispiel verstehe ich noch nicht! Auch habe ich die Funktionsweise von Monaden noch nicht vollends verstanden! Aber ich arbeite dran!

Zum Seitenanfang

Landei

Gepostet:
06.03.2011 10:47

Ist vielleicht gar kein schlechtes Einsteigsbeispiel. Für das Folgende brauchst du import Control.Monad:

join ist eine Verallgemeinerung von concat für verschachtelte Listen, sozusagen "wenn du zweimal denselben Typ verschachtelt hast, lass eine Verschachtelungsebene weg". Also macht er aus [[1,2,3],[4,5],[],[6,7,8]] genau das Gleiche wie ein concat. Für andere Typen funktioniert das ähnlich, etwa für Maybe:

join (Just (Just 3)) ist Just 3,
join (Just Nothing) oder join Nothing ist Nothing u.s.w.

join hat die Signatur join :: (Monad m) => m (m a) -> m a, woran man schön erkennen kann, dass die äußere Monade "abgepellt" wird.

Monaden müssen zwei Funktionen definieren, und zwar return und >>= (auch "bind" genannt).
return "verpackt" einen einzelnen Wert in eine Monade:
(return 3) :: [Int] gibt [3],
(return 3) :: Maybe Int gibt Just 3.

Interessanter ist >>=, das eine Monade durch eine Funktion verändert, so ähnlich wie das map für Listen tut. Es hat den Typ (>>=) :: (Monad m) => m a -> (a -> m b) -> m b. Wenn man z.B. alle Listenelemente doppelt hintereinander schreiben wollte, ginge das so:
[1,2,3,4,5] >>= (\x -> [x,x]) ergibt[1,1,2,2,3,3,4,4,5,5]

join lässt sich mit >>= ausdrücken (und umgekehrt). Die Signatur von >>= lautet (>>=) :: (Monad m) => m a -> (a -> m b) -> m b. Setzt man an dieser Stelle für a den Ausdruck m b ein, erhält man m (m b) -> (m b -> m b) -> m b. Ersetzt man die mittlere Funktion noch fest durch die Identitätsfunktion id, bleibt m (m b) -> m b übrig, genau die Signatur von join. Deshalb gilt:
join xxs = xss >>= id

Die do-Natation ist nur syntaktischer Zucker für eine Kette aus >>=, return u.s.w., und kann nach einfachen Regeln abgeleitet werden.

Die von mir hier verwendete Sichtweise von Monaden als "Verpackungen" ist für den Einstieg sehr praktisch und hilft, ein grundlegendes Verständnis zu bekommen, was da vorgeht, ist aber zu beschränkt. Die eigentliche Schwierigkeit bei Monaden ist, auch die eine allgemeinere Sichtweise als "Aktion mit einem Effekt" zu verstehen, ohne die Monaden wie IO, State, Reader, Writer u.s.w. rätselhaft bleiben.

Eine gute Einführung gibt http://learnyouahaskell.com/a-fistful-of-monads - allerdings wirst du aus den vorigen Kapiteln noch Functor unf Applicative nachschlagen müssen.

Zum Seitenanfang

Haskell-Forum