Why is `fmap` needed to call `succ` on a `Maybe Integer`?

Question

I am brand new to Haskell and am working on a practice Collatz conjecture problem. The required output is the number of steps needed to get to 1 from a given integer. This is the first time I've had to use the Maybe type, which may be contributing to my confusion.

I have this working solution based on another solution I found to the same problem:

collatz :: Integer -> Maybe Integer
collatz n
    | n <= 0 = Nothing
    | n == 1 = Just 0
    | even n = fmap succ . collatz $ n `div` 2
    | otherwise = fmap succ . collatz $ 3 * n + 1

What is unclear to me is why it is necessary to use fmap succ in this situation. Based on my current understanding, I would expect to just be able to call succ on the output of the recursive call to collatz in order to increment it; however, this throws an error:

> No instance for (Enum (Maybe Integer))
        arising from a use of `succ'

It looks like the error has something to do with calling succ on a Maybe Integer type instead of an Integer. Is the error because a Maybe Integer isn't considered enumerable in Haskell? If so why does calling fmap succ solve this problem?

Answer 1

If you just start learning Haskell, using . and $ needlessly present an additional cognitive load for you. What you have is simpler written as

collatz :: Integer -> Maybe Integer
collatz n
    | n <= 0    = Nothing
    | n == 1    = Just 0
    | even n    = fmap succ (collatz (n `div` 2))
    | otherwise = fmap succ (collatz (3 * n + 1))

Now, what is succ? If we look at its type,

> :t succ
succ :: Enum a => a -> a

the main thing to notice is that the input and the output types are one and the same. It is also an instance of the Enum class of types, which is just to say that this type implements its specific version of the succ function (it's a bit circular that way).

Since we're dealing with Integers, which do implement their version of succ as

succ :: Integer -> Integer
succ i = i + 1

it's all good and taken care of.

Except collatz :: Integer -> Maybe Integer takes an Integer and returns a Maybe Integer:

-- pseudocode
Maybe Integer = Nothing
              | Just      Integer
             -- ^ tags    ^ types of contained data

So we need to apply succ to the contained Integer. And that's the job of fmap:

-- pseudocode
> :t fmap
fmap :: Functor f => (a -> b) -> f     a -> f     b
> :t fmap @ Maybe
fmap ::              (a -> b) -> Maybe a -> Maybe b
> :t fmap @ Maybe succ @ Integer
fmap ::                    Maybe Integer -> Maybe Integer

Which is a generic function defined by a class of types that each define their specialized version of it. As Maybe indeed does:

-- pseudocode:
fmap f Nothing  = Nothing
fmap f (Just i) = Just (f i)
                --      ^^ f applied on the "inside"
                --      ^^ when there is something in there