```
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.