Funktionale Programmierung: Fold-Funktionen

Literatur

Typische Struktur

für einfache Listenfunktionen

f          :: [a] -> b
 
f  []      =  e
f (x : xs) =  x `op` f xs

Beispiele

sum          :: Num a => [a] -> a
 
sum  []      =  0
sum (x : xs) =  x + sum xs

length          :: [a] -> Int
 
length  []      =  0
length (x : xs) =  1 + length xs

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

and          :: [Bool] -> Bool
 
and  []      =  True
and (x : xs) =  x && and xs

fast

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

Transformation in obiges Schema?

Verarbeitung

x1 : (x2 : (x3 : []))

wird transformiert in

x1 `op` (x2 `op` (x3 `op` e))

Abstraktion

von der Operation

Trennung von Kontrollstruktur und Verarbeitung

Definition: foldr

fold right

`op` bezeichnet eine rechtsassoziative Operation

foldr               :: (a -> b -> b) -> b ->
                       [a] -> b
 
foldr op e  []      =  e
foldr op e (x : xs) =  x `op` (foldr op e xs)

Rekursionstyp?

Beispiele

sum    = foldr (+) 0
 
concat = foldr (++) []
 
and    = foldr (&&) True
 
length = foldr oneplus 0
         where
         oneplus x n = 1 + n
 
-- kürzer
 
length = foldr (\ x -> (1+)) 0
 
-- noch kürzer
 
length = foldr (const (1+)) 0

length mit sum?

reverse mit foldr?

Laufzeit von reverse mit foldr?

Identität für Listen mit foldr?

map mit foldr?

filter mit map implementiert.

map mit foldr implementiert.

Aber: Direkte Implementierung von map kann effizienter sein als foldr.

linksassoziative Operationen mit fold?

Beispiel

Horner-Schema

    decimal [x0, x1, x2]
  =
    ((0 * 10 + x0) * 10 + x1) * 10 + x2
  =
    ((0 `op` x0) `op` x1) `op` x2
    where
    n `op` x = n * 10 + x

foldl

fold left

    foldl op e [x0, x1, ..., xn]
  =
    (...((e `op` x0) `op` x1) ...) `op` xn

Definition

foldl               :: (b -> a -> b) -> b ->
                       [a] -> b
 
foldl op e  []      =  e
foldl op e (x : xs) =  foldl op (e `op` x) xs

Rekursionstyp?

Beispiel

reverse = foldl snoc []
          where
          snoc xs x = x : xs
 
-- oder
 
reverse = foldl (flip (:)) []

Laufzeit von reverse mit foldl?

concat mit foldl?

Laufzeit von concat mit foldl?

Maximum und Minimum über Listen mit fold?

Problem

Wert der leeren Liste?

Lösung

Varianten von fold für nicht leere Listen

foldr1  :: (a -> a -> a) -> [a] -> a
 
foldr1 op (x : xs)
  | null xs     = x
  | otherwise   = x `op` foldr1 op xs

foldl1  :: (a -> a -> a) -> [a] -> a
 
foldl1 op (x : xs)
  = foldl op x xs

 Das letzte (foldr) oder das erste Element (foldl) wird für
das fehlende e verwendet.

Beispiele

minimum :: Ord a => [a] -> a
minimum = foldl1 min
 
maximum :: Ord a => [a] -> a
maximum = foldl1 max

scanl

Verarbeiten aller Anfangsstücke einer Liste

    scanl op e [x0, x1, x2, ...]
  =
    [ e
    , e `op` x0
    , (e `op` x0) `op` x1
    , ((e `op` x0) `op` x1) `op` x2
    , ...
    ]

Beispiel

die zu einer Zahlenfolge gehörige Reihe

scanl (+) 0
 
-- Beispiele
 
scanl (+) 0 (repeat 1)         = ???
scanl (+) 0 [1..]              = ???

Definition

scanl               :: (a -> b -> b) -> b ->
                       [a] -> [b]
 
scanl op e  []      = []
scanl op e (x : xs) = e : scanl op (e `op` x) xs

scanl mit fold?

Gesetze

für fold Funktionen

1. Dualitätsgesetz

für assoziative Operationen `op` mit e als neutralem Element und endlichen Listen xs gilt

foldr op e xs = foldl op e xs

Beispiele

sum     = foldl (+) 0
and     = foldl (&&) True
or      = foldl (||) False
concat  = foldl (++) []

2. Dualitätsgesetz

Wenn op1, op2 die folgenden Bedingungen erfüllen, dann gilt für endliche Listen xs:

x `op1` (y `op2` z) = (x `op1` y) `op2` z
x `op1` e           = e `op2` x
 
foldr op1 e xs = foldl op2 e xs

Das erste Gesetz ist Spezialfall des zweiten.

Beweis?

foldl und foldr auf unendlichen Listen?