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.