- Explizite Tail Recursion
- map
- foldl und foldr
- foldl'
Explizite Schleife mit Tail Recursion
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | import Data.Char (digitToInt)
asInt :: String -> Int
asInt xs = loop 0 xs
loop :: Int -> String -> Int
-- recursive case
loop acc (x:xs) = let acc' = acc * 10 + digitToInt x
in loop acc' xs
-- base or tail case
loop acc _ = acc
ok = (123 == asInt "123") &&
(0 == asInt "") &&
(6171178737961038279 == asInt "11111111111111111111111")
|
Tail call optimization
Funktionsaufrufe werden wegoptimiert => Konstanter Platz
haskell asInt (unfoldr (\b -> if b == 0 then Nothing else Just ('1', b-1)) 1e8)
Laufzeit ca. 10 Sekunden, Speicherverbrauch:

Map
1 2 3 4 5 6 7 8 9 10 11 12 | import Data.Char (toUpper)
- - Beispiel 1 : Square
square :: [Double] - > [Double]
square (x:xs) = x * x : square xs
square _ = []
- - Beispiel 2 : Upper Case
upperCase :: String - > String
upperCase (x:xs) = toUpper x : upperCase xs
upperCase [] = []
|
- Wende eine Funktion auf jedes einzelne Element an
- gib die Liste der Ergebnisse zurück
1 2 | square2 xs = map f xs
where f x = x * x
|
MyMap
Die Funktionalität von map kann zur Veranschaulichung so implementiert werden:
1 2 3 4 5 6 7 8 | myMap :: (a - > b) - > [a] - > [b]
myMap f (x:xs) = f x : myMap f xs
myMap _ _ = []
ok = let step = ( + 1 )
in let testf xs = myMap step xs = = map step xs
in and [testf [ 1. . 22 ], testf [], testf [ 1 ]]
|
Filtern oder Auswählen
Variante 1: Explizit
1 2 3 4 5 | alleUngeraden :: [ Int ] - > [ Int ]
alleUngeraden (x:xs) | odd x = x : alleUngeraden xs
| otherwise = alleUngeraden xs
alleUngeraden _ = []
|
Variante 2: Mit der Funktion filter
1 | alleUngeraden2 xs = filter odd xs
|
Eine Antwort aus einer Liste errechnen: foldl
1 2 3 4 5 6 7 | myfoldl :: (b - > a - > b) - > b - > [a] - > b
myfoldl step acc (x:xs) = myfoldl step (step acc x) xs
myfoldl _ acc [] = acc
- - pruefe das Ergebnis von myFoldl
foldlWorks = foldl ( + ) 0 [ 1. . 100 ] = = myfoldl ( + ) 0 [ 1. . 100 ]
|
1 2 3 4 5 | import Debug.trace (trace)
plus a b | trace ((show a) + + " + " + + show b) False = undefined
a b | otherwise = a + b
bsp = myfoldl plus 0 [ 1. . 3 ]
|
1 2 3 4 5 6 | *Main> bsp
0 + 1
1 + 2
3 + 3
6
*Main>
|
Dank TCO ist alles gut, oder?
1 2 3 4 5 6 | $ ghci +RTS -K2M -RTS MyFoldl.hs
...
Ok, modules loaded: Main.
*Main> myfoldl (+) 0 [1..10e4]
*** Exception: stack overflow
|
Profiling: siehe Kapitel 25

Nicht strikte Evaluierung und foldl
1 2 | myfoldl step acc (x:xs) = myfoldl step (step acc x) xs
myfoldl _ acc [] = acc
|
1 2 3 4 5 | 0: myfoldl (+) 0 [1..3] ->
1: myfoldl (+) (stepresult1=0+1) [2..3] ->
2: myfoldl (+) (stepresult2=stepresult1+2) [3]
3: myfoldl (+) (stepresult3=stepresult2+3) []
4: stepresult3 (Rekursion terminiert, acc wird zugewiesen und der thunk reduziert)
|
- es gibt eine innere Funktion (+) und eine äussere Funktion myfoldl
- Die Schritte 1-3 legen reduzierbare Ausdrücke (redex) auf dem Heap ab (nicht strikt Parameterbehandlung der äusseren Funktion myfoldl)
- Erst ab Schritt 4 werden die Ausdrücke ausgewertet. Dazu wird der Stack benötigt. Die erste Zahl (das zweite Funktionsargument) kommt auf den Stack, dann wird das andere Argument ausgerechnet.
Quelle: http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27
myfoldl' mit seq
1 2 | let new = 1 + 2
in new `seq` foldl' ( + ) new []
|
seq evaluiert das erste Argument new zu 3 und gibt das zweite Argument foldl' (+) 3 [] zurück.
1 2 3 | myfoldl' step acc (x:xs) = let stepresult = step acc x
in seq stepresult (myfoldl' step stepresult xs)
myfoldl' _ acc [] = acc
|
myfoldl' Speicherverbrauch

foldl'
1 2 3 4 5 | * Main> import Data. List (foldl')
* Main Data. List > foldl ( + ) 0 [ 1. . 1e5 ]
* * * Exception: stack overflow
* Main Data. List > foldl' ( + ) 0 [ 1. . 1e5 ]
5.00005e9
|
foldr
1 2 3 4 | myfoldr :: (a - > b - > b) - > b - > [a] - > b
myfoldr step acc (x:xs) = step x (myfoldr step acc xs)
myfoldr _ acc [] = acc
|
Achtung: Die Parameter der Step Funktion sind im Vergleich zu foldr vertauscht
haskell import Debug.Trace (trace) plus a b | trace ((show a) ++ " + " ++ show b) False = undefined a b | otherwise = a+b bsp = myfoldr plus 0 [1..3]
*Main> bsp
0 + 3
3 + 2
5 + 1
6
*Main>
myfoldr (+) 0 [1..1e6]))

foldr Einzelschritte
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | foldr (+) 0 [1..1000000] -->
1 + (foldr (+) 0 [2..1000000]) -->
1 + (2 + (foldr (+) 0 [3..1000000])) -->
1 + (2 + (3 + (foldr (+) 0 [4..1000000]))) -->
1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000])))) -->
-- ...
-- ... My stack overflows when there's a chain of around 500000 (+)'s !!!
-- ... But the following would happen if you got a large enough stack:
-- ...
1 + (2 + (3 + (4 + (... + (999999 + (foldr (+) 0 [1000000]))...)))) -->
1 + (2 + (3 + (4 + (... + (999999 + (1000000 + ((foldr (+) 0 []))))...)))) -->
1 + (2 + (3 + (4 + (... + (999999 + (1000000 + 0))...)))) -->
1 + (2 + (3 + (4 + (... + (999999 + 1000000)...)))) -->
1 + (2 + (3 + (4 + (... + 1999999 ...)))) -->
1 + (2 + (3 + (4 + 500000499990))) -->
1 + (2 + (3 + 500000499994)) -->
1 + (2 + 500000499997) -->
1 + 500000499999 -->
500000500000
|
(+) ist strikt in beiden Argumenten.
Siehe http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27
foldr durch foldl implementiert
1 2 3 4 | - - file : ch04 / Fold.hs
myFoldl :: (a - > b - > a) - > a - > [b] - > a
myFoldl f z xs = foldr step id xs z
where step x g a = g (f a x)
|
- arg1 : “what to do with each head/tail element of the list”
- arg2 : “what to substitute for the end of the list”
Beispiel 1: identity
Beispiel 2: append