# Difference between revisions of "99 questions/Solutions/54A"

From HaskellWiki

< 99 questions | Solutions

(categorize) |
|||

Line 33: | Line 33: | ||

with this type. Hence, it is redundant to introduce a predicate to |
with this type. Hence, it is redundant to introduce a predicate to |
||

check this property: it would always return <hask>True</hask>. |
check this property: it would always return <hask>True</hask>. |
||

+ | |||

+ | |||

+ | [[Category:Programming exercise spoilers]] |

## Latest revision as of 13:35, 25 December 2016

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

.