A Collatz sequence in Haskell

WordPress.com does not always render Markadown properly, so a copy of this post resides here.


I am coninuing my adventure in Haskell. In order to make it a bit more fun, I decided to code a simple yet very intriguing problem, I first heard of when I read AI Memo 239: The Collatz conjecture.

Item 133
Item 133. The Collatz conjecture in AIM 239

Construct a sequence of integers where given an arbitrary interger the value of the next is:
* If the number is even, divide it by two.
* If the number is odd, triple it and add one.

This can easily be coded in Haskell as follows:

collatz :: Int -> Int
collatz 1 = 1
collatz n =
  if (even n)
    then (n `div` 2)
    else (3 * n + 1)

But how can one obtain a sequence of numbers from this? A very clever solution is here where the author implements a variation of takeWhile which includes also the first list item that fails the test the first time. So my question became, can it be done in another way? Yes it can:

collatzSequence :: Int -> [Int]
collatzSequence n =
  if n == 1
    then [1]
    else [n] ++ collatzSequence (collatz n)

Let's see some test runs:

*Main> collatzSequence 5
[5,16,8,4,2,1]
*Main> collatzSequence 50
[50,25,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
*Main> collatzSequence 500
[500,250,125,376,188,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
*Main> collatzSequence 512
[512,256,128,64,32,16,8,4,2,1]
*Main> collatzSequence 513
[513,1540,770,385,1156,578,289,868,434,217,652,326,163,490,245,736,368,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
*Main>

You may have observed we only run it on positive integers. When we run it with negative integers, there are a few more cycles that we need to take into account. Here is the updated sequence function, written with guards:

collatzSequence :: Int -> [Int]
collatzSequence n
  | n == 1 = [1]
  | n == (-2) = [(-2)]
  | n == (-5) = [(-5)]
  | n == (-17) = [(-17)]
  | otherwise = [n] ++ collatzSequence (collatz n)

Test:

*Main> collatzSequence (-50)
[-50,-25,-74,-37,-110,-55,-164,-82,-41,-122,-61,-182,-91,-272,-136,-68,-34,-17]

Now if there was also a way to prove the conjecture…

Please note that in Haskell the unary minus is a function and not an operator, hence, you need to parenthesize. This also works:

*Main> collatzSequence $ -50
[-50,-25,-74,-37,-110,-55,-164,-82,-41,-122,-61,-182,-91,-272,-136,-68,-34,-17]

Update: A friend posted me his own elegant version of the Collatz sequence:

collatz :: Int -> [Int]
collatz 1 = [1]
collatz n
    | even n =  n : collatz (n `div` 2)
    | odd n  =  n : collatz (n * 3 + 1)

main = do
  putStrLn $ show $ collatz 1
  putStrLn $ show $ collatz 6
  putStrLn $ show $ collatz 23
Advertisements

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s