99 questions/Solutions/54A

From HaskellWiki
< 99 questions‎ | Solutions
Revision as of 21:41, 13 July 2010 by Wapcaplet (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

(*) 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)

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.