Programming Praxis - Look And Say, Revisited

In today’s Programming Praxis exercise, our goal is to calculate Conway’s constant. Let’s get started, shall we?

First we need to represent the polynomial that we’re going to take the root of.

conway :: Num a => a -> a
conway x = sum $ zipWith (*) (iterate (* x) 1)
    [ -6,  3,-6, 12,-4, 7,-7, 1, 0, 5,-2, -4,-12, 2, 7,12,-7,-10
    , -4,  3, 9, -7, 0,-8,14,-3, 9, 2,-3,-10, -2,-6, 1,10,-3,  1
    ,  7, -7, 7,-12,-5, 8, 6,10,-8,-8,-7, -3,  9, 1, 6, 6,-2, -3
    ,-10, -2, 3,  5, 2,-1,-1,-1,-1,-1, 1,  2,  2,-1,-2,-1, 0,  1]

Next, we calculate the root by halving the interval until the value at the middle is sufficiently close to 0.

root :: (Fractional a, Ord a) => (a -> a) -> a -> a -> a -> a
root f lo hi e | abs (f mid) < e = mid
               | f mid > 0       = root f lo mid e
               | otherwise       = root f mid hi e
               where mid = (lo + hi) / 2

Since we know the root lies somewhere between 1 and 2, we use those as the starting values.

main :: IO ()
main = print $ root conway 1 2 1e-7 == 1.303577269034296

We get the correct answer, so everything seems to be working properly.

About these ads

Tags: bonsai, code, constant, conway, Haskell, kata, look and say, praxis, programming