Haskell - MinMax using foldr

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 

Answer 4

Было бы хорошо, если функция minMax вернулся Nothing в случае пустого списка. Вот версия, которая делает это.

import Control.Arrow 
import Data.Maybe 
import Data.Foldable 

minMax :: (Ord a) => [a] -> Maybe (a,a) 
minMax = foldl' (flip $ \ x -> Just . maybe (x,x) (min x *** max x)) Nothing 

foldl' Это использует вместо foldr.