# 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) ``