Haskell second smallest value in list

  • A+
Category:Languages

I'm trying to write a function secondSmallest that returns the second smallest value in the list, or Nothing if there is no such value. Also, if the smallest value of the list occurs multiple times, it's also the second smallest. For example:

  • secondSmallest [1.0] --> Nothing
  • secondSmallest [1,1,2] --> Just 1
  • secondSmallest [5,3,7,2,3,1] --> Just 2

Here's what I have so far:

secondSmallest :: Ord a => [a] -> Maybe a secondSmallest []       = Nothing secondSmallest [x]      = Nothing secondSmallest (x:y:xs) = Just secondSmallest ((if x < y then x else y):xs) 


Using sort

A lazy approach is by using sort :: Ord a => [a] -> [a]. sort returns a sorted list, but in a lazy manner, and obtaining the k-th element, with O(n) for a fixed element, and in case we enumerate up to the k-th element, it will take O(n log k), we can thus perform pattern matching on the sort result, and then return the second element, like:

import Data.List(sort)  secondSmallest :: Ord a => [a] -> Maybe a secondSmallest l | (_:x:_) <- sort l = Just x                  | otherwise = Nothing 

By using an accumulator

Another approach is by using an accumulator. An accumulator is a parameter in the recursion that we (optionally) update and then pass an updated version. In this case we can use a 2-tuple that contains the smallest, and one-but-smallest element. So now we implement another function

secondSmallest' :: Ord a => (a, a) -> [a] -> a secondSmallest' (s1, s2) ... 

where s1 <= s2 always holds. Now there are some cases we need to consider:

  1. the list is empty, in that case we reached the end of the list, and thus can return s2, the thus far obtained second minimum

    secondSmallest' (_, s2) [] = s2 
  2. the list is not empty, and the head x is greater than or equal to s2, in that case the thus far two smallest elements remain the same, so we can pass the 2-tuple unchanged and we recurse on the tail of the list.

    secondSmallest' s@(s1, s2) (x:xs) | x >= s2 = secondSmallest' s xs 
  3. in case the head x is greater than or equal to s1, but less than s2, then we know that this is the newest second smallest, so in that case we construct a new 2-tuple with (s1, x) and recurse on the tail of the list

                                      | x >= s1 = secondSmallest' (s1, x) xs 
  4. in case the head x is less than s1, then we obtained a new smallest element. In that case s1 is the newest smallest element:

                                      | otherwise = secondSmallest' (x, s1) xs 

So now we implemented a function that - given we already have two thus far smallest elements - can return the second smallest element:

secondSmallest' :: Ord a => (a, a) -> [a] -> a secondSmallest' (_, s2) [] = s2 secondSmallest' s@(s1, s2) (x:xs) | x >= s2 = secondSmallest' s xs                                   | x >= s1 = secondSmallest' (s1, x) xs                                   | otherwise = secondSmallest' (x, s1) xs 

But now we still have not solved the main problem, how do we obtain the first 2-smallest elements. Basically there are three cases here:

  1. in case the list contains at least two elements, and the first element is less than or equal to the second element, we take the first element as the smallest and the second as the second smallest element, and perform a call on the rest of the list and we wrap the result in a Just constructor:

    secondSmallest (x1:x2:xs) | x1 <= x2 = Just (secondSmallest' (x1, x2) xs) 
  2. in case the list contains at least two elements but the first element is greater than the second, then we take the first element as the second smallest, and the second element as the smallest, we again perform a call to the secondSmallest' function, and wrap the result in a Just constructor:

                              | otherwise = Just (secondSmallest' (x2, x1) xs) 
  3. in case the list contains less items, we can not calculate the second smallest, since there is no second smallest, so we return Nothing:

    secondSmallest _ = Nothing 

so in full we get:

secondSmallest :: Ord a => [a] -> Maybe a secondSmallest (x1:x2:xs) | x1 <= x2 = Just (secondSmallest' (x1, x2) xs)                           | otherwise = Just (secondSmallest' (x2, x1) xs) secondSmallest _ = Nothing  secondSmallest' :: Ord a => (a, a) -> [a] -> a secondSmallest' (_, s2) [] = s2 secondSmallest' s@(s1, s2) (x:xs) | x >= s2 = secondSmallest' s xs                                   | x >= s1 = secondSmallest' (s1, x) xs                                   | otherwise = secondSmallest' (x, s1) xs 

Note that secondSmallest' is in fact a fold pattern, so we can write it like:

secondSmallest :: Ord a => [a] -> Maybe a secondSmallest (x1:x2:xs) | x1 <= x2 = Just (secondSmallest' (x1, x2) xs)                           | otherwise = Just (secondSmallest' (x2, x1) xs) secondSmallest _ = Nothing  secondSmallest' :: Ord a => (a, a) -> [a] -> [a] secondSmallest' t = snd . foldr f t     where f s@(s1, s2) x | x >= s2 = s                          | x >= s1 = (s1, x)                          | otherwise = (x, s1) 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: