How to extract the maximum element from a List in haskell?

Question

I am new to Haskell and I want to extract the maximum element from a given List so that I end up with the maximum element x and the remaining list xs (not containing x). It can be assumed that the elements of the list are unique.

The type of function I want to implement is somewhat like this:

maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])

Notably, the first argument is a function that turns an element into a comparable form. Also, this function is non-total as it would fail given an empty List.

My current approach fails to keep the elements in the remainder list in place, meaning given [5, 2, 4, 6] it returns (6, [2, 4, 5]) instead of (6, [5, 2, 4]). Furthermore, it feels like there should be a nicer looking solution.

compareElement :: (Ord b) => (a -> b) -> a -> (b, (a, [a])) -> (b, (a, [a]))
compareElement p x (s, (t, ts))
  | s' > s    = (s', (x, t:ts))
  | otherwise = (s, (t, x:ts))
  where s' = p x

maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
maxElement p (t:ts) = snd . foldr (compareElement p) (p t, (t, [])) $ ts

UPDATE

Thanks to the help of the answer of @Ismor and the comment @chi I've updated my implementation and I feel happy with the result.

maxElement :: (Ord b) => (a -> b) -> [a] -> Maybe (b, a, [a], [a])
maxElement p =
 let
    f x Nothing = Just (p x, x, [], [x])
    f x (Just (s, m, xs, ys))
      | s' > s = Just (s', x, ys, x:ys)
      | otherwise = Just (s, m, x:xs, x:ys)
      where s' = p x
  in
    foldr f Nothing

The result is either Nothing when the given list is empty or Maybe (_, x, xs, _). I could write another "wrapper" function with the originally intended type and call maxElement under the hood, but I believe this also ok.

Answer 1

This answer is more of a personal advise than a proper answer. As a rule of thumb, whenever you find yourself trying to write a loop with an accumulator (as in this case), try to write it in this form

foldr updateAccumulator initialAccumulator --use foldl' if it is better for your use case`

then, follow the types to complete It as shown below

Step 1

Write undefined where needed. You know the function should look like this

maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
maxElement f xs = foldr updateAccumulator initalAccumulator xs
 where 
  updateAccumulator  = undefined
  initialAccumulator = undefined

Step 2

"Chase the type". Meaning that using the type of maxElement and foldr you can deduce the types of updateAccumulator and initialAccumulator. Try to reduce polymorphism as much as you can. In this case:

• You know foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
• You know your Foldable is [] so It'd be easier to substitute
• Hence foldr :: (a -> b -> b) -> b -> [a] -> b
• Because you want foldr to produce (a, [a]) you know b ~ (a, [a])
• etc... keep going until you know what types your functions have. You can use ghc typed holes in this process, which is a very nice feature

maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
maxElement f xs = foldr updateAccumulator initalAccumulator xs
 where 
  -- Notice that you need to enable an extension to write type signature in where clause
  -- updateAccumulator :: a -> (a, [a]) -> (a, [a])
  updateAccumulator newElement (currentMax, currentList) = undefined
  -- initialAccumulator  :: (a, [a])
  initialAccumulator = undefined

Step 3

Now, writing down the function should be easier. Below I leave some incomplete parts for you to fill

maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
maxElement f xs = foldr updateAccumulator initalAccumulator xs
 where 
  -- updateAccumulator :: a -> (a, [a]) -> (a, [a])
  updateAccumulator newElement (currentMax, currentList) = 
    if f newElement > f currentMax
      then undefined -- How does the accumulator should look when the new element is bigger than the previous maximum?
      else undefined
  -- initialAccumulator  :: (a, [a])
  initialAccumulator = undefined -- Tricky!, what does happen if xs is empty?

Hope this clarifies some doubts, and understand I don't give you a complete answer.

Answer 2

I don't know if you were trying to avoid using certain library functions, but Data.List has a maximumBy and deleteBy that do exactly what you want:

import Data.Function (on)
import Data.List (deleteBy, maximumBy)
import Data.Ord (comparing)

maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
maxElement f xs = (max, remaining) where
  max = maximumBy (comparing f) xs
  remaining = deleteBy ((==) `on` f) max xs

Answer 3

Thanks to the help of the answer of @Ismor and the comment @chi I've updated my implementation and I feel happy with the result.

maxElement :: (Ord b) => (a -> b) -> [a] -> Maybe (b, a, [a], [a])
maxElement p =
 let
    f x Nothing = Just (p x, x, [], [x])
    f x (Just (s, m, xs, ys))
      | s' > s = Just (s', x, ys, x:ys)
      | otherwise = Just (s, m, x:xs, x:ys)
      where s' = p x
  in
    foldr f Nothing

The result is either Nothing when the given list is empty or Maybe (_, x, xs, _). I could write another "wrapper" function with the originally intended type and call maxElement under the hood, but I believe this is also ok.

Answer 4

Construct the list of all the "zippers" over the input list, then take the maximumBy (comparing (\(_,x,_) -> foo x)) of it, where foo is your Ord b => a -> b function, then reverse-append the first half to the second and put it in a tuple together with the middle element.

A zipper over a list xs is a triple (revpx, x, suffx) where xs == reverse revpx ++ [x] ++ suffx:

> :t comparing (\(_,x,_) -> x)
comparing (\(_,x,_) -> x)
  :: Ord a => (t, a, t1) -> (t, a, t1) -> Ordering

Constructing the zippers list is an elementary exercise (see the function picks3 there).

---

About your edited solution, it can be coded as a foldr over the tails so it's a bit clearer what's going on there:

maxElement :: (Ord b) => (a -> b) -> [a] -> Maybe (b, a, [a])
maxElement p [] = Nothing
maxElement p xs = Just $ foldr f undefined (tails xs)
 where
    f [x]     _   =  (p x, x, [])
    f (x:xs) (b, m, ys)
      | b' > b    =  (b', x, xs)   -- switch over
      | otherwise =  (b, m, x:ys)
      where b' = p x

It's also a bit cleaner as it doesn't return the input list's copy for no apparent reason, as your version did since it used it for internal purposes.

Both ways are in fact emulating a paramorphism.