Funktionale Programmierung: Map, filter und List Comprehension

Map, filter und List Comprehension

map

Literatur LYAH: Maps and filters Verarbeitung aller Elemente einer Liste Anwenden einer Funktion auf jedes Element einer Liste   map square [1, 2, 3] = [1, 4, 9]   map (<2)   [1, 2, 3] = [True, False, False] Definition map            :: (a -> b) -> [a] -> [b]   map f []       =  [] map f (x : xs) =  f x : map f xs Beispiel sum sum          :: Num a => [a] -> a sum []       =  0 sum (x : xs) =  x + sum xs upto upto          :: Integral a => a -> a -> [a] upto m n   | m > n     = []   | otherwise = m : upto (m + 1) n   from          :: Integral a => a -> [a] from n        = n : from (n + 1) ? sum (map square (upto 1 100)) = ??? sum (map square (upto 1 100)) = 338350 Syntax für bessere Lesbarkeit   [m .. n]  = upto m n [m .. ]   = from m Gesetze map id      = id map (f . g) = map f . map g ? Wo sind diese Gesetze anwendbar? Compiler Optimierungen automatische Tests Datenstrukturen, die eine map-Funktion besitzen, die diese beiden Gesetzte erfüllt, heißen Funktor. ? Funktor für Maybe? mapMaybe :: (a -> b) -> (Maybe a -> Maybe b)   mapMaybe f Nothing  = Nothing mapMaybe f (Just x) = Just (f x) weitere Gesetze f . head         =  head . map f map f . tail     =  tail . map f map f . reverse  =  reverse . map f map f . concat   =  concat . map (map f)   map f (xs ++ ys) = map f xs ++ map f ys

filter

Selektion von Elementen einer Liste Anwenden eines Prädikates auf alle Elemente einer Liste   filter even [1, 2, 3, 4] = [2, 4]   (sum . filter even) [1..10] = 30   (sum . map square . filter even) [1..10] = 220 Definition filter            :: (a -> Bool) -> [a] -> [a]   filter p []       =  [] filter p (x : xs)   | p x           = x : filter xs   | otherwise     =     filter xs Eigenschaften filter p . filter q = filter (p `and` q)   and       :: (a -> Bool) ->              (a -> Bool) -> (a -> Bool) and p q x = p x && q x   filter p . concat = concat . map (filter p) filter definiert durch map und concat   filter p = concat . map box            where            box x = if p x then [x] else []

list comprehension

Literatur LYAH: I'm a list comprehension 2. Notation zum Arbeiten mit map und filter Beispiel .1   [ x * x | x <- [1..5]] =   map square [1..5] Beispiel .2   [ x * x | x <- [1..5], odd x] =   (map square . filter odd) [1..5] Definition Transformationsregeln Generator Regel [ e | x <- xs, Q ] = concat (map f xs)                      where                      f x = [e | Q] Wächter Regel [ e | p, Q ]       = if p                      then [e | Q]                      else [] ? Beweis: Beispiel .2 ?   [ x * x | x <- [1..5], odd x] = { Generator-Regel }   concat (map f [1..5]) where f x = [x * x | odd x] = { Wächter-Regel }   concat (map f [1..5]) where f x = if odd x then [x * x] else [] = { map auswerten }   concat [[1],[],[9],[],[25]] = { concat auswerten }   [1,9,25] Beispiele ge = [ (i, j) | i <- [1..5]               , j <- [1..5]               , i <= j      ] ? Ergebnis? ge = [(1,1),(1,2),(1,3),(1,4),(1,5)      ,(2,2),(2,3),(2,4),(2,5)      ,(3,3),(3,4),(3,5)      ,(4,4),(4,5)      ,(5,5)      ] Gesetze über list comprehension   [ f x | x <- xs ]     = map f xs [ x   | x <- xs, p x] = filter p xs ? Was ist besser: list comprehension oder map und filter? kein Unterschied im Laufzeitverhalten

Beispiel: List Comprehension

zip und zipWith

map erzeugt aus einstelligen Funktionen auf Element-Typen einstellige Funktionen auf Listen.   map :: (a -> b) -> ([a] -> [b]) ? Auch sinnvoll für 2-stellige und n-stellige Funktionen? erzeugt aus 2-stelligen Funktionen auf Element-Typen 2-stellige Funktionen auf Listen. zip verarbeitet 2 Listen zu einer neuen Resultat-Liste   zip :: [a] -> [b] -> [(a,b)]   zip  []     ys    = [] zip  xs     []    = [] zip (x:xs) (y:ys) = (x, y) : zip xs ys Beispiel Suchen aller Positionen, an denen ein bestimmter Wert steht:   positions       :: Eq a => a -> [a] -> [Int]   positions x xs  = [ i | (i, y) <- zip [0..] xs, x == y ] ? Punktfreie Version von positions? positions       :: Eq a => a -> [a] -> [Int]   positions x     = map fst                   .                   filter ( (==x) . snd )                   .                   zip [0..] Beispiel Suche der 1. Position, an der ein bestimmter Wert steht (oder -1):   position        :: Eq a => a -> [a] -> Int   position x xs   = head (positions x xs ++ [-1]) ? Punktfreie Version von position? position        :: Eq a => a -> [a] -> Int   position x      = head                   .                   (++ [-1])                   .                   positions x zipWith "anheben" (liften) von 2-stelligen Funktionen auf Listen   zipWith                :: (a -> b -> c) -> ([a] -> [b] -> [c]) zipWith f xs ys        =  map (uncurry f) (zip xs ys) ? Beispiele für sinnvolle Anwendungen? Vektorrechnung? addV                   :: Num a => [a] -> [a] -> [a] addV                   = zipWith (+)   scalarProd             :: Num a => [a] -> [a] -> a scalarProd xs ys       = sum (zipWith (*) xs ys)   -- oder scalaProd xs           = sum . zipWith (*) xs zipWith besser: Direkte Variante   zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]   zipWith f  []     ys          = [] zipWith f  xs     []          = [] zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys ? zip mit zipWith implementieren? zip = zipWith mkPair     where     mkPair x y = (x, y)   -- kürzer   zip = zipWith (,) unzip inverse Operation zu zip   unzip  :: [(a,b)] -> ([a], [b])   unzip  =  pair (map fst, map snd)   uncurry zip . unzip = id ? Herleitung der Definition von unzip?   unzip xys = { Definition von unzip }   (map fst xys, map snd xys) = { Definition von pair: pair (f,g) x = (f x, g x) }   pair (map fst, map snd) xys     unzip = { Extensionalitätsprinzip }   pair (map fst, map snd)

Letzte Änderung: 20.09.2016

© Prof. Dr. Uwe Schmidt