99 questions/Solutions/54A
< 99 questions | Solutions
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
(*) Check whether a given term represents a binary tree
In Haskell, we characterize binary trees with a datatype definition:
data Tree a = Empty | Branch a (Tree a) (Tree a)
deriving (Show, Eq)
The above tree is represented as:
tree1 = Branch 'a' (Branch 'b' (Branch 'd' Empty Empty)
(Branch 'e' Empty Empty))
(Branch 'c' Empty
(Branch 'f' (Branch 'g' Empty Empty)
Empty)))
Other examples of binary trees:
tree2 = Branch 'a' Empty Empty -- a binary tree consisting of a root node only
tree3 = nil -- an empty binary tree
tree4 = Branch 1 (Branch 2 Empty (Branch 4 Empty Empty))
(Branch 2 Empty Empty)
The type system ensures that all terms of type Tree a
are binary trees: it is just not possible to construct an invalid tree
with this type. Hence, it is redundant to introduce a predicate to
check this property: it would always return True
.