= Solution
Use <pattern matching> on the two <data constructors>, concatenating the left <subtree>'s <inorder traversal>, the root label, and the right <subtree>'s <inorder traversal>:
``
data Tree = Leaf | Fork Tree Int Tree
inorder :: Tree -> [Int]
inorder Leaf = []
inorder (Fork l x r) = inorder l ++ [x] ++ inorder r
``
Here `Leaf` represents the empty <binary tree>, rather than a labelled leaf. The printed declaration uses `type`; an executable <Haskell> <algebraic data type> requires `data`, as above. By <structural induction>, the two equations return precisely the prescribed <inorder traversal>:
$$
\boxed{\operatorname{inorder}(\operatorname{Fork}(l,x,r))=\operatorname{inorder}(l)\mathbin{++}[x]\mathbin{++}\operatorname{inorder}(r).}
$$
Back to article page
