Best recursion choice for "penultimax"

[Dean Herington]

Mark P Jones wrote:

> Moreover,
> in attempting to "optimize" the code, you might instead break it
> and introduce some bugs that will eventually come back and bite.

Indeed!  If we take Mark Phillips's original version of penultimax as our
specification, all four alternate versions are incorrect: They fail to
ignore duplicates of the maximum value.  Here are fixed versions.

penultimax2a :: [Int] -> Int
penultimax2a ms = penultimax2' ms 0 0
  where
  penultimax2' :: [Int] -> Int -> Int -> Int
  penultimax2' [] p q = q
  penultimax2' (m:ms) p q
    | m>p       = penultimax2' ms m p
    | m==p      = penultimax2' ms p q
    | m>q       = penultimax2' ms p m
    | otherwise = penultimax2' ms p q

penultimax3a :: [Int] -> Int
penultimax3a ms = snd (maxpenmax ms)
  where
  maxpenmax :: [Int] -> (Int,Int)
  maxpenmax [] = (0,0)
  maxpenmax [m] = (m,0)
  maxpenmax (m:ms)
    | m>p       = (m,p)
    | m==p      = (p,q)
    | m>q       = (p,m)
    | otherwise = (p,q)
    where
    (p,q) = maxpenmax ms

penultimax1a :: Ord a => [a] -> a
penultimax1a  = head . head . tail . group . sortBy (flip compare)

penultimaxa :: Ord a => [a] -> a
penultimaxa  = snd . tournament . map enter
 where enter x = (x, [])

       tournament [(x, xds)] = (x, maximum xds)
       tournament others     = tournament (round others)

       round ((x,xds):(y,yds):others)
                 | x>y       = (x, y:xds) : rest
                 | x==y      = (x, xds++yds) : rest
                 | otherwise = (y, x:yds) : rest
                   where rest = round others
       round xs              = xs

 -- Dean