Higher order functions (HOFs) für Listen

Ein gut sortierter Werkzeugkasten voll HOFs erlaubt, typische Aufgaben ohne explizite Programmierung des Listendurchlaufs (Rekursion, pattern matching) zu lösen.

Natürlich ist alles polymorph um universelle Anwendung zu ermöglichen!

• map wendet eine Funktion an auf jedes Listenelement:

   map:: (a->b)->[a]->[b]
  
  map f [] = []
  
  map f (x:xs) = f x : map f xs
  
  
  
  
  
  
  > map even [1..10]
  
  [False,True,False,True,False,True,False,True,False,True]
  
  
  

• fold-Funktionen fassen Listenelemente zusammen, indem sie eine geeignete Operation "`dazwischen setzen"'; es gibt mehrere Arten:

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

  also:

  foldr op start [x₁...x_n] = x₁ `op` (x₂ `op` (...(x_n `op` start)...)

  foldl op start [x₁...x_n] = (...(start `op` x₁) `op` x₂)...) `op` x_n

   > foldr (+) 0 [1..10]
  
  55
  
  > foldl (+) 0 [1..10]
  
  55
  
                          - jetzt Unterschied!
  
  
  
  
  
  
  > foldr (-) 0 [1..10]
  
  -5                      - 1-(2-(...10-0)...)
  
  > foldl (-) 0 [1..10]
  
  -55                     - (...(0-1)-2)...)-10
  
  
  

  Will man nur die Elemente der Liste zusammenfassen, so benötigt man für foldr und foldl ein neutrales Element der anzuwendenden Operation als Startwert (Basiswert):

   sum:: [Int]->Int
  
  sum = foldr (+) =
  
  
  

  es geht auch ohne:

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

  also: foldr op start [x₁...x_n] = x₁ `op` (x₂ `op` (...(x_n-1 `op` x_n)...)

  Liste darf nicht leer sein!

  analog: foldl1

   > foldl1 max [1..10]
  
  10      - 0 nicht neutrales Element für max, da Liste auch negative
  
          - Werte enthalten könnte.
  
  
  

• filter, takeWhile, dropWhile

  liefern einen Teil der Liste

   filter:: (a->Bool)->[a]->[a]
  
  filter p []      = []
  
  filter p (x:xs)
  
     |p x          = x: filter p xs
  
     |otherwise    = filter p xs
  
  
  
  
  
  
  > filter even [1..11]
  
  [2,4,6,8,10]
  
  
  
  
  
  
  takeWhile:: (a->Bool)->[a]->[a]
  
  takeWhile p []   = []
  
  takeWhile p (x:xs)
  
     |p x          = x:takeWhile p xs
  
     |otherwise    = []         - also Anfangsstück, solange p gilt
  
  
  
  
  
  
  dropWhile:: (a->Bool)->[a]->[a]
  
  dropWhile p []   = []
  
  dropWhile p (x:xs)
  
     |p x          = dropWhile p xs
  
     |otherwise    = x:xs
  
  
  

• mehr in Prelude

  (einige Definitionen dort aus Gründen der Systematik anders als bei uns, aber äquivalent)

• mit solchen HOFs leicht, komplexere Listenverarbeitungsbeispiele ökonomisch zu formulieren:

  z.B.:

   > ((foldl (+) 0).(map (^2)).(filter (>0)) [-10..10]
  
  385
  
  
  

  also Stufenverarbeitung:

   [-10..10]
  
       >----|
  
  v
  
  filter (>0)
  
               |
  
               |           [1..10]
  
  v
  
  map (^2)
  
               |
  
               |           [1,4,9,16,25,36,49,64,81,100]
  
  v
  
  foldl (+) 0
  
               |
  
               >-> 385