Softwerkskammer

 

Schleifen, Kapitel 4, 2. Teil

  1. Explizite Tail Recursion
  2. map
  3. foldl und foldr
  4. foldl'

Explizite Schleife mit Tail Recursion

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

asInt (unfoldr (\b -> if b == 0 then Nothing else Just ('1', b-1)) 1e8)

Laufzeit ca. 10 Sekunden, Speicherverbrauch:
asInt Speicherverbrauch

Map

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
square2 xs = map f xs
             where f x = x*x

MyMap

Die Funktionalität von map kann zur Veranschaulichung so implementiert werden:

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

alleUngeraden :: [Int] -> [Int]

alleUngeraden (x:xs) | odd x = x : alleUngeraden xs
                     | otherwise = alleUngeraden xs
alleUngeraden _ = []

Variante 2: Mit der Funktion filter

alleUngeraden2 xs = filter odd xs

Eine Antwort aus einer Liste errechnen: foldl

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]

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]    

*Main> bsp
0 + 1
1 + 2
3 + 3
6
*Main>

Dank TCO ist alles gut, oder?

$ ghci +RTS -K2M -RTS MyFoldl.hs
GHCi, version 7.8.3: http://www.haskell.org/ghc/  :? for help
...
Ok, modules loaded: Main.
*Main> myfoldl (+) 0 [1..10e4]
*** Exception: stack overflow

myfoldl (+) 0 [1..1e6]

Profiling: siehe Kapitel 25

myfoldl Speicherverbrauch

Nicht strikte Evaluierung und foldl

myfoldl step acc (x:xs) = myfoldl step (step acc x) xs
myfoldl _ acc [] = acc

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

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.

myfoldl' step acc (x:xs) = let stepresult = step acc x
                           in seq stepresult (myfoldl' step stepresult xs)
myfoldl' _ acc [] = acc

myfoldl' Speicherverbrauch

myfoldl' Speicherverbrauch

foldl'

*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

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

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]))

myfoldr Speicherverbrauch

foldr Einzelschritte

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

-- 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)

foldr als Transformation

  • 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

foldr (:) [] [1..3]

Beispiel 2: append

foldr (:) [1,2,3] [1..3]

 

Aktivitäten