查找元组列表中的最大元素

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

惯用的方式是使用maximumBy (comparing snd).

该a ~ Int消息意味着由于某种原因Haskell推断a必须是a Int,但类型签名不会将其限制为Ints.正如Amos在评论中指出的那样,GHC告诉你它的源位置,这是因为你使用它作为第二个参数!!,这是一个Int.

Answer 2

使用库的惯用方法是使用maximumBy.

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

然后剩下的就是定义类型的函数,a -> a ->Ordering以便它知道如何对元素进行排序.构造Ordering对象的常用方法是使用

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

Answer 3

到目前为止提出的解决方案非常优雅，您可能应该在编写的任何实际代码中使用它们。但这里的版本使用与您正在使用的相同的模式匹配样式。

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

该解决方案避免了杂乱索引，而只是跟踪当前最大元素，该元素在遍历整个列表时返回。避免使用列表索引通常被认为是良好的做法。