Vorlesung: Praxis der Funktionalen Programmierung


Zweimal ist einmal

Wir betrachten eine überraschende Anwendung des fmap auf binären Bäumen. (Hat eigentlich nicht viel mit fmap zu tun, sondern viel mehr mit lazy evaluation. Egal, trotzdem lustig.)

Wir lösen die Aufgabe: gegeben ist ein t :: Tree a, gesucht ist ein Baum s gleicher Form wie t, der in jedem Knoten das Maximum aller Schlüsselwerte von t enthält (also überall die gleiche Zahl).

Das ist überhaupt nicht schwer:

import Tree
import TFold
import TMap
import Anamorph

tmax :: Ord a => Tree a -> Maybe a
-- ergibt Nothing, wenn der Baum leer ist,
-- sonst Just maximum
tmax = tfold ( \ l k r -> max (max l r) (Just k) ) Nothing

alles_max :: Ord a => Tree a -> Tree a
alles_max Leaf = Leaf
alles_max t =
    let Just m = tmax t
    in	fmap (const m) t

    

Der Witz ist aber, daß es auch eine Lösung gibt, die den Baum nur einmal durchläuft. Dieses Programm wurde von Richard Bird gefunden. Wichtiger Mann für die Funktionale Programmierung.
import Tree
import TFold
import TMap
import Anamorph

ersetzen_und_max :: Ord a => a -> Tree a -> (Tree a, Maybe a)
-- alle Knoten durch m ersetzen
-- außerdem Maximum der Knoten ausgeben
ersetzen_und_max m =
    tfold ( \ (l, lm) k (r, rm) 
	      -> ( Node { left = l, key = m, right = r }
		 , max (max lm rm) (Just k)
		 )
	  ) ( Leaf, Nothing )

alles_max :: Ord a => Tree a -> Tree a
alles_max Leaf = Leaf
alles_max t =
    let (s, Just m) = ersetzen_und_max m t
    in	s

    


best viewed with any browser


http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de