如何用Haskell递归实现ved函数，仅删除列表最大元素最后一次出现

需求梳理 #

你需要的实现满足以下约束：

• 替换现有基于列表推导的「删除所有最大值实例」的实现，改为仅删除列表中最大元素的最后一次出现
• 完全基于递归实现，仅可使用:（cons运算符）、head、tail以及比较操作，不得调用其他任何Haskell库函数
• 不能直接使用现有代码里的maximum库函数，需要自行递归实现最大值查询逻辑

实现思路 #

我们分两步完成递归实现：

1. 先递归实现求列表最大值的函数rmax2：逐次对比当前元素和剩余子列表的最大值，返回较大的那个值即可
2. 再实现递归辅助函数处理列表：递归遍历到列表末端后反向判断，当首次遇到最大值（也就是原列表最后一次出现的最大值）时跳过该元素，其余元素直接保留即可，辅助函数返回二元组记录「处理后的子列表」和「是否已经删除过最大值」两个状态，避免二次遍历

完整代码 #

-- 递归求列表最大值，仅使用head、tail、比较操作
rmax2 :: Ord a => [a] -> a
rmax2 xs
  | tail xs == [] = head xs
  | otherwise = let h = head xs
                    tMax = rmax2 (tail xs)
                in if h >= tMax then h else tMax

ved :: Ord a => [a] -> [a]
ved [] = []
ved xs = let maxVal = rmax2 xs
             -- 辅助函数：返回(处理后的子列表, 该子列表是否已删除过最大值)
             helper [] = ([], False)
             helper currList = let curr = head currList
                                   rest = tail currList
                                   (processedRest, deleted) = helper rest
                               in if deleted
                                     -- 后续已经删过最大值，当前元素直接保留
                                     then (curr : processedRest, True)
                                     -- 后续还没删过最大值，判断当前元素是不是要删的那个
                                     else if curr == maxVal
                                             -- 当前是最后一个最大值，跳过不保留
                                             then (processedRest, True)
                                             -- 当前不是最大值，保留继续判断
                                             else (curr : processedRest, False)
             (res, _) = helper xs
         in res

效果验证 #

你可以直接调用测试效果：

• 输入ved [1,3,2,3,4]，输出为[1,3,2,3]（最后一个4被删除）
• 输入ved [5,2,5,3]，输出为[5,2,3]（第二个5是最后一个最大值，被删除）
• 输入ved [2]，输出为[]（唯一元素是最大值，直接删除）

内容的提问来源于stack exchange，提问作者King Valdimir