create a function ved that will only remove the last occurrence of the largest item in the list using recursion

Question

You must use recursion to define rmax2 and you must do so from “scratch”. That is, other than the cons operator, head, tail, and comparisons, you should not use any functions from the Haskell library.

I created a function that removes all instances of the largest item, using list comprehension. How do I remove the last instance of the largest number using recursion?

ved :: Ord a => [a] -> [a]
ved [] =[]
ved as = [ a | a <- as, m /= a ]
  where m= maximum as

Answer 1

An easy way to split the problem into two easier subproblems consists in:

1. get the position index of the rightmost maximum value
2. write a general purpose function del that eliminates the element of a list at a given position. This does not require an Ord constraint.

If we were permitted to use regular library functions, ved could be written like this:

ved0 :: Ord a => [a] -> [a]
ved0  [] = []
ved0 (x:xs) =
    let
        (maxVal,maxPos) = maximum (zip (x:xs) [0..])
        del k ys        = let (ys0,ys1) = splitAt k ys  in  (ys0 ++ tail ys1)
    in
        del maxPos (x:xs)

where the pairs produced by zip are lexicographically ordered, thus ensuring the rightmost maximum gets picked.

We need to replace the library functions by manual recursion.

Regarding step 1, that is finding the position of the rightmost maximum, as is commonly done, we can use a recursive stepping function and a wrapper above it.

The recursive step function takes as arguments the whole context of the computation, that is:

1. current candidate for maximum value, mxv
2. current rightmost position of maximum value, mxp
3. current depth into the original list, d
4. rest of original list, xs

and it returns a pair: (currentMaxValue, currentMaxPos)

-- recursive stepping function:
findMax :: Ord a => a -> Int -> Int -> [a] -> (a, Int)
findMax mxv mxp d  []    = (mxv,mxp)
findMax mxv mxp d (x:xs) = if (x >= mxv) then  (findMax x d (d+1) xs)
                                         else  (findMax mxv mxp (d+1) xs)

-- top wrapper:
lastMaxPos :: Ord a => [a] -> Int
lastMaxPos  []    = (-1)
lastMaxPos (x:xs) = snd (findMax x 0 1 xs)

Step 2, eliminating the list element at position k, can be handled in very similar fashion:

-- recursive stepping function:
del1 :: Int -> Int -> [a] -> [a]
del1 k d  []    = []
del1 k d (x:xs) = if (d==k)  then  xs  else  x : del1 k (d+1) xs

-- top wrapper:
del :: Int -> [a] -> [a]
del k xs = del1 k 0 xs

Putting it all together:

We are now able to write our final recursion-based version of ved. For simplicity, we inline the content of wrapper functions instead of calling them.

-- ensure we're only using authorized functionality:
{-#  LANGUAGE  NoImplicitPrelude    #-}
import Prelude (Ord, Eq, (==), (>=), (+), ($), head, tail,
                IO, putStrLn, show, (++))  -- for testing only


ved :: Ord a => [a] -> [a]
ved  []    = []
ved (x:xs) =
    let
        findMax mxv mxp d  []    = (mxv,mxp)
        findMax mxv mxp d (y:ys) = if (y >= mxv) then  (findMax y d (d+1) ys)
                                                 else  (findMax mxv mxp (d+1) ys)
        (maxVal,maxPos) = findMax x 0 1 xs
        del1 k d (y:ys) = if (d==k)  then  ys  else  y : del1 k (d+1) ys
        del1 k d  []    = []
    in
        del1 maxPos 0 (x:xs)


main :: IO ()
main = do
    let  xs  = [1,2,3,7,3,2,1,7,3,5,7,5,4,3]
         res = ved xs
    putStrLn $ "input=" ++ (show xs) ++ "\n" ++ "  res=" ++ (show res)

Answer 2

Borrowing the implementation of dropWhileEnd from Hackage, we can implement a helper function splitWhileEnd:

splitWhileEnd :: (a -> Bool) -> [a] -> ([a], [a])
splitWhileEnd p = foldr (\x (xs, ys) -> if p x && null xs then ([], x:ys) else (x:xs, ys)) ([],[])

splitWhileEnd splits a list according to a predictor from the end. For example:

ghci> xs = [1,2,3,4,3,2,4,3,2]
ghci> splitWhileEnd (< maximum xs) xs
([1,2,3,4,3,2,4],[3,2])

With this helper function, you can write ven as:

ven :: Ord a => [a] -> [a]
ven xs = 
    let (x, y) = splitWhileEnd (< maximum xs) xs
     in init x ++ y

ghci> ven xs
[1,2,3,4,3,2,3,2]

For your case, you can refactor splitWhileEnd as:

fun p = \x (xs, ys) -> if p x && null xs then ([], x:ys) else (x:xs, ys)
splitWhileEnd' p [] = ([], [])
splitWhileEnd' p (x : xs) = fun p x (splitWhileEnd' p xs)

ven' xs = let (x, y) = splitWhileEnd' (< maximum xs) xs in init x ++ y

If init and ++ are not allowed, you can implement them manually. It's easy!

BTW, I guess this may be your homework for Haskell course. I think it's ridiculous if your teacher gives the limitations. Who is programming from scratch nowadays?

Anyway, you can always work around this kind of limitations by reimplementing the built-in function manually. Good luck!

Answer 3

If you are strictly required to use recursion, you can use 2 helper functions: One to reverse the list and the second to remove the first largest while reversing the reversed list.

This result in a list where the last occurrence of the largest element is removed.

We also use a boolean flag to make sure we don't remove more than one element.

This is ugly code and I really don't like it. A way to make things cleaner would be to move the reversal of the list to a helper function outside of the current function so that there is only one helper function to the main function. Another way is to use the built-in reverse function and use recursion only for the removal.

removeLastLargest :: Ord a => [a] -> [a]
removeLastLargest xs = go (maximum xs) [] xs where
  go n xs []     = go' n True [] xs
  go n xs (y:ys) = go n (y:xs) ys
  go' n f xs []  = xs
  go' n f xs (y:ys)
    | f && y == n = go' n False xs ys
    | otherwise   = go' n f (y:xs) ys