Best recursion choice for "penultimax"

[Richard Braakman]

On Sun, Nov 24, 2002 at 10:06:42PM -0800, Mark P Jones wrote:
> To your three implementations, let me add another two.  If you are
> looking
> for the smallest possible definition, consider the following:
> 
>   import List
> 
>   penultimax1 :: Ord a => [a] -> a
>   penultimax1  = head . tail . sortBy (flip compare)

Hmm, I think penultimax was underspecified.  What should be the value
of penultimax [3, 4, 5, 5] ?  Your version would say 5, while
Dr. Phillips's original version would say 4.  If 4 is the correct answer,
then the definition could be corrected this way:

penultimax1' :: Ord a => [a] -> a
penultimax1' = head . tail . sortBy (flip compare) . nub

Doing both sort and nub is probably overkill, though I'm not sure how
expensive it actually is if only the first two elements are needed.
The order in which sort and nub are applied might make a difference, too.

Removing duplicate elements from a sorted list is much simpler than nub:

penultimax1'' :: Ord a => [a] -> a
penultimax1'' = head . tail . uniq . sortBy (flip compare)

uniq :: (Eq a) => [a] -> [a]
uniq (x : y : xs) | x == y = uniq (y : xs)
                  | otherwise = x : uniq (y : xs)
uniq xs = xs  -- empty and singleton lists

Richard Braakman