使用foldr的Haskell - MinMax

Question

我正在寻找一个Haskell函数，它接受一个列表作为参数并返回一个元组( min，max)，其中min是列表的最小值，max是最大值。

我已经有了这个：

maxMinFold :: Ord a => [a] -> (a, a)
maxMinFold list = foldr (\x (tailMin, tailMax) -> (min x tailMin) (max x tailMax)) -- missing part

你能帮我补充一下缺失的部分吗？(或者告诉我我做错了什么)

非常感谢

Answer 1

你拿着头，用它作为第一分钟，和最大，然后折叠在尾巴上。

maxMinFold :: Ord a => [a] -> (a, a)
maxMinFold (x:xs) = foldr (\x (tailMin, tailMax) -> (min x tailMin, max x tailMax)) (x,x) xs

至于您的回答，您的折叠函数没有返回正确的类型。

请注意，

foldr :: (a -> b **-> b**) -> b -> [a] -> b

特别地，您需要返回一个b，这在您的情况下是一个元组。

Answer 2

因为您总是必须遍历整个列表才能找到最小值和最大值，所以这里是使用foldl的解决方案

maxMinList :: Ord a => [a] -> (a,a)
maxMinList (x:xs) = foldl (\(l,h) y -> (min l y, max h y)) (x,x) xs

Answer 3

为了在foldr中高效地完成这个任务，

data NEList a = NEList a [a]
-- deriving (Eq, Ord, Show, Read, Functor, Foldable, Traversable)

minMax :: Ord a => NEList -> (a, a)
minMax (NEList x0 xs) = foldr go (,) xs x0 x0 where
  go x r mn mx
    | x < mn = r x mx
    | mx < x = r mn x
    | otherwise = r mn mx

另一种类似的办法是：

minMaxM :: Ord a => [a] -> Maybe (a, a)
minMaxM xs = foldr go id xs Nothing where
  go x r Nothing = r (Just (x, x))
  go x r mnmx@(Just (mn, mx))
    | x < mn = r (Just (x, mx))
    | mx < x = r (Just (mn, x))
    | otherwise = r mnmx