3

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?

jpmarinier
  • 4,427
  • 1
  • 10
  • 23
arsalanQ
  • 127
  • 6
  • 1
    If you had to come up with your own instance of `Enum` for the `Maybe Integer` type, how would you write the required `succ` function ? – jpmarinier Aug 20 '21 at 18:02
  • @jpmarinier I haven't learned much about instances yet but I came up with this: `instance (Num m) => Enum (Maybe m) where succ Nothing = Nothing succ (Just x) = Just (x + 1)` which compiles and allows me to use `succ` directly. I can see how this is basically replicating the same functionality of fmap for `Maybe` that Will explained below. – arsalanQ Aug 20 '21 at 21:03
  • 1
    yes, your instance does typecheck, and it is very close to `fmap succ`. But it is not really satisfactory at the semantic level, so it was not included in the language library. For example, Nothing is its own successor, which is not really the common idea of a successor; I see this is covered in the comments below Will's answer. BTW we have recently seen a couple of questions about the Collatz conjecture in Haskell (I will add the *Collatz* tag to your question). And for some reason they all insist on using Maybe. I am not sure this is really useful. Homework requirement ?? – jpmarinier Aug 20 '21 at 21:38
  • 1
    @jpmarinier this exercise is from Exercism's Haskell track and Maybe Integer is included as the output type in the provided type signature, so that may be the source of similar questions. I'm not sure if it's a strict requirement of the exercise (haven't tried omitting it to see if it still passes the test suite) or if it was just included for 'flavor' purposes to emphasize the unsolved nature of the Collatz conjecture. It certainly made the exercise much more challenging and was discouraging for me given it's categorized as Easy and is only the 5th exercise in the series. – arsalanQ Aug 21 '21 at 05:02
  • 2
    Thanks for pointing me to the Haskell track in Exercism. Apparently, Exercism is happy if one uses a [Maybe-free solution](https://exercism.io/tracks/haskell/exercises/collatz-conjecture/solutions/61d4e1e37ec1492fb141dc70d66ba689) for positive inputs, and just use the `Maybe` stuff to deal with negative inputs. – jpmarinier Aug 21 '21 at 11:22
  • @jpmarinier very nice solution and good to know that a semi-Maybe-free solution passes. I'll ultimately be taking this approach too but it was educational to go on this little detour and learn about structural wrapping :) – arsalanQ Aug 21 '21 at 20:41

1 Answers1

7

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
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Thank you very much for the thoughtful and detailed response. To paraphrase what I'm taking away from this: we can't call succ on a Maybe Integer to get an incremented Maybe Integer; instead we need to call succ on the regular Integer inside of its Maybe container and then return that value inside a Maybe container, which is what the specialized version of fmap for Maybe does. Is this correct? – arsalanQ Aug 20 '21 at 18:54
  • 2
    You might think that `succ Nothing` could be defined to return `Nothing`, but `Enum` also provides (and really, is primarily based on,) methods `toEnum :: Int -> a` and `fromEnum :: a -> Int`. There's no good choice for what `fromEnum Nothing` should return. – chepner Aug 20 '21 at 18:58
  • @chepner is this ambiguity around how to handle `Nothing` the underlying reason why we can't simply increment a `Maybe Integer`, and hence need to use `fmap`? It seems like doing `succ (Just 1)` should simply give `Just 2` without any extra hassle, but now that I consider it more, incrementing `Nothing` doesn't really make sense and thus handling these Maybe Integers can't be as straightforward as I might want it to be. – arsalanQ Aug 20 '21 at 19:08
  • 1
    we want to use `Maybe` as a _structural_ wrapper, not influencing the (optional) value inside it. thinking about `Maybe Integer` as an incrementable value in its own right is a completely different point of view. In your case there's no chance for the collatz sequence ever flipping sign, so `Nothing` is returned for the invalid - non-positive - inputs right away. – Will Ness Aug 20 '21 at 19:38
  • 2
    You could define `collatz` in terms of a helper function `collatz' :: Integer -> Integer`, where `collatz` is responsible for ensuring that `collatz'` is never called on a non-positive integer. `collatz n | n <=0 = Nothing; | otherwise = Just (collatz' n)`. Then `collatz'` would never need to use `fmap`, as it no longer receives a value of type `Maybe Integer`, only `Integer` values for which `succ` is defined. – chepner Aug 20 '21 at 19:57
  • 1
    ^^^ and that's what "structural wrapping" means: the contents and the wrapping are separate -- in the _data_, like in the original code in the question, mirroring the explicit separation in the _code_, as in the above comment. – Will Ness Aug 20 '21 at 20:21
  • @chepner Interesting - I hadn't thought of that approach and I think I like it better than using fmap. It makes what's going on with the wrapping more transparent and easier to grasp conceptually to me as a beginner. Thanks to you and Will for clearing this up for me. – arsalanQ Aug 21 '21 at 05:11
  • 1
    @arsalanQ here's also a [somewhat related entry](https://stackoverflow.com/q/54498459/849891). – Will Ness Aug 21 '21 at 15:38