How to properly type optional arguments in haskell

Question

I am trying to write a function that recursively determines the amount of steps needed to resolve the collatz conjecture. I want the function input to be just the starting input number for the series, with an additional counter variable to be added in the first iteration. The JS equivalent would look like:

const collatz = (v, count) => {
  if (!count) return collatz(v,0)
  if (v === 1) return count
  if (v % 2 === 0) return collatz(v/2, count + 1)
  return collatz(v*3+1, count + 1)
}

My Haskell code:

module CollatzConjecture (collatz) where
collatz :: Integer -> Maybe Integer -> Maybe Integer
collatz v () = collatz v 0
collatz 1 count = Just count
collatz v count 
  | even v = collatz (div v 2) next
  | otherwise = collatz (v * 3 + 1) next
  where next = count + 1

But the compiler complains

    • Couldn't match type ‘Maybe Integer’ with ‘Integer’
      Expected type: Maybe Integer
        Actual type: Maybe (Maybe Integer)
    • In the expression: Just count
      In an equation for ‘collatz’: collatz 1 count = Just count
  |
4 | collatz 1 count = Just count
  |                   ^^^^^^^^^^

What is the error in my thinking?

user_625403 · Answer

Don't pollute your function's public API with an extra parameter used only for an implementation detail. Instead, have your public 1-argument function delegate to a private 2-argument function. Often an internal function like this is named go, if you can't think of a better name.

collatz :: Integer -> Integer
collatz = go 0
  where go count 1 = count
        go count v | even v = next $ div v 2
                   | otherwise = next $ v * 3 + 1
          where next = go $ count + 1

I've also made some other improvements:

There's no reason to return a Maybe Integer when you never return Nothing.
I swapped the parameter order (count first) to make partial application of go and next more convenient.
Instead of defining your helper variable next as an integer, I've defined it as a partial application of go, so that your two cases only have to repeat next, rather than go (...) next.

The function as a whole would also be much simpler if you didn't do the counting yourself at all. I don't suggest this immediately, since it's fairly unrecognizable compared to your initial attempt, but an experienced Haskeller would write this more like:

collatz :: Integer -> Int
collatz = length . takeWhile (/= 1) . iterate step
  where step n | even n = n `div` 2
               | otherwise = 3 * n + 1

user_849891 · Answer

The error in your thinking is that Maybe is not a keyword, nor is it some kind of a hint to a compiler. It is a type constructor. Maybe Integer is a concrete, specific data type. It is used to represent the general concept of optionality, but by concrete values (of this type).

Each value in Haskell has one type. It can't be either Int or (). Haskell's sum types are tagged unions.

A type is a type -- one type. Values of type Maybe Int are written either Just i (where i :: Int, i.e. i has type Int) or Nothing, according to the data type definition for Maybe,

data Maybe a  =  Nothing
              |  Just a

Conceptually, Maybe Int is the same as Either () Int -- it does represent maybe an Int or nothing, ():

data Either a b  =  Left a
                 |  Right b

so Just i is just like Right i, and Nothing is like Left ().

But not i or () on their own -- they must be tagged with the appropriate data constructor, here Right or Left.

How to properly type optional arguments in haskell

2 Answers