Vorlesung: Praxis der Funktionalen Programmierung

Strukturierte Funktionale Programmierung

Das Ziel der map/fold-Benutzung ist, daß im Programm keine rekursiven Definition mehr stehen. Sondern: wenn man eine Rekursion benötigt, dann stelle sie durch eines der bekannten Rekursionsschemata dar.

Vergleiche das mit dem Unterschied zwischen GOTO- und strukturierter Programmierung: natürlich könnte man alles mit wilden Sprüngen machen, aber es hat sich gezeigt, daß strukturierte Sprünge (Schleifen) viel übersichtlicher sind. Das gleiche passiert in funktionalen Sprachen: natürlich kann man alles beliebig rekursiv aufrufen lassen, aber es ist softwaretechnisch viel günstiger, nur festgelegte Schemata zu verwenden.

Das hat neben der Lesbarkeit auch den Vorteil der Implementiernbarkeit: fortgeschrittene Compiler können map/fold-Zusammensetzungen kräftig umformen, bevor sie wirklich Code erzeugen. Vergleiche wieder mit GOTO/strukturiert: der Compiler kann er Schleifen viel freier umordnen oder ausrollen, aber nicht, wenn er befürchten muß, daß jemand wild mitten hinein oder herausspringt.

Rechenregeln für map und foldr

Zeige

foldr g x0 . map f = foldr ( \ x y -> g (f x) y ) ( f x0 )

length . map f 

Rechenregeln für fold

Erstens

foldr (:) id =

h . foldr f b = foldr g (h b)

foldr f b . g (:) [] = g f b

Anwendung

Der Baum wird erst erzeugt und dann sofort wieder zerlegt. Vornehm gesagt ist build ein Anamorphismus :: b -> Tree a und flatten ein Katamorphismus Tree a -> c (heißt bei uns tfold) und die Komposition von beiden :: b -> c braucht keinen Baum (Quelltext).

Jetzt werden auch einige Folklore-Namen klar: weil wir keine Bäume brauchen, wird das Programm also ent-waldet: Deforestation. Wodurch passiert das oft in der Natur? Sauren Regen, daher der Name Acid-Rain-Theorem:

wenn   h :: b -> Maybe (b, a, b)
und    f :: b -> a -> b -> b;  z :: b

dann   tfold f z . anamorph h = g
   where  
       g x = case h x of
                   Nothing -> z
		   Just (l, k, r) -> f (g l) k (g r)