 A+
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 kth element, with O(n) for a fixed element, and in case we enumerate up to the kth 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 2tuple that contains the smallest, and onebutsmallest 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:

the list is empty, in that case we reached the end of the list, and thus can return
s2
, the thus far obtained second minimumsecondSmallest' (_, s2) [] = s2

the list is not empty, and the head
x
is greater than or equal tos2
, in that case the thus far two smallest elements remain the same, so we can pass the 2tuple unchanged and we recurse on the tail of the list.secondSmallest' s@(s1, s2) (x:xs)  x >= s2 = secondSmallest' s xs

in case the head
x
is greater than or equal tos1
, but less thans2
, then we know that this is the newest second smallest, so in that case we construct a new 2tuple with(s1, x)
and recurse on the tail of the list x >= s1 = secondSmallest' (s1, x) xs

in case the head
x
is less thans1
, then we obtained a new smallest element. In that cases1
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 2smallest elements. Basically there are three cases here:

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)

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 aJust
constructor: otherwise = Just (secondSmallest' (x2, x1) xs)

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)