Visit the collatz-conjecture exercise on Exercism to read the full instructions and download the exercise files.
Dig Deeper
Generate a list of steps
Generate a list of steps
-- Using `iterate`
collatz :: Integer -> Maybe Integer
collatz n
| n > 0 = Just (countSteps n)
| otherwise = Nothing
where
countSteps = toInteger . length . takeWhile (/= 1) . iterate nextStep
nextStep k = if even k then k `div` 2 else 3 * k + 1
-- Using `unfold`
collatz :: Integer -> Maybe Integer
collatz n
| n > 0 = Just (countSteps n)
| otherwise = Nothing
where
countSteps = toInteger . length . unfoldr nextStep
nextStep 1 = Nothing
nextStep k = Just (k, if even k then k `div` 2 else 3 * k + 1)
This approach neatly disentangles all four concerns of
- computing the next Collatz step,
- computing the sequence of all Collatz steps,
- truncating this sequence at the first
1, and
- counting the number of steps,
using only functions from the standard library for all of these except one.
iterate and unfoldr
When you have a ‘seed’ element and a way of computing every next element from it, you can use iterate or unfoldr to produce the entire sequence.
iterate (documentation) uses the given function to iteratively compute the next element from the previous one:
powersOfTwo = iterate (2 *) 1
-- >>> take 5 powersOfTwo
-- [1,2,4,8,16]
The list produced by iterate is always infinite, so you might need to truncate it yourself.
unfoldr (documentation) is more general than iterate:
- In addition to determining what the next element should be, the given function also gets to decide when the list should end.
It does this by returning a
Just when the list should be extended with another element, and Nothing when the list should end.
- Also, new list elements are not computed from old ones, but instead from ‘seed’ values that can be of a different type.
Every time a next element is computed, a new ‘seed’ for the rest of the list is produced as well.
In the following example we compute the letters of the alphabet from their place in the sequence.
alphabet :: [Char]
alphabet = unfoldr nextLetter 0
where
nextLetter :: Int -> Maybe (Char, Int)
nextLetter index
| index == 26 = Nothing
| otherwise = Just (letterAt index, index + 1)
letterAt index = chr (ord 'a' + index)
-- >>> alphabet
-- "abcdefghijklmnopqrstuvwxyz"
iterate can be regarded as a special case of unfoldr.
Indeed, it could have been defined as
iterate :: (a -> a) -> a -> [a]
iterate f = unfoldr (\x -> Just (x, f x))
In this approach
Given any number, nextStep will compute the next Collatz number.
This is the only logic that is provided by us instead of by the standard library.
nextStep is used by iterate or unfoldr to generate all the steps.
The sequence of steps should be terminated at the first 1.
unfoldr does this by itself, but iterate needs some help from takeWhile.
With a complete sequence of steps, the only thing that remains to be done is to count them.
We simply use length for this.
Haskell’s laziness helps this approach be efficient.
length requests elements from the list of steps one by one.
These elements are generated on demand and discarded shortly after.
The full list of elements is never realized in memory: here the list functions less like a container and more like a generator from some other languages.
As a result, this solution operates in constant memory.
Recursion
Recursion
collatz :: Integer -> Maybe Integer
collatz n = case compare n 1 of
LT -> Nothing
EQ -> Just 0
GT -> (1 +) <$> collatz (if even n then n `div` 2 else 3 * n + 1)
The number of steps it takes to get to 1 is one plus however many more steps it will take after taking one step.
This suggest a recursive solution.
Recursion
Recursion in Haskell is the phenomenon of functions or values being defined in terms of themselves.
For example, here is a recursive definition of an (infinite) list:
-- A recursive (constant) value
ones :: [Integer]
ones = 1 : ones
-- 👆
-- recursion
-- `ones` is infinite, so take care to
-- ask for only finitely many elements
-- >>> take 5 ones
-- [1,1,1,1,1]
And here is a recursive definition of the well-known factorial function:
-- A recursive function
factorial :: Integer -> Integer
factorial n
| n <= 0 = 1
| otherwise = n * factorial (n - 1)
-- 👆
-- recursion
-- >>> factorial 5 == 5 * 4 * 3 * 2 * 1 * 1
-- True
This factorial function will always produce an output, because
- it contains a base case that directly results in output, and
- it only ever recursively applies itself to ‘smaller’ values than its own argument, and
- any series of ever ‘smaller’ values is guaranteed to eventually hit one of the base cases.
In the case of factorial 4 above we have
factorial 4
= (4 * factorial 3)
= (4 * (3 * factorial 2))
= (4 * (3 * (2 * factorial 1)))
= (4 * (3 * (2 * (1 * factorial 0))))
= (4 * (3 * (2 * (1 * 1))))
= (4 * (3 * (2 * 1)))
= (4 * (3 * 2))
= (4 * 6)
= 24
Haskell does not provide any dedicated loop devices such as many other languages’ for and while constructs.
Instead, all ‘loopiness’ in Haskell is produced through recursion – if not by you then under the hood of some of the functions you use.
In this approach
First, we compare the input with 1.
If it is less than 1 then the input is invalid and we return Nothing.
If it is exactly 1, then the number of steps it takes to reach 1 is zero – because we’re already there – so we return Just 0.
If the input is greater than 1, it’ll take at least one step to get to 1.
This step we calculate using the Collatz formula:
nextStep n = if even n then n `div` 2 else 3 * n + 1
After this step it’ll take some more (possibly zero) steps to reach 1.
To compute how many, we recursively call collatz.
The total number it will take to get to 1 is one more than whatever the recursive call finds.
The recursive calls produces a Maybe Integer rather than just an Integer, so we cannot just increment it.
Nothing that a bit of pattern matching won’t fix, however:
theAnswer =
case collatz (if even n then n `div` 2 else 3 * n + 1) of
Nothing -> Nothing
Just steps -> Just (steps + 1)
This pattern of mapping Nothing to Nothing and Just to Just is very common.
The function fmap was invented to do it for us:
-- >>> fmap (+1) Nothing
-- Nothing
-- >>> fmap (+1) (Just 6)
-- Just 7
It makes the code a lot more compact.
theAnswer =
fmap (1 +) (collatz (if even n then n `div` 2 else 3 * n + 1))
The solution highlighted at the top is slightly different: it uses <$> instead of fmap.
<$> is a synonym of fmap and so does exactly the same thing: fmap f xs == f <$> xs always.
Sometimes using the operator results in more readable code, but it might take some getting used to.
theAnswer =
(1 +) <$> collatz (if even n then n `div` 2 else 3 * n + 1)
Considerations on this approach
In a way, this solution is elegant.
However, it suffers an inefficiency.
For example, evaluation of collatz 16 might go as follows.
collatz 16
= (1 +) <$> collatz 8
= (1 +) <$> ((1 +) <$> collatz 4)
= (1 +) <$> ((1 +) <$> ((1 +) <$> collatz 2))
= (1 +) <$> ((1 +) <$> ((1 +) <$> ((1 +) <$> collatz 1)))
= (1 +) <$> ((1 +) <$> ((1 +) <$> ((1 +) <$> Just 0)))
= (1 +) <$> ((1 +) <$> ((1 +) <$> Just 1))
= (1 +) <$> ((1 +) <$> Just 2)
= (1 +) <$> Just 3
= Just 4
A tower of nested <$> applications forms!
For every step a <$> layer is added.
For numbers that take a long time to reach 1 this can take a lot of memory.
(As it happens, Collatz stopping times tend to be very short.
But the general points still stands.)
It is impossible to collapse the tower early.
<$> needs to know whether its right operand is a Nothing or a Just, but this does not become clear until the last step has been taken.
For an example of how to avoid this problem, see the worker–wrapper approach.
Worker–wrapper
Worker–wrapper
collatz :: Integer -> Maybe Integer
collatz n
| n > 0 = Just (go 0 n)
| otherwise = Nothing
where
go !acc 1 = acc
go !acc k = go (acc + 1) (if even k then k `div` 2 else 3 * k + 1)
This approach uses an inner worker function to simultaneously calculate successive steps and keep track of the number of steps already taken.
It also uses a bang pattern to force intermediate evaluation, to guarantee decent space efficiency.
The worker–wrapper construct
Sometimes, when solving a problem, it is more convenient or efficient to keep track of some kind of state.
Many other languages use local variables for this.
However, variables do not exist in Haskell: all bindings are constants.
In lieu of local variables we can add extra parameters to our functions.
These will hold our state.
‘Changing’ the state is done by calling the same functions (recursively) with different arguments.
Functions that uses such additional parameters to represent state are often called workers, and functions that use workers to solve a problem in a stateful way are often called wrappers.
As an example, consider the following possible definition of length.
length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
One problem with this function is that it builds large computations that take up potentially a lot of memory:
_ = length "abcde"
== 1 + length "bcde"
== 1 + (1 + length "cde")
== 1 + (1 + (1 + length "de"))
== 1 + (1 + (1 + (1 + length "e")))
== 1 + (1 + (1 + (1 + (1 + length ""))))
-- this computation is as large as the list was long!
== 1 + (1 + (1 + (1 + (1 + 0))))
== 1 + (1 + (1 + (1 + 1)))
== 1 + (1 + (1 + 2))
== 1 + (1 + 3)
== 1 + 4
== 5
It would be more efficient to keep track of a running total number of encountered elements.
To do this we can use a variant of length with an additional parameter:
length' :: Int -> [a] -> Int
length' count [] = count
length' count (_:xs) = length' (1 + count) xs
Here the parameter count is used to keep track of the number of previously encountered elements.
It might evaluate as follows.
_ = length' 0 "abcde"
== length' 1 "bcde"
== length' 2 "cde"
== length' 3 "de"
== length' 4 "e"
== length' 5 ""
== 5
The computation stays small at every step – much more efficient!
To obtain an efficient function length with the familiar [a] -> Int type – instead of the more involved Int -> [a] -> Int – we can ‘wrap’ length' in a function that provides it with initial arguments:
length :: [a] -> Int
length xs = length' 0 xs
where
length' count [] = count
length' count (_:xs) = length' (1 + count) xs
Here length is known as the wrapper, and length' as the worker.
Hence, this is an example of the worker–wrapper construct.
The worker is commonly called go, loop, or f' when the wrapper is called f.
The worker–wrapper pattern is more general than demonstrated here.
For a few more more examples, see the relevant wiki article, and for yet more examples and an explanation of the general pattern see the paper «The worker/wrapper transformation» (pdf).
Bang patterns
The above implementation of length' might evaluate as efficiently as illustrated.
However, depending on which optimization opportunities are spotted by the compiler, it also might not!
The definition of length' allows evaluation to proceed as follows as well.
_ = length' 0 "abcde"
== length' (1 + 0) "bcde"
== length' (1 + (1 + 0)) "cde"
== length' (1 + (1 + (1 + 0))) "de"
== length' (1 + (1 + (1 + (1 + 0)))) "e"
== length' (1 + (1 + (1 + (1 + (1 + 0))))) ""
== 1 + (1 + (1 + (1 + (1 + 0))))
== 1 + (1 + (1 + (1 + 1)))
== 1 + (1 + (1 + 2))
== 1 + (1 + 3)
== 1 + 4
== 5
Still a computation as large as the list was long is built.
The situation is not quite as bad as before though.
In the case of the naive implementation of length, the built up expression has the form
_ = 1 + (1 + (⋯(1 + length …)⋯))
This expression cannot be simplified before length … has been evaluated.
That is, simplification cannot begin until the last recursive step has been evaluated.
As a consequence, the computation must grow as big as the original list.
The computation built up by length' on the other hand has the form
_ = 1 + (1 + (⋯(1 + 0)⋯))
This can be simplified!
In fact, as illustrated in the previous section, it can be simplified at every individual step.
Haskell offers various ways to force intermediate evaluation.
One convenient tool is the bang pattern, enabled by the BangPatterns language extension.
{-# LANGUAGE BangPatterns #-} -- 👈 at the top of the file
length'' :: Int -> [a] -> Int
length'' !count [] = count
length'' !count (_:xs) = length'' (1 + count) xs
-- 👆
-- bang patterns
Bang patterns force evaluation of arguments at function invocation.
Consequently, this length'' (at worst) evaluates as follows.
_ = length'' 0 "abcde"
== length'' (1 + 0) "bcde"
== length'' (1 + 1) "cde"
== length'' (1 + 2) "de"
== length'' (1 + 3) "e"
== length'' (1 + 4) ""
== 1 + 4
== 5
Here, at each step the (1 + …) argument is reduced to a single number first, before again 1 is added to it.
We can eliminate even that last recurring + using another strictness management tool: the seq function.
length''' :: Int -> [a] -> Int
length''' count [] = count
length''' count (_:xs) =
let count' = 1 + count
in count' `seq` length''' count' xs
x `seq` y always returns y, but additionally guarantees that x is evaluated if y is evaluated.
Here, length''' uses it to guarantee that count' is evaluated ‘before’ it is passed to the recursive length''' call.
As a result, length''' evaluates optimally.
A full discussion of strictness in Haskell here would take up too much space.
Please consult your other learning resources.
The track docs include an article on Haskell learning resources.
Source: Exercism haskell/collatz-conjecture