All Together Now!

Finally, here’s a complete Haskell module that uses ifs, pattern matching, local defintions and recursion. The module is interested in the Collatz conjecture, a famous open problem in mathematics. It asks:

Does the Collatz sequence eventually reach 1 for all positive integer initial values?

The Collatz sequence is defined by taking any number as a starting value, and then repeatedly performing the following operation:

• if the number is even, divide it by two
• if the number is odd, triple it and add one

As an example, the Collatz sequence for 3 is: 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1 … As you can see, once the number reaches 1, it gets caught in a loop.

module Collatz where

-- one step of the Collatz sequence
step :: Integer -> Integer
step x = if even x then down else up
    where down = div x 2
        up = 3*x+1

-- collatz x computes how many steps it takes for the Collatz sequence
-- to reach 1 when starting from x
collatz :: Integer -> Integer
collatz 1 = 0
collatz x = 1 + collatz (step x)

-- longest finds the number with the longest Collatz sequence for initial values
-- between 0 and upperBound
longest :: Integer -> Integer
longest upperBound = longest' 0 0 upperBound

-- helper function for longest
longest' :: Integer -> Integer -> Integer -> Integer
-- end of recursion, return longest length found
longest' number _ 0 = number
-- recursion step: check if n has a longer Collatz sequence than the current known longest
longest' number maxlength n =
    if len > maxlength
    then longest' n len (n-1)
    else longest' number maxlength (n-1)
    where len = collatz n

(note that in the example above longest and longest' are different functions. longest' is a helper function of longest that receives more arguments. We will talk more about that later on..)

We can load the program in GHCi and play with it.

$ stack ghci
GHCi, version 9.2.8: https://www.haskell.org/ghc/  :? for help
Prelude> :load Collatz.hs
[1 of 1] Compiling Collatz          ( Collatz.hs, interpreted )
Ok, one module loaded.
*Collatz>

Let’s verify that our program computes the start of the Collatz sequence for 3 correctly.

*Collatz> step 3
10
*Collatz> step 10
5
*Collatz> step 5
16

How many steps does it take for 3 to reach 1?

*Collatz> collatz 3
7

What’s the longest Collatz sequence for a starting value under 10? What about 100?

*Collatz> longest 10
9
*Collatz> longest 100
97

The lengths of these Collatz sequences are:

*Collatz> collatz 9
19
*Collatz> collatz 97
118

With this information, we can finish the rest of the exercises:

Exercises:

All exercises for this chapter can be found in Set1.

Remember that you can test your functions by using

stack ghci Set1.hs

Then, you can run the test by using

stack runhaskell Set1Test.hs

You should be able to make the following exercises now:

You can check your current points from the blue blob in the bottom-right corner of the page.