maxTwo Implementation Haskell

Question

Given a list of integers xs, find the two largest values and return them in a pair (largest first). Largest duplicates should be preserved (included) in the output. Do not modify the original list.

This is what I came up with but it did not quite give the correct answer. Here is the code and the second section is the terminal run:

minInt = minBound :: Int

maxTwoHelper1 :: [Int] -> (Int, Int)
maxTwoHelper1 (x : xs) = maxTwoHelper2 minInt minInt xs

maxTwoHelper2 :: Int -> Int -> [Int] -> (Int, Int)
maxTwoHelper2 first second [] = (first, second)
maxTwoHelper2 first second (x : xs)
  | x >= first = maxTwoHelper2 x second xs
  | x >= second = maxTwoHelper2 first x xs
  | otherwise = maxTwoHelper2 first second xs

*Main> maxTwoHelper1 [1,0,-1]
(0,-1)

Answer 1

Your maxTwoHelper1 is dropping the x, it should consider all elements, so:

maxTwoHelper1 :: [Int] -> (Int, Int)
maxTwoHelper1 xs = maxTwoHelper2 minBound minBound xs

Your maxTwoHelper2 also contains an error: in case x >= first, x is the largest, and first the second largest, so:

maxTwoHelper2 :: Int -> Int -> [Int] -> (Int, Int)
maxTwoHelper2 first second [] = (first, second)
maxTwoHelper2 first second (x : xs)
  | x >= first = maxTwoHelper2 x first xs  -- ? first as second largest
  | x >= second = maxTwoHelper2 first x xs
  | otherwise = maxTwoHelper2 first second xs

Answer 2

The easiest way is to use sortBy:

import Data.List (sortBy)
import Data.Function (on)
import Data.Ord (Down (..))

maxTwo :: (Ord a, Bounded a) => [a] -> (a, a)
maxTwo xs = case sortBy (compare `on` Down) xs of
  [] -> (minBound, minBound)
  [biggest] -> (biggest, minBound)
  biggest : second : _ -> (biggest, second)

-- Or, if you don't mind "can't happen" errors:

maxTwo :: (Ord a, Bounded a) => [a] -> (a, a)
maxTwo xs = case sortBy (compare `on` Down) $ minBound : minBound : xs of
  biggest : second : _ -> (biggest, second)
  _ -> error "Impossible!"

This is efficient because the sortBy function uses an incremental sort (it happens to be a lazy bottom-up merge sort, but there are also incremental versions of heapsort and quicksort available). It only takes time O(n + k * log k) to get the first k elements of the result of sorting n elements. See these slides for a proof. So getting the k biggest elements for any fixed k (in this case 2) takes O(n) time.