Vorlesung: Praxis der Funktionalen Programmierung


Geradeaus-Rechnungen

Wir betrachte die Aufgabe, jeden Knoten eines binären Baumes mit seiner Inorder-Nummer zu versehen. Das können wir nicht so einfach als tmap oder tfold schreiben, da wir das Ergebnis der Rechung links (die Anzahl der Knoten) auf der rechten Seite benötigen. Bei tfold-Funktionen sind jedoch die Rechungen links und rechts unabhängig.

Wir wollen diesmal wirklich sequentiell durch den Baum durch. Wir schreiben eine Funktion, die als Eingabe eine Zahl n :: Int sowie einen Baum t :: Tree a bekommt, und als Ergebnis ein Paar (m :: Int, s :: Tree Int) ausgibt, so daß s der mit [ n .. m - 1 ] numerierte Baum t ist.

import Tree
import Anamorph

inorder :: Tree a -> Tree Int
inorder t = let (m, s) = helper 1 t in s

helper :: Int -> Tree a -> (Int, Tree Int)
helper n Leaf = (n, Leaf)
helper n (Node { left = l, right = r }) =
    let (nl, hl) = helper n l
	(nr, hr) = helper (nl + 1) r
    in	(nr, Node { left = hl, key = nl, right = hr })

Das geht, sieht aber nicht schön aus: wir müssen von Hand drauf aufpassen, daß wir den Zustand des Zählers richtig von einem in den anderen Zweig transportieren. Wir werden das in kürze viel eleganter aufschreiben.

best viewed with any browser


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