8

我是 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)'`

我需要一些关于如何做到这一点的帮助。

4

4 回答 4

27

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

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

于 2013-08-08T05:15:47.703 回答
11

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

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

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

compare :: (Ord a) => a -> a -> Ordering
于 2013-08-08T05:16:00.560 回答
4

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

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

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

于 2013-08-08T07:13:27.083 回答
1

同样值得注意的是，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的实例。

于 2016-09-14T17:21:52.173 回答