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

1 2 3 |
-- data SternTerm = L | R deriving (Eq, Show) type SternPath = [SternTerm] |

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:

1 2 3 4 5 6 7 8 |
-- sternPath :: Fraction -> SternPath sternPath frac = go (fraction <$> buildBrocTreeLazy) fr [] where fr = reduce frac go (BNode (F p q) l r) (F n d) path | p == n && q == d = path | F p q < F n d = go r fr (R : path) | otherwise = go l fr (L : path) |

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.

1 2 3 4 5 6 |
-- fractionPath :: SternPath -> [Fraction] fractionPath = go ( fraction <$> buildBrocTreeLazy) where go (BNode frac _ _) [] = [frac] go (BNode frac l r) (p:ps) = frac : go (pick p l r) ps where pick p l r = if p == L then l else r |

Some examples in GHCI:

1 2 3 4 5 6 |
-- λ-> fractionPath [L,L,L,L,L,L,L,L] [1/1,1/2,1/3,1/4,1/5,1/6,1/7,1/8,1/9] *Matrix λ-> fractionPath [R,R,R,R,R,R,R,R] [1/1,2/1,3/1,4/1,5/1,6/1,7/1,8/1,9/1] |

which is what you’d expect.

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

1 2 3 4 5 6 7 |
λ-> p = [L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R,L,R] *Matrix λ-> fractionPath p [1/1,1/2,2/3,3/5,5/8,8/13,13/21,21/34,34/55,55/89,89/144,144/233,233/377, 377/610,610/987,987/1597,1597/2584,2584/4181,4181/6765,6765/10946, 10946/17711,17711/28657,28657/46368,46368/75025,75025/121393,121393/196418, 196418/317811,317811/514229,514229/832040] |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
-- data Matrix = M Integer Integer Integer Integer deriving Show instance Monoid Matrix where mempty = ident -- Identity 2x2 matrix -- matrix multiplication mappend (M a b c d) (M w x y z) = M (a*w + b*y) (a*x + b*z) (c*w + d*y) (c*x + d*z) left :: Matrix left = M 1 1 0 1 right :: Matrix right = M 1 0 1 1 ident :: Matrix ident = M 1 0 0 1 |

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:

1 2 3 |
-- reduceMatrix :: Matrix -> Fraction reduceMatrix (M a b c d) = F (c + d) (a + b) |

and map a *SternTerm* to a *Matrix* with this simple function

1 2 3 |
-- sternTermMatrix :: SternTerm -> Matrix sternTermMatrix t = if t == L then left else right |

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

1 2 3 |
-- reduceSternPath :: SternPath -> Fraction reduceSternPath = reduceMatrix . foldl (\ acc t -> sternTermMatrix t <> acc ) ident |

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

1 2 3 4 5 |
-- λ-> reduceSternPath [L,L,L,L,L,L,L,L] 1/9 λ-> reduceSternPath [R,R,R,R,R,R,R,R] 9/1 |

Whilst *reduceSternPath *is OK, a neater implementation is

1 2 3 |
-- reduceSternPath' :: SternPath -> Fraction reduceSternPath' = reduceMatrix . mconcat . fmap sternTermMatrix |

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!