We all know the Fibonacci sequence and how it is generated… 1, 1, 2, 3, 5, 8,… We just add the ‘previous’ pair to get the next number and then move along to the next pair. An interesting variation on this is to add adjacent pairs and write down their sum as before but, after appending the sum, also append the second digit of the pair just added and this gives… 1, 1, 2, 1, 3, 2, 3, 1 … Starting with 1, 1 1 + 1 -> 2 – append 2 and then copy forward 1 1 Read More

## Tag: trees

## The expressiveness of Haskell – Trees.

A simple recursive data declaration is enough to define a tree.

1 |
data Tree a = Empty | Node a (Tree a) (Tree a) |

This simply states that a Tree of ‘a’s is either Empty or (‘|’) it has a Node that has an ‘a’ and two other trees, a left subtree and a right subtree. The code to add an item to a tree is equally simple and recursive.

1 2 3 4 5 |
add :: (Ord a) => Tree a -> a -> Tree a add Empty x = Node x Empty Empty add (Node n left right) x | x <= n = Node n (add left x) right | otherwise = Node n left (add right x) |

The function signature

1 |
add :: (Ord a) => Tree a -> a -> Tree a |

states that ‘add’ takes a Tree of ‘a’, a value to add and returns a Tree of ‘a’. The only restriction on ‘a’ being that it must be of type ‘Ord’ meaning two ‘a’s can be compared Read More