CODEWITHSUNDEEP
haskell
Shifter
Shifter

Reputation: 11

Return the second-smallest value from a list

min2 :: Ord a => [a] -> a
min2 x =  if g  == minimum x then minimum x else g
  where
    g = minimum(filter (> minimum x) x)

this only works for list where there is only one minimum value; so min2 [2110, 4820, 2110, 4120] != 2110, it counts 2110 as a single element not 2

The code is all I have right now, how can I account for the repeated element

Upvotes: 1

Views: 303

Answers (2)

Stefan Holdermans
Stefan Holdermans

Reputation: 8050

First sort the list and then select the second element of the resulting intermediate list (if any):

import Data.List (sort)

min2 :: Ord a => [a] -> a
min2 xs = case sort xs of
  []           -> error "min2: empty list"
  [x]          -> error "min2: singleton list"
  (x : y : xs) -> y

> min2 [2110, 4820, 2110, 4120]
2110

Or, if you want a more obvious linear-time solution, you could simply traverse the input list and maintain an accumulating parameter that stores the two smallest values encountered so far:

data Acc a = Empty | Singleton a | Min2 a a

min2' :: Ord a => [a] -> a
min2' = fromAcc . foldl go Empty
  where
    go Empty x         = Singleton x
    go (Singleton y) x
      | x < y          = Min2 x y
      | otherwise      = Min2 y x
    go (Min2 y z) x
      | x < y          = Min2 x y
      | x < z          = Min2 y x
      | otherwise      = Min2 y z

    fromAcc Empty         = error "min2': empty list"
    fromAcc (Singleton x) = error "min2': singleton list"
    fromAcc (Min2 x y)    = y

> min2' [2110, 4820, 2110, 4120]
2110

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476544

You can sort the list of items, and then pick the second item. For example:

import Data.List(sort)

min2 :: Ord a => [a] -> Maybe a
min2 xs
    | (_:x:_) <- sort xs = Just x
    | otherwise = Nothing

The sort function is implemented as a lazy mergesort where it first [src] with some extra optimizations. That means if you for example obtain the k-th element, it will run in *O(*k×log n+n) time, so for the second item, it will run in O(n).

Upvotes: 0

Related Questions