Walking the Tree.

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 use the larger tree then you’ll need to mentally rotate the tree – or modify the code 🙂 )

Using code already written and adding a bit more we can write a bit of Haskell to create a path generator.

First some types

In other words a SternPath is just a list of L and R.

To generate the path for a given fraction we first generate a Stern-Brocot tree (lazily as we don’t know how deep to go, see earlier post for buildBrocTreeLazy) and then build up the path by doing what is really a search on a binary tree. Like this:

We create a tree and fmap fraction over it – this gives us a Tree Fraction. (see previous posts for details of Tree). Next, we make sure the supplied Fraction is in its simplest form and then we recursively append R or L to the result and quit when we find the Fraction. We know that the function will terminate as the Stern-Brocot contains all positive rational numbers… Very neat and pleasing.

Reducing a path is also quite simple – here’s a version that returns a list of fractions – each corresponding to the term in the path.

Some examples in GHCI:

which is what you’d expect.

A really interesting path to evaluate is alternating L then R i.e.

and we see that the numerators (or denominators) are the Fibonacci numbers! (Which ties in quite nicely with the earlier posts about continued fractions ).

It is also fascinating that we can express the SternPath as the multiplication of 2×2 matrices! This is discussed in detail in Concrete Mathematics by Graham et al which is a gem of a book and gives a more detailed treatment of the stern path expressed as matrix manipulation. What follows next is just an overview of what’s discussed in Concrete Mathematics.

Stern Matrices

In Haskell we can defines a data type Matrix and define a ‘left‘, ‘right‘ and identity matrix and make a Monoid instance for it like this

And any Matrix – M a b c d – represents the fraction (c + d)/(a + b) and, even more ‘amazingly’, the immediate ancestor fractions are given by c/a and d/b.

We can reduce a Matrix to a Fraction like this:

and map a SternTerm to a Matrix with this simple function

With these functions we can reduce a path to a fraction like this:

where we fold over the list making use of the Monoidal nature of Matrix. So, for example,

Whilst reduceSternPath is OK, a neater implementation is

where we use the ‘free’ (Monoid) implementation of mconcat to reduce a list of Matrix that’s created by fmapping over the SternPath. It’s little things like this that make Haskell such a joy to use and shows that you don’t always have to swim in the deep end to have fun with the language!

All the code is in Github and thanks for reading!

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

ˆ Back To Top