Finding maximum element in a list of tuples

Question

I am a complete beginner in Haskell. I have a list of tuples that I'm using in Haskell: the structure is like this [(a,b),(c,d),(e,f),(g,h)]

What I want is to return the maximum element in this tuple according to the second value: So if the list of tuples is [(4,8),(9,10),(15,16),(10,4)], I want the maximum element to be (15,16).

But I have no idea how to do this. This is my attempt so far,

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

And I get this error message which makes no sense for me:

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

I need some help on how to do this.

Answer 1

The solutions presented so far have been very elegant, and you should probably use them in any real code you write. But here's a version that uses the same pattern-matching style that you're using.

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

This solution avoids juggling indices around, and instead just keeps track of the current maximum element, which is returned when the entire list has been traversed. Avoiding indices with lists is generally considered good practice.

Answer 2

The idiomatic way would be to use maximumBy (comparing snd).

The a ~ Int message means that for some reason Haskell infers that a must be an Int, but the type signature does not limit it to Ints. As Amos notes in the comments and GHC tells you with its source location, this is because you're using it as the second argument of !!, which is an Int.

Answer 3

An idiomatic way using the libraries is to use maximumBy.

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

Then all is left is to define the function of type a -> a ->Ordering so it knows how to order the elements. The usual way to construct Ordering objects is to use

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

Answer 4

It is also worth noting that tuples in Haskell are instances of Ord. Thus they can be ordered and compared. They are ordered using lexicographic ordering (primary by the first element of tuple, secondary by second etc.), so following holds:

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

If you want to get the tuple with maximal second element. You can just swap the elements of tuple for the maximum function and then swap the result elements like this:

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

Although for this to work both tuple elements must be instances of Ord.