It’s just fun playing around with Stern-Brocot trees and a bit of Haskell…! For any fraction on the Stern-Brocot tree there is just one path to it from the root. That path can written as a sequence of left or right ‘turns’ at each node depending on whether the target node is smaller or larger than the current node. This leads to the Stern Path For example in this small tree the path to, say, 4/5 is, from 1/1, LRRR. The fraction 5/2 has path RRL. To get to 5/8 we go LRLR… and so on. (If you want to Read More

## Tag: trees

## A Stern View.

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

## 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