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.