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
Tags: bonsai, code, Haskell, hofstadter, kata, praxis, programming, sequence
