Posts Tagged ‘hofstadter’

Programming Praxis – Hofstadter’s Sequence

February 1, 2013

In today’s Programming Praxis exercise, our goal is to write a program that generates the Hofstadter sequence. Let’s get started, shall we?

A quick import:

import Data.List

The exercise provides a 2-line Haskell solution in addition to the usual Scheme one. This solution, however, is needlessly complicated, including both a worker function and explicit recursion. We can eliminate both using the unfoldr function, which takes an initial state and a function that produces an output element and a new state. The state we need to keep track of is the S sequence and the next number of R that will be generated. Since R is of the same type as S, we combine the two into a single list in which the first element is the upcoming element in R and the rest is S. Whenever we calculate the next element of R, we remove it from S. This way, we can do the whole thing in a single line.

hofstadter :: [Integer]
hofstadter = unfoldr (\(r:s:ss) -> Just (r, r+s:delete (r+s) ss)) [1..]

Since the sequence is infinite, you can take as many elements as you want.

main :: IO ()
main = print $ take 25 hofstadter