CODEWITHSUNDEEP
listhaskellmaxfold
enneenne
enneenne

Reputation: 219

haskell second largest element from list

I have this function that returns the second largest value from a given list:

import Data.List

secondL :: Ord a => [a] -> a
secondL xs = 
  let  x = head xs 
  in  let  find (a, b) x = (min b (max a x), max b x) 
     in  fst  (foldl find (x, x) xs)

This function should be working correctly, but for better purity I would like to exclude the function find's definition which is inside, and rework this function so that there is no other function declaration inside.

I was thinking about including (min b (max a x), max b x) into foldl argument, but this doesn't seem to be working well.

Upvotes: 2

Views: 446

Answers (1)

Will Ness
Will Ness

Reputation: 71119

listToMaybe . take 1 . drop 1 . sortBy (flip compare)
  :: Ord a => [a] -> Maybe a

will do this for you. It is even linear, because Haskell is lazy, and Haskell's sort is mergesort.

If you meant second largest, not second among the largest, you can just stick a nub in there to get it:

listToMaybe . take 1 . drop 1 . nub . sortBy (flip compare)
  :: Ord a => [a] -> Maybe a

It'll still be linear.

Trying it out:

> listToMaybe . take 1 . drop 1 . nub . sortBy (flip compare) $ [1,3,2,3,1]
Just 2

> listToMaybe . take 1 . drop 1 . nub . sortBy (flip compare) $ [3,3,3]
Nothing

(use https://hoogle.haskell.org/ to search for functions)

If you want to code it with left fold specifically, then

foo :: Ord a => [a] -> Maybe a
foo xs 
   | [_,y] <- foldl' g [] xs  =  Just y
   | otherwise  =  Nothing
  where
  g ys x  =  take 2 . nub . reverse . sort $ x:ys

Writing g out by hand with all the comparisons and the checks needed (or itself as a fold) is left as an exercise.

Upvotes: 3

Related Questions