fold #
Die Funktion summe
summe :: Num a => [a] -> a summe [] = 0 summe (x:xs) = x + summe xs
alternativ mit Hilfe von foldr definiert
summe = foldr (+) 0
welches selbst wiederum in etwa so definiert werden kann
foldr :: (a -> b -> b) -> b -> [a] -> b foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs)
auf eine Liste [1..3] angewandt, ergibt
> summe (1 : 2 : 3 : []) 6
oder anders ausgedrückt
> 1 + (2 + (3 + 0)) 6
kann folgendermaßen verallgemeinert werden:
auf eine Liste [1..n]
x1 : (x2 : ··· : (xn-1 : (xn : []))···)
foldr (+) 0 angewandt, ergibt
x1 + (x2 + ··· + (xn-1 + (xn + 0))···)
Ähnlich kann auch mit foldl
foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v [] = v foldl f v (x:xs) = foldl f (f v x) xs
vorgegangen werden (wir sparen uns diesesmal allerdings eine Definiton von produkt und wenden foldl gleich direkt an)
> foldl (*) 1 (2 : 3 : 4 : []) 24
gleichbedeutend mit
> ((1 * 2) * 3) * 4 24
oder allgemeiner formuliert:
eine Liste
x1 : (x2 : ··· : (xn-1 : (xn : []))···)
wird zu
(···((1 * x1) * x2) * ··· * xn-1) * xn
wenn foldl (*) 1 auf diese angewandt wird.
Links: