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.

CodePudding user response：

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.

CodePudding user response：

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.