Programming Praxis – Hofstadter’s Sequence

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
About these ads

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: