Grundlagen der Funktionalen Programmierung: Funktionen höherer Ordnung

Beispiel

Alle Elemete einer Liste ohne Berücksichtigung ihrer Position verarbeiten

map :: (a -> b) -> [a] -> [b]
 
map f []       = []
map f (x : xs) = f x : map f xs

2. Beispiel

Filtern von Listen

filter :: (a -> Bool) -> [a] -> [a]
 
filter p []        = []
filter p (x : xs)
  | p x            = x : filter p xs
  | otherwise      =     filter p xs

vordefinierte Funktionen

für All- und Existenz-Quantor

all :: (a -> Bool) -> [a] -> Bool
 
all p []       = True
all p (x : xs) = p x && all p xs

any :: (a -> Bool) -> [a] -> Bool
 
any p []       = False
any p (x : xs) = p x || any p xs

foldr

Falten von Listen

Schema

für die Verarbeitung von Listen

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

Beispiele

sum :: Num a => [a] -> a
sum []            = 0              -- c  = 0
sum (x : xs)      = x + sum xs     -- op = +
 
product :: Num a => [a] -> a
product []       = 1               -- c  = 1
product (x : xs) = x * product xs  -- op = *
 
or :: [Bool] -> Bool
or []            = False           -- c  = False
or (x : xs)      = x || or xs      -- op = ||
 
and :: [Bool] -> Bool
and []           = True            -- c  = True
and (x : xs)     = x && and xs     -- op = &&
 
concat :: [[a]] -> [a]
concat []        = []              -- c  = []
concat (x : xs)  = x ++ concat xs  -- op = ++

Ziel

Verarbeitungsschema parametrisieren und für alle Beispiele wiederverwenden

Abstrahieren

Eine Konstante in einer Funktion zu einem Parameter machen

foldr

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

Beispiele

sum     = foldr (+)  0
product = foldr (*)  1
and     = foldr (&&) True
or      = foldr (||) False
concat  = foldr (++) []
 
all p   = foldr (λ x r  -> p x && r) True
any p   = foldr (λ x r  -> p x || r) False
 
map f   = foldr (λ x rs -> f x : rs) []

Lineare Rekursion

Arbeitsweise

x1 : (x2 : (x3 : []))
 
-- [] ersetzen durch c
-- :  ersetzen durch op
 
x1 `op` (x2 `op` (x3 `op` c))

Manchmal muss eine Funktion erst in eine Normalform gebracht werden,
um sie in ein foldr zu transformieren.

Beispiel

Länge einer Liste

length :: [a] -> Int
 
length []       = 0
length (x : xs) = 1 + length xs
 
==>
 
length []       = 0
length (x : xs) = x `op` length xs
  where
   x `op` n = 1 + n
 
==>
 
length = foldr (λ x n -> 1 + n) 0

2. Beispiel

reverse

reverse :: [a] -> [a]
 
reverse []       = []
reverse (x : xs) = reverse xs ++ [x]
 
==>
 
reverse []       = []
reverse (x : xs) = x `op` reverse xs
  where
   x `op` rs = rs ++ [x]
 
==>
 
reverse = foldr (λ x rs -> rs ++ [x]) []

3. Beispiel

filter

filter :: (a -> Bool) -> [a] -> [a]
 
filter p []        = []
filter p (x : xs)
  | p x            = x : filter p xs
  | otherwise      =     filter p xs
 
==>
 
filter p []        = []
filter p (x : xs)  = x `op` filter p xs
  where
    x' `op` rs
      | p x'       = x' : rs
      | otherwise  =      rs
 
==>
 
filter p = foldr op []
  where
    x `op` rs
      | p x        = x : rs
      | otherwise  =     rs

Berechnungsschema

für foldr

  foldr op c [x0, x1, ..., xn]
=
  x0 `op` (x1 `op` (... (xn `op` c)...))

Die Berechnung wird rechtsassoziativ durchgeführt.

Gibt es ein fold, das linksassoziativ arbeitet?

Beispiel

Aufsummieren

sum :: Num a => [a] -> a
 
sum xs = sum' 0 xs                      -- .0
  where
    sum' r []       = r                 -- .1
    sum' r (x : xs) = sum' (r + x) xs   -- .2

Auswerten

	`sum [1, 2, 3]`
=	{ .0 }
	`sum' 0 [1, 2, 3]`
=	{ .2 }
	`sum' (0 + 1) [2, 3]`
=	{ .2 }
	`sum' ((0 + 1) + 2) [3]`
=	{ .2 }
	`sum' (((0 + 1) + 2) + 3) []`
=	{ .1 }
	`((0 + 1) + 2) + 3`
=	{ rechnen }
	`(1 + 2) + 3`
=	{ rechnen }
	`3 + 3`
=	{ rechnen }
	`6`

Rekursions-Schema

aus sum und sum' ableiten

f xs = f' c xs                        -- c
 
f' acc []       = acc
f' acc (x : xs) = f' (acc `op` x) xs  -- op

foldl

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

Endrekursion

Berechnungsschema

für foldl

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

Die Berechnung wird linksassoziativ durchgeführt.

Beispiele

sum     = foldl (+)  0
product = foldl (*)  1
and     = foldl (&&) True
or      = foldl (||) False
concat  = foldl (++) []
 
all p   = foldl (λ r x -> r && p x) True
any p   = foldl (λ r x -> r || p x) False
 
map f   = foldl (λ rs x -> rs ++ [f x]) []

Wann foldr, wann foldl?

Nicht einheitlich zu beantworten

Beispiel

reverse mit foldl

reverse :: [a] -> [a]
 
reverse = reverse' []
  where
    reverse' acc [] = acc
    reverse' acc (x : xs) = reverse' (x : acc) xs
 
==>
 
reverse = foldl (:) []

foldr: and, or (kurze Auswertung)

foldr: concat (lineare Laufzeit vs. quadratische)

foldr: map (lineare Laufzeit vs. quadratische)

foldl: sum, product (Endrekursion)

foldl: reverse (lineare Laufzeit vs. quadratische)

Gibt es Funktionen höherer Ordnung auf Listen, die nicht mit einem fold verarbeitet werden können?

Beispiel

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
 
zipWith op []       ys       = []
zipWith op xs       []       = []
zipWith op (x : xs) (y : ys) = (x `op` y) : zipWith op xs ys

Anwendung

Vektor-Operationen

addV, subV :: Num a => [a] -> [a] -> [a]
addV = zipWith (+)
subV = zipWith (-)
 
sprod :: Num a => [a] -> [a] -> [a]
sprod = zipWith (*)

module HigherOrderedFct
where
import Prelude hiding ( map
                      , filter
                      , any
                      , all
                      , takeWhile
                      , dropWhile
                      , sum
                      , product
                      , or
                      , and
                      , concat
                      , reverse
                      , foldl
                      , foldr
                      , flip
                      , id
                      , (.)
                      )
twice           :: (a -> a) -> a -> a
twice f x       = f (f x)
map             :: (a -> b) -> [a] -> [b]
map f xs        = [f x | x <- xs]
map' :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x : xs) = f x : map' f xs
filter          :: (a -> Bool) -> [a] -> [a]
filter p xs     = [x | x <- xs, p x]
filter'         :: (a -> Bool) -> [a] -> [a]
filter' p []    = []
filter' p (x : xs)
    | p x       = x : filter' p xs
    | otherwise =     filter' p xs
all            :: (a -> Bool) -> [a] -> Bool
all p []       = True
all p (x : xs) = p x && all p xs
any            :: (a -> Bool) -> [a] -> Bool
any p []       = False
any p (x : xs) = p x || any p xs
takeWhile       :: (a -> Bool) -> [a] -> [a]
takeWhile p []  = []
takeWhile p (x : xs)
    | p x       = x : takeWhile p xs
    | otherwise = []
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p []  = []
dropWhile p (x : xs)
    | p x       = dropWhile p xs
    | otherwise = x : xs
-- foldr
sum             :: Num a => [a] -> a
sum []          = 0
sum (x : xs)    = x + sum xs
product         :: Num a => [a] -> a
product []      = 1
product (x : xs)
                = x * product xs
or              :: [Bool] -> Bool
or []           = False
or (x : xs)     = x || or xs
and             :: [Bool] -> Bool
and []          = True
and (x : xs)    = x && and xs
concat          :: [[a]] -> [a]
concat []       = []
concat (xs : xss)
                = xs ++ concat xss
reverse         :: [a] -> [a]
reverse []      = []
reverse (x : xs)= reverse xs ++ [x]
sumR            :: Num a => [a] -> a
sumR            = foldr (+)  0
productR        :: Num a => [a] -> a
productR        = foldr (*)  1
orR             :: [Bool] -> Bool
orR             = foldr (||) False
andR            :: [Bool] -> Bool
andR            = foldr (&&) True
concatR         :: [[a]] -> [a]
concatR         = foldr (++) []
foldr           :: (a -> b -> b) -> b -> [a] -> b
foldr op c []   = c
foldr op c (x : xs)
                = x `op` foldr op c xs
lengthR         :: [a] -> Integer
lengthR         = foldr (\ x n -> 1 + n) 0
reverseR        :: [a] -> [a]
reverseR        = foldr (\ x xs -> xs ++ [x]) []
mapR            :: (a -> b) -> [a] -> [b]
mapR f          = foldr (\ x xs -> f x : xs) []
filterR         :: (a -> Bool) -> [a] -> [a]
filterR p       = foldr (\ x xs -> if p x
                                   then x : xs
                                   else xs
                  ) []
suml            :: Num a => [a] -> a
suml            = sum' 0
    where
      sum' acc []       = acc
      sum' acc (x : xs) = sum' (acc + x) xs
reverse'        :: [a] -> [a]
reverse' xs     = rev [] xs
  where
    rev acc []       = acc
    rev acc (x : xs) = rev (x : acc) xs
foldl               :: (b -> a -> b) -> b -> [a] -> b
foldl op acc []     = acc
foldl op acc (x:xs) = foldl op (acc `op` x) xs
sumL            :: Num a => [a] -> a
sumL            = foldl (+)  0
productL        :: Num a => [a] -> a
productL        = foldl (*)  1
orL             :: [Bool] -> Bool
orL             = foldl (||) False
andL            :: [Bool] -> Bool
andL            = foldl (&&) True
concatL         :: [[a]] -> [a]
concatL         = foldl (++) []
lengthL         :: [b] -> Integer
lengthL         = foldl (\ r x -> r + 1) 0
reverseL        :: [a] -> [a]
reverseL        = foldl (\ r x -> x : r) []
-- ghci: :set +s
t1 = length (reverseR [1..10000])
t2 = length (reverseL [1..10000])
t3 = length (concatR (replicate 10000 "a"))
t4 = length (concatL (replicate 10000 "a"))
infixr 9 .
(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \ x -> f (g x)
id :: a -> a
id = \ x -> x
compose :: [a -> a] -> (a -> a)
compose = foldr (.) id
(>>>) :: (a -> b) -> (b -> c) -> (a -> c)
(>>>) = flip (.)
composeL :: [a -> a] -> (a -> a)
composeL = foldl (>>>) id
flip :: (a -> b -> c) -> (b -> a -> c)
flip op = \ y x -> x `op` y
fs :: [Integer -> Integer]
fs = [(+1), (*2), (`div` 3), (^2)]
r1 = compose  fs 5
r2 = composeL fs 5

Funktionen höherer Ordnung

Listenverarbeitung mit Funktionen höherer Ordnung

Funktionskomposition

Beispiele zum Kapitel

Die Quelle