Best recursion choice for "penultimax"

Dr Mark H Phillips mark@austrics.com.au
25 Nov 2002 15:21:38 +1030


Hi,

I have just implemented the function "penultimax" which takes a list
of positive integers and produces the "penultimate maximum", that is,
the next biggest integer in the list after the maximum.  Eg:

penultimax [15,7,3,11,5] = 11

One implementation is:

penultimax :: [Int] -> Int
penultimax ms = foldr max 0 (filter (<msMax) ms)
  where
  msMax = foldr max 0 ms

But I can think of two variations which might be more efficient:

penultimax2 :: [Int] -> Int
penultimax2 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>q       = penultimax2' ms p m
    | otherwise = penultimax2' ms p q

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

How do I work out which is best to use?  Is there
one clear "winner", or will they each have pros and
cons?

Thanks,

Mark.

-- 
Dr Mark H Phillips
Research Analyst (Mathematician)

AUSTRICS - smarter scheduling solutions - www.austrics.com

Level 2, 50 Pirie Street, Adelaide SA 5000, Australia
Phone +61 8 8226 9850
Fax   +61 8 8231 4821
Email mark@austrics.com.au