Haskell function seeking further explanation

Question

I've been trying to create a haskell function which gets the largest odd integer in a list. Sounds easy, and I sure thought I could do it but it looks like I'm stuck! Here is my code, so far it returns the largest number in the list including both odd and even numbers:

maximum :: (Ord a) => [a] -> a  
maximum [x] = x  
maximum (x:xs) = max x (maximum xs)

Thank you in advance for your help!

Answer 1

There are several options which all teach you something about the language. First of all, there's the issue with totality that epsilonhalbe mentioned. For now, I will just have the code throw an error.

maximumOddError :: a
maximumOddError = error "maximumOdd: list contains no odd element"

The most important complication is that when you start you don't know if there will be any odd numbers at all. So you either have to defer that test (we'll come to that) or filter and check in one go.

Option 1: Tail recursion

The simplest solution is to do both checks in one. In general this is also a nice optimization technique. For now, it separates error handling and iteration.

maximumOdd :: (Integral a) => [a] -> a
maximumOdd ls = case dropWhile even ls of
                  []   -> maximumOddError
                  n:ns -> findOddMax n ns -- n is definitely odd
  where
    findOddMax currentMax [] = currentMax
    findOddMax currentMax (x:xs)
        | even x         = findOddMax currentMax xs
        | x < currentMax = findOddMax currentMax xs
        | otherwise      = findOddMax x          xs

Option 2: Sort

Instead of looking at every piece, you could also take a high-level perspective. Why search, when you could instead just sort the list and have the element you search be presented at one end? Of course you must still filter, so basically what you want is something like last . sort . filter odd. But last is another traversal, so it's better to sort the list in descending order:

import Data.List ( sortBy )

maximumOdd :: (Integral a) => [a] -> a
maximumOdd = head . sortBy reverseOrder . filter odd
  where
    reverseOrder a b = compare b a

Note that head will fail on empty lists. So the error handling isn't as nice. But it should be easy to add. What's the performance compared to a simple maximum . filter odd? You tell me!

Option 3: Tail recursion with nice error handling

Now let's add some better error handling via Maybe. The easiest version to do that is the tail recursive one, as we separated error handling and iteration.

maximumOdd :: (Integral a) => [a] -> Maybe a
maximumOdd ls = case dropWhile even ls of
                  []   -> Nothing
                  n:ns -> Just $ findOddMax n ns -- n is definitely odd
  where
    findOddMax … -- same as above

This is very much the same method as dfeuer's. He just used more existing functions to make it shorter and even more efficient, and he integrated error handling into the recursion. That is what most experienced Haskell programmers will do. (You could argue about performance costs of wrapping and unwrapping, but eh. Do that when you need it.)

Option 4: Sort with nice error handling

This one is easy as well, because there's a nice version of head that does exactly what we need.

import Data.Maybe ( listToMaybe )

maximumOdd :: (Integral a) => [a] -> Maybe a
maximumOdd = listToMaybe . sortBy reverseOrder . filter odd
  where
    reverseOrder a b = compare b a

Option 5: Direct traversal with nice error handling

Finally, we're back to the initial approach. But Maybe now allows us to defer error checking. The thing is: You need to know some special tools, or you must invent them. I'll just use the existing ones.

import Control.Applicative ( (<|>) )

maximumOdd :: (Integral a) => [a] -> Maybe a
maximumOdd []                 = Nothing
maximumOdd [x]    | even x    = Nothing
                  | otherwise = Just x
maximumOdd (x:xs) | even x    =           maximumOdd xs
                  | otherwise = max x <$> maximumOdd xs -- either "max x" applied inside the Maybe-construct
                                <|> Just x              -- or x, if that produced an error

Answer 2

maximumOdd :: Integral a => [a] -> Maybe a
maximumOdd = foldl' go Nothing
  where
    go Nothing x | odd x = Just x
    go (Just gr) x | odd x && x > gr = Just x
    go acc _ = acc

Answer 3

First of all - if you have only even elements in your list you have a problem, as your function is not total (i.e. it produces an error) - so it is best to modify the type of your result to account for that possibility:

Also as others have already mentioned - odd requires your constraint to be Integral instead of Ord.

maximodd :: Integral a => [a] -> Maybe a
maximodd xs = case filter odd xs' of
                []  -> Nothing
                xs' -> Just (maximum xs')

The function filter odd removes all non-odd elements (i.e. all even numbers) - then we pattern match on the result to account for failure.

If you want to work with your original function then the code gets a lot more tricky:

maximum :: Integral a => [a] -> a
maximum [x] = x
maximum (x:xs) = let y = maximum xs
                 in if x >= y && odd x
                      then x
                      else if x < y && odd y
                             then y
                             else ??

hmm - I don't think you can make it work like this - but maybe with a helper function.

maximum :: Integral a => [a] -> Maybe a
maximum xs = maximum' Nothing xs
  where maximum' Nothing (x:xs) = if odd x
                                    then maximum' (Just x) xs
                                    else maximum' Nothing xs
        maximum' (Just y) (x:xs) = if odd x
                                     then maximum' (Just $ max x y) xs
                                     else maximum' (Just y) xs
        maximum' x _ = x

Which is also more complicated - and haskell is definitely not known for being complicated ;)