如何从 haskell 中的列表中提取最大元素？

Question

我是 Haskell 的新手，我想从给定的 List 中提取最大元素，以便最终得到最大元素 x 和剩余列表 xs（不包含 x）。可以假设列表的元素是唯一的。

我要实现的功能类型有点像这样：

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

值得注意的是，第一个参数是一个将元素转换为可比较形式的函数。此外，此函数不是完整的，因为它会在给定空 List.

的情况下失败

我目前的方法无法将剩余列表中的元素保持在原位，这意味着给定 [5, 2, 4, 6] 它 returns (6, [2, 4, 5]) 而不是 (6, [5, 2, 4])。而且，感觉应该有更好看的方案。

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

更新

感谢@Ismor 的回答和评论@chi 的帮助，我更新了我的实现，我对结果感到满意。

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

当给定列表为空时，结果为 Nothing 或 Maybe (_, x, xs, _)。我可以用最初预期的类型编写另一个“包装器”函数并在后台调用 maxElement，但我相信这也可以。

Answer 1

此答案更像是个人建议，而非正确答案。根据经验，每当您发现自己试图用累加器编写循环（如本例）时，请尝试以这种形式编写它

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

然后按照类型完成如下图

第 1 步

在需要的地方写undefined。你知道这个函数应该是这样的

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

第 2 步

“追类型”。这意味着使用 maxElement 和 foldr 的类型你可以推导出 updateAccumulator 和 initialAccumulator 的类型。尽量减少多态性。在这种情况下：

你懂的foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
您知道您的 Foldable 是 []，所以替换起来会更容易
因此foldr :: (a -> b -> b) -> b -> [a] -> b
因为你想要foldr产生(a, [a])你知道b ~ (a, [a])
等等...继续前进，直到您知道您的函数有哪些类型。你可以在这个过程中使用ghc typed holes，这是一个非常好的功能

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

第 3 步

现在，写下函数应该更容易了。下面我留一些不完整的部分给大家补上

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?

希望这能澄清一些疑问，并理解我没有给你一个完整的答案。

Answer 2

在输入列表上构造所有“拉链”的列表，然后取其中的 maximumBy (comparing (\(_,x,_) -> foo x))，其中 foo 是您的 Ord b => a -> b 函数，然后反向追加前半部分到后半部分，并与中间元素一起放在一个元组中。

列表 xs 上的拉链是三元组 (revpx, x, suffx)，其中 xs == reverse revpx ++ [x] ++ suffx:

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

构建 zippers 列表是（请参阅那里的函数 picks3）。

关于您编辑的解决方案，它可以在 tails 上编码为 foldr，这样可以更清楚地了解那里发生的事情：

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

它也更简洁一些，因为它没有 return 没有明显原因的输入列表副本，就像您的版本那样，因为它将它用于内部目的。

这两种方式实际上都在模拟 paramorphism。

Answer 3

我不知道您是否试图避免使用某些库函数，但是 Data.List 有一个 maximumBy 和 deleteBy 完全符合您的要求：

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 4

感谢@Ismor 的回答和评论@chi 的帮助，我更新了我的实现，我对结果感到满意。

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

当给定列表为空时，结果为 Nothing 或 Maybe (_, x, xs, _)。我可以用最初预期的类型编写另一个“包装器”函数并在后台调用 maxElement，但我相信这也可以。

如何从 haskell 中的列表中提取最大元素？

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

haskell

functional-programming

list

第 1 步

第 2 步

第 3 步