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.

3 Responses to “Programming Praxis – Look And Say, Revisited”

1. Graham Says:

Just curious: what do you use to post/syntax highlight your haskell code? It doesn’t look like the sourcecode-tagged versions on the Praxis page.

2. Remco Niemeijer Says:

Since this a wordpress.com blog I can’t use any highlighting plugins, so I use a program called Highlight (http://www.andre-simon.de/doku/highlight/en/highlight.html) that outputs html. It’s not flawless, but it works well enough in most cases.

3. Graham Says:

Thanks! I’d seen Highlight before, but had forgotten how extensive it is.