Posts Tagged ‘sequence’

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

Programming Praxis – Look And Say

March 15, 2011

In today’s Programming Praxis exercise, our task is to generate the Look and Say sequence (1, 11, 21, 1211, etc.). Let’s get started, shall we?

A quick import:

import Data.List

The algorithm is pretty straightforward: convert the number to a string, replace each sequence of identical digits with the length followed by the digit and convert the result back to an integer. Repeat indefinitely.

lookAndSay :: Integer -> [Integer]
lookAndSay = iterate (read . f . group . show) where
    f = (>>= \x -> show (length x) ++ take 1 x)

A test to see if everything is working properly:

main :: IO ()
main = print $ take 10 (lookAndSay 1) == [1, 11, 21, 1211, 111221,
    312211, 13112221, 1113213211, 31131211131221, 13211311123113112211]

Yup. Unfortunately there doesn’t appear to be a Haskell Package that does run-length encoding, or I might have been able to do it in one line.