The earlier post *Fractions to Phi to Fibonacci!* showed a simple structure for Continued Fractions (CF) and used a CF representation of the Golden Ratio to derive the terms of the Fibonacci Sequence. It also alluded to a particular notation to express a CF and here we will describe that notation, create a parser for it and calculate the square roots of some integers from their specific CFs and finally derive a general CF that can be used to find the square root of any integer.

## CF List Notation

Essentially the CF is written as a list of ints like this [a0; a1, a2, a3…]. The first entry is followed by a ‘;’ and others by a ‘,’. The terms a1, a2, a3… taken together, are the ‘repeating’ terms and it is necessary to only write one ‘cycle’ of the repeating terms. For example root 2 as a CF is

and as a list this would be [1;2]

or

would be [1;1].

As for square roots of integers, here’s a list in CF list form. Again, for more details, please see

http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html#section6.3

√1 [ 1; ]

√2 [ 1; 2 ]

√3 [ 1; 1, 2 ]

√4 [ 2; ]

√5 [ 2; 4 ]

√6 [ 2; 2, 4 ]

√7 [ 2; 1, 1, 1, 4 ]

√8 [ 2; 1, 4 ]

√9 [ 3; ]

√10 [ 3; 6 ]

## Haskell Abstraction

We can represent this list notation as a first *Digit* and then a list of the repeated *Digit* like this

1 2 3 4 5 6 7 8 |
-- -- type Digit = Integer type First = Digit type Repeat = [Digit] -- [a1;a2,a3,a4...] => first = a1, repeat = [a2,a3,a4] data FracStruc = FracStruc { first :: First, repeat :: Repeat} deriving (Show) |

really just some type synonyms and a *FracStruc* using record syntax.

Writing functions that will parse a string into a *FracStruc* is fairly straightforward I really quite enjoy this sort of thing with Haskell. So, using *Megaparsec* a few functions to do this are

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
-- -- -- right and left bird :). Put the parser in the middle dropSpaces :: Parser a -> Parser a dropSpaces p = space *> p <* space -- A number followed by a separator char - for Fractions this will be ; or , digitSep :: Char -> Parser Digit digitSep = dropSpaces . digitSep1 where digitSep1 :: Char -> Parser Digit digitSep1 ch = do d <- some digitChar space many . char $ ch return (read d) -- Parse out the a1 in [a1;a2,a3...] firstP :: Parser Digit firstP = dropSpaces . digitSep $ ';' -- Parse out the a2, a3... in [a1;a2, a3...] repeatP :: Parser Repeat repeatP = many . digitSep $ ',' -- Parse a FracStruc from "[a1;a2, a3...]" fracStrucP :: Parser FracStruc fracStrucP = char '[' *> (firstP >>= \firstDig -> repeatP >>= \rep -> return $ FracStruc firstDig rep) <* char ']' |

I think most of this is fairly clear. The *dropSpace* uses the Applicative sequence actions where *> ignores the value of the first argument and <* ignores the value of the second argument, so dropping spaces ‘before and after’. The *fracStrucP* parser pull this together and we can test run it in GHCI like this:

1 2 3 4 |
-- -- λ-> runParser fracStrucP "" "[1;2]" Right (FracStruc {first = 1, repeat = [2]}) |

and we see that the number 1 goes into first and the repeat part is a list with just 2 in it. A larger one:

1 2 3 4 |
-- -- λ-> runParser fracStrucP "" "[1;1,2,3,4,5]" Right (FracStruc {first = 1, repeat = [1,2,3,4,5]}) |

and overall the parser is fairly forgiving of spurious spaces:

1 2 3 4 |
-- -- λ-> runParser fracStrucP "" "[ 1 ; 1 , 2, 3,4,5 ]" Right (FracStruc {first = 1, repeat = [1,2,3,4,5]}) |

*FracStruc* has enough information to supply the values of the ‘a’s in a CF and we’re taking the ‘b’s to be fixed at 1. A function that takes a *FracStruc* and returns a function of Integer to Fraction is:

1 2 3 4 5 6 7 8 |
-- -- -- The fa function in contFrac fa fb is fully defined by the values in a FracStruc genFa :: FracStruc -> (Integer -> Fraction) genFa (FracStruc fs rep) = \n -> if n == 0 then Numbr fs else Numbr (g n) where g n = rep !! ix where ix = rem (fromIntegral (n - 1)) (length rep) |

The returned function is specified by the lambda expression \*n -> …* such that if *n* is 0 then the value of *first* is returned. Otherwise the *repeat* list is indexed into in a circular fashion based on *n* and the length of the *repeat* list. We can now define this function:

1 2 3 4 5 6 7 8 9 |
-- -- Create a fraction to the supplied depth using the given FracStruc -- fb assumed fixed at 1 frac :: Integer -> FracStruc -> Fraction frac depth struc@(FracStruc fs rep) | null rep = Numbr fs | otherwise = contFrac fa fb depth where fa = genFa struc fb = const 1 |

The function *frac* takes a depth and a *FracStruc* and returns a *Fraction*. The ‘a’s are generated by *genFa* *struc* and the ‘b’s are fixed at 1. If there’s no repeating structure then the *first* from *FracStruc* is returned otherwise the *contFrac* (from the previous post) is called. We are now able to write a couple of functions to create a *Fraction* from a list:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
-- -- -- From the supplied list and the given depth perhaps create a Fraction fracFromList :: Integer -> String -> Maybe Fraction fracFromList depth s = case makeStruct s of Nothing -> Nothing Just struc -> Just $ frac depth struc -- Runs fracStrucP to maybe make a FracStruc makeStruct :: String -> Maybe FracStruc makeStruct txt = case runParser fracStrucP "" txt of Right s -> Just s _ -> Nothing |

And now we are able to write expression like these

1 2 3 4 5 6 7 |
-- -- λ-> fracFromList 25 "[1;1]" (phi) Just 121393/75025 *FractionParser λ-> fracFromList 25 "[1;2]" (root 2) Just 1855077841/1311738121 |

As can be seen the result is in the *Maybe* monad and we can do this sort of thing
evalFrac <$> (fracFromList 25 "[1;2]") to give
Just 1.4142137

or we can write

1 2 3 4 |
-- -- evalFracM :: Integer -> String -> Maybe Float evalFracM depth s = fracFromList depth s >>= Just . evalFrac |

so tying things back to the CF for root 2 and running in GHCI

1 2 3 4 5 6 7 |
-- -- λ-> z = [evalFracM n "[1;2]" | n <- [0..15]] *FractionParser λ-> z [Just Infinity,Just 1.0,Just 1.5,Just 1.4,Just 1.4166666,Just 1.4137931,Just 1.4142857,Just 1.4142011,Just 1.4142157,Just 1.4142132, Just 1.4142137,Just 1.4142135,Just 1.4142135,Just 1.4142135,Just 1.4142135,Just 1.4142135] |

we see the results in a monadic context. Or, if we wanted it in *Maybe* fraction form

1 2 3 4 5 6 7 |
-- -- λ-> z = [fracFromList n "[1;2]" | n <- [0..15]] *FractionParser λ-> z [Just 1/0,Just 1/1,Just 3/2,Just 7/5,Just 17/12,Just 41/29,Just 99/70,Just 239/169,Just 577/408,Just 1393/985,Just 3363/2378, Just 8119/5741,Just 19601/13860,Just 47321/33461,Just 114243/80782,Just 275807/195025] |

And, just for phun – here’s the same phing for phis with the *denom* function fmapped over them.

1 2 3 4 5 6 |
-- -- λ-> phis = [fracFromList n "[1;1]" | n <- [0..15]] *FractionParser λ-> fmap (fmap denom ) phis [Just 0,Just 1,Just 1,Just 2,Just 3,Just 5,Just 8,Just 13,Just 21,Just 34,Just 55,Just 89,Just 144,Just 233,Just 377,Just 610] |

Here is the list of the roots of 1..10 in CF list format

√1 [ 1; ]

√2 [ 1; 2 ]

√3 [ 1; 1, 2 ]

√4 [ 2; ]

√5 [ 2; 4 ]

√6 [ 2; 2, 4 ]

√7 [ 2; 1, 1, 1, 4 ]

√8 [ 2; 1, 4 ]

√9 [ 3; ]

√10 [ 3; 6 ]

and ignoring the √x chars we have a list like this [“[1;]”, “[1;2]”, “[1;1,2]”, “[2;]”, “[2;4]”, “[2;2,4]”, “[2;1,1,1,4]”, “[2;1,4]”, “[3;]”, “[3;6]”] and we can map *evalFracM* over it, to a depth of say 15, to give the square roots of 1..10 🙂

1 2 3 4 |
-- -- λ-> fmap (evalFracM 15) ["[1;]","[1;2]","[1;1,2]","[2;]","[2;4]","[2;2,4]","[2;1,1,1,4]","[2;1,4]","[3;]","[3;6]"] [Just 1.0,Just 1.4142135,Just 1.7320508,Just 2.0,Just 2.236068,Just 2.4494898,Just 2.6457512,Just 2.828427,Just 3.0,Just 3.1622777] |

## And finally

…it can be shown that

can be written as

clearly the CF list for this will be [1;2] and the function to generate the ‘b’s will simply be (x – 1). So a couple of simple function for this…

1 2 3 4 5 6 7 8 9 10 11 |
-- -- -- A function for the 'a's for a 'fixed' FracStruc 1 [2] fa12 :: Integer -> Fraction fa12 = genFa (FracStruc 1 [2]) -- The number and the depth root :: Integer -> Integer -> Fraction root n = contFrac fa fb where fa = fa12 fb _ = n - 1 |

Here we use a ‘fixed’ *FracStruc 1 [2] *to create the ‘a’s. In the function *root* the function for the ‘b’s is a simple (n – 1). We can generate the roots of 1..10 by

*fmap evalFrac [root n 10 | n <- [1..10]] *which gives

## [1.0,1.4142137,1.7320755,2.0000677,2.2340426,2.4503307,2.6476114,2.8319218,3.005865,3.1713445]

and is a lot simpler than the techniques discussed in the ‘Root of the Problem’ part 1 and part 2.

All the code is on Github.

Thanks for reading…!