How many functions for Maybe a -> Maybe a?

Question

In Thinking Functionally with Haskell (p 45), Richard Bird says there are six functions with type Maybe a -> Maybe a, though he only names five.

Applied to Nothing the function can only return Nothing or undefined. Applied to Just x the function can only return Nothing or Just x or undefined. The point is that we know absolutely nothing about the underlying type, so no new values can be invented. That makes six possible functions in all.

I count seven:

first, second, third, fourth, fifth, sixth, seventh :: Maybe a -> Maybe a

first (Just x) = Just x
second (Just x) = Nothing
third (Just x) = undefined
fourth Nothing = Nothing
fifth Nothing = undefined
sixth undefined = Nothing
seventh undefined = undefined

A related puzzle is that when I try to put three of these definitions under a single function, I get a compilation error "Pattern match is redundant." Removing any of the three lines causes it to disappear

foo :: Maybe a -> Maybe a
foo (Just x) = Nothing
foo Nothing = undefined
foo undefined = Nothing

Answer 1

Your functions are not fully specified -- each time they take only one case. This means that the case that is not covered, errors.

so essentially if you write:

first (Just x) = Just x

it is:

first (Just x) = Just x
first _ = error "case not covered"

You thus need to cover the two cases combined: Just x, or Nothing and thus multiply the possibilities of each case.

Another problem is that undefined in sixth undefined = Nothing does not check if the item is undefined: it is just a variable named undefined. So it is equivalent to sixth x = Nothing.

So that leaves us essentially with three options for Just x: Just x, Nothing and undefined/error, and two options for Nothing: Nothing and undefined, so:

first (Just x) = Just x
first Nothing = Nothing

second (Just x) = Just x
second Nothing = undefined

third (Just x) = Nothing
third Nothing = Nothing

fourth (Just x) = Nothing
fourth Nothing = undefined

fifth (Just x) = undefined
fifth Nothing = Nothing

sixth (Just x) = undefined
sixth Nothing = undefined

These are however not all the options: you can also return Just undefined (or Just (error "<undefined>")) for any of the two cases. I leave listing these as an exercise.