CODEWITHSUNDEEP
haskelloption-type
adsbb pppp
adsbb pppp

Reputation: 53

How to find Maximum element in List with maybe output

This code works

max_elem :: (Ord a) => [a] -> a 
max_elem [x] = x 
max_elem [] = error "No elements" 
max_elem (x:xs)  
    |x > max_elem xs = x 
    |otherwise = max_elem xs

I want to have it so it returns Nothing if their are no elements and Just x for the maximum element I tried the following

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

I got the following error. Recommendations to fix this please.

 • Couldn't match expected type ‘a’ with actual type ‘Maybe a’
      ‘a’ is a rigid type variable bound by
        the type signature for:
          max_elem :: forall a. Ord a => [a] -> Maybe a
        at <interactive>:208:13
    • In the second argument of ‘(>)’, namely ‘max_elem xs’
      In the expression: x > max_elem xs
      In a stmt of a pattern guard for
                     an equation for ‘max_elem’:
        x > max_elem xs
    • Relevant bindings include
        xs :: [a] (bound at <interactive>:211:13)
        x :: a (bound at <interactive>:211:11)
        max_elem :: [a] -> Maybe a (bound at <interactive>:209:1)

Upvotes: 2

Views: 3271

Answers (4)

Justin L.
Justin L.

Reputation: 13600

The problem is x > max_elem xs; max_elem xs is Maybe a, not a, meaning that it might return Nothing. However, you do know that it will only return Nothing if xs is empty, but you know xs won't be empty because you matched the case where it would using [x]. You can take advantage of this fact by writing a "non-empty" maximum:

max_elem_ne :: Ord a => a -> [a] -> a
max_elem_ne m []     = m
max_elem_ne m (x:xs)
  | m > x     = max_elem m xs
  | otherwise = max_elem x xs

Or, alternatively, using max:

max_elem_ne :: Ord a => a -> [a] -> a
max_elem_ne m []     = m
max_elem_ne m (x:xs) = max_elem (max m x) xs

You can think of the first argument as the maximum value seen "so far", and the second list argument as the list of other candidates.

In this last form, you might have noticed that max_elem_ne is actually a just left fold, so you could even just write:

max_elem_ne :: Ord a => a -> [a] -> a
max_elem_ne = foldl' max

Now, with max_elem_ne, you can write your original max_elem:

Then you can write:

max_elem :: Ord a => [a] -> Maybe a
max_elem []     = Nothing
max_elem (x:xs) = Just (max_elem_ne x xs)

So you don't have to do any extraneous checks (like you would if you redundantly pattern matched on results), and the whole thing is type-safe.

You can also use the uncons :: [a] -> Maybe (a,[a]) utility function with fmap and uncurry to write:

max_elem :: Ord a => [a] -> Maybe a
max_elem = fmap (uncurry max_elem_ne) . uncons

Upvotes: 0

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476534

We can generalize this task and work with all Foldables. Here we thus use the foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b function that folds a certain Foldable structure. We can do this with the function max . Just, and as initial element Nothing:

max_elem :: (Ord a, Foldable f) => f a -> Maybe a 
max_elem = foldr (max . Just) Nothing

Note that this works since Haskell defines Maybe a to be an instance of Ord, given a is an instance of Ord, and it implements it in a way that Nothing is smaller than any Just element.

This makes the above definition perhaps a bit "unsafe" (in the sense that we here rely on the fact that from the moment we have a Just x, the max will select such Just x over a Nothing). When we would use min, this would not work (not without using some tricks).

We can also use pattern guards and thus solve the case where the list is empty in a different way, like:

max_elem :: Ord a => [a] -> Maybe a 
max_elem [] = Nothing
max_elem l = Just (maximum l)

Upvotes: 1

wisn
wisn

Reputation: 1024

The error message was clear enough to solve your problem.

|x >  max_elem xs = Just x

The problem is that you compare x which is a with max_elem which is Maybe a. That's why you got such error message. You can solve the problem with this code below.

max_elem :: (Ord a) => [a] -> Maybe a 
max_elem []     = Nothing
max_elem (x:xs) = case (max_elem xs) of
  Nothing -> Just x
  Just y  -> if x > y then Just x else Just y

Upvotes: 2

Shersh
Shersh

Reputation: 9169

You get your error because of this line: x > max_elem xs. max_elem xs has type Maybe a where a is an element of a list. It has type a. You can't compare values of different types. a and Maybe a are different types. See Haskell equality table:

Replace == operator with > and you will get the same table.

You can solve problem in your code by replacing x > max_elem xs with Just x > max_elem xs. Does it make sense to you?

As you can see, Maybe a data type has Ord a => Ord (Maybe a) instance which is actually really handy! So you can implement your function in even more concise way to utilize this Ord instance:

max_elem :: Ord a => [a] -> Maybe a 
max_elem = foldr max Nothing . map Just

Though, this probably won't be the most efficient solution if you care about performance.

Upvotes: 2

Related Questions