CODEWITHSUNDEEP
haskell
TMOTTM
TMOTTM

Reputation: 3391

Haskell: How to safely implement max using Maybe?

I'd like to implement a recursive safe max function that returns Nothing if an empty list is provided and Just a in case a maximum is found.

A naive approach (that just returns zero if an empty list is provided) would look like this:

max' :: [Int] -> Int
max' [] = 0
max' (x:xs) | x < max' xs = max' xs
            | otherwise = x

Now using the Prelude Maybe data type:

safeMax :: (Ord a) => [a] -> Maybe a
safeMax [] = Nothing
safeMax [x] = x
safeMax (x:y:xs) | x = safeMax (y:xs)
               | otherwise = Just x

I get the message that it cannot construct the infinite data type a ~ Maybe a. What is here the problem?

The full error message is this:

safemax.hs:33:15: error:
    • Occurs check: cannot construct the infinite type: a ~ Maybe a
    • In the expression: x
      In an equation for ‘safeMax’: safeMax [x] = x
    • Relevant bindings include
        x :: a (bound at safemax.hs:33:10)
        safeMax :: [a] -> Maybe a (bound at safemax.hs:32:1)
   |
33 | safeMax [x] = x

Solution: Use Just x and use x < y:

safeMax :: (Ord a) => [a] -> Maybe a
safeMax [] = Nothing
safeMax [x] = Just x
safeMax (x:y:xs) | x < y = safeMax (y:xs)
               | x > y = safeMax (x:xs)
               | otherwise = Just x

Upvotes: 1

Views: 292

Answers (2)

chepner
chepner

Reputation: 532003

Your first attempt is close. safeMax [] isn't really a base case, since no recursive call will ever be made on a empty list (the second case safeMax [x] = ... ensures that). So once you know that safeMax (y:xs) in your third case can only return a Just value, you can safely pattern match on that.

safeMax (x:y:xs) = let Just y' = safeMax (y:xs)
                   in Just $ if x >= y' then x else y'

Now you'll realize that you unnecessarily matched the tail of the original input; you don't care about the value of y at all. Get rid of it, and just recurse on the tail.

safeMax (x:xs) = let Just y = safeMax xs
                 in Just $ if x >= y then x else y

Since [] isn't really a base case, you can define safeMax to use a helper function that can assume a non-empty list.

safeMax [] = Nothing
safeMax = Just . safeMax'
   where safeMax' [x] = Just x
         safeMax' (x:xs) = let y = safeMax' xs
                           in if x >= y then x else y

Of course, safeMax' is just Prelude.maximum, so you can write, as suggested by Daniel Wagner,

safeMax [] = Nothing
safeMax xs = Just (maximum xs)

Upvotes: 0

Code-Apprentice
Code-Apprentice

Reputation: 83557

I believe the problem is with x < safeMax xs. Here you are trying to use (<) to compare an a with a Maybe a. You need to unwrap the return value from safeMax xs before doing this comparison.

Upvotes: 1

Related Questions