Поиск максимального элемента в списке кортежей

Question

Я полный новичок в Haskell. У меня есть список кортежей, которые я использую в Haskell: структура, как этот [(a,b),(c,d),(e,f),(g,h)]

То, что я хочу, чтобы вернуть максимальный элемент в этом наборе в соответствии со вторым значением: Таким образом, если список кортежей [(4,8),(9,10),(15,16),(10,4)], я хочу, чтобы максимальный элемент был (15,16).

Но я не знаю, как это сделать. Это моя попытка до сих пор,

maximum' :: (Ord a) => (Num a) => [(a,b)] -> a 
maximum' [] = error "maximum of empty list" 
maximum' [(x,y)] = -1 
maximum' (x:xs) 
    | snd x > snd(xs !! maxTail) = 0 
    | otherwise = maxTail 
    where maxTail = maximum' xs + 1 

И я получаю сообщение об ошибке, которое не имеет никакого смысла для меня:

newjo.hs:23:25: 
Could not deduce (a ~ Int) 
from the context (Ord a, Num a) 
    bound by the type signature for 
      maximum' :: (Ord a, Num a) => [(a, b)] -> a 
    at newjo.hs:19:14-47 
    `a' is a rigid type variable bound by 
     the type signature for maximum' :: (Ord a, Num a) => [(a, b)] -> a 
     at newjo.hs:19:14 
In the second argument of `(!!)', namely `maxTail' 
In the first argument of `snd', namely `(xs !! maxTail)' 
In the second argument of `(>)', namely `snd (xs !! maxTail)'` 

мне нужна помощь о том, как это сделать.

Answer 1

решений, представленных до сих пор было очень элегантно, и вы должны, вероятно, использовать их в любом реальном коде вы пишете. Но вот версия, которая использует тот же стиль соответствия шаблону, который вы используете.

maximum' :: Ord a => [(t, a)] -> (t, a) 
maximum' []  = error "maximum of empty list" 
maximum' (x:xs) = maxTail x xs 
    where maxTail currentMax [] = currentMax 
     maxTail (m, n) (p:ps) 
      | n < (snd p) = maxTail p ps 
      | otherwise = maxTail (m, n) ps 

Это решение позволяет избежать индексов жонглирование вокруг, а просто отслеживает текущий максимальный элемент, который возвращается, когда весь список был пройден. Как правило, избегать индексов со списками считается хорошей практикой.

Answer 2

Идиоматическим способом было бы использовать maximumBy (comparing snd).

a ~ Int сообщение означает, что по какой-то причине Haskell делает вывод, что a должен быть Int, но тип подписи не ограничивает его Int с. As Amos notes in the comments и GHC сообщают вам исходное местоположение, потому что вы используете его в качестве второго аргумента !!, который является Int.

Answer 3

Идиоматическим способом использования библиотек является использование maximumBy.

maximumBy :: (a -> a -> Ordering) -> [a] -> a 

Тогда все осталось определить функцию типа a -> a ->Ordering поэтому он знает, как заказать элементы. Обычный способ построения Ordering объектов является использование

compare :: (Ord a) => a -> a -> Ordering 

Answer 4

Следует также отметить, что кортежи в Haskell являются экземплярами Ord. Таким образом, их можно упорядочить и сравнить. Они упорядочены с помощью лексикографического упорядочения (первичного первого элементом кортежа, вторичного по второй и т.д.), так что имеет место следующего:

maximum [(1,1),(1,8),(2,1),(2,6)] == (2,6) 

Если вы хотите получить кортеж с максимальным вторым элементом. Вы можете просто поменять местами элементы кортежа для функции максимум, а затем поменять местами элементы результата, как это:

maximum' :: (Ord a, Ord b) => [(a,b)] -> (a,b) 
maximum' l = swap $ maximum $ map swap l 
      where swap (x, y) = (y, x) 

Хотя для этого, чтобы работать как кортежи элементы должны быть экземплярами Ord.