Haskell列表中的第二个最小值

Question

我正在尝试编写一个secondSmallest返回列表中第二个最小值的函数,如果没有这样的值,则返回Nothing.此外,如果列表的最小值出现多次,则它也是第二小的值.例如:

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

这是我到目前为止所拥有的:

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)

Answer 1

运用 sort

懒惰的方法是使用sort :: Ord a => [a] -> [a].sort返回一个排序列表,但是以一种懒惰的方式,并获得第k个元素,其中O(n)表示固定元素,如果我们枚举最多k个元素,则需要O(n log k) ),我们可以在sort结果上执行模式匹配,然后返回第二个元素,如:

import Data.List(sort)

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

通过使用累加器

另一种方法是使用累加器.累加器是递归中的参数,我们(可选)更新然后传递更新的版本.在这种情况下,我们可以使用包含最小和一个但最小元素的2元组.所以现在我们实现另一个功能

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

s1 <= s2总是在哪里.现在我们需要考虑一些情况:

1. 列表是空的,在这种情况下我们到达列表的末尾,因此可以返回s2到目前为止获得的第二个最小值

   secondSmallest' (_, s2) [] = s2
   

2. 列表不是空的,并且头部x大于或等于s2,在这种情况下,迄今为止最小的两个最小元素保持不变,因此我们可以将2元组保持不变,并且我们递归到列表的尾部.

   secondSmallest' s@(s1, s2) (x:xs) | x >= s2 = secondSmallest' s xs
   

3. 如果头部x大于或等于s1但小于s2,那么我们知道这是最新的第二小,所以在这种情况下我们构造一个新的2元组,(s1, x)并在列表的尾部递归

                                     | x >= s1 = secondSmallest' (s1, x) xs
   

4. 如果头部x小于s1,则我们获得一个新的最小元素.在这种情况下s1是最新的最小元素:

                                     | otherwise = secondSmallest' (x, s1) xs
   

所以,现在我们实现了一个功能-鉴于我们已经有两个这样迄今最小的元素-可以返回第二个最小的元素:

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

但是现在我们仍然没有解决主要问题,我们如何获得前2个最小的元素.基本上这里有三种情况:

1. 如果列表包含至少两个元素,并且第一个元素小于或等于第二个元素,我们将第一个元素作为最小元素,将第二个元素作为第二个最小元素,并对其余的元素执行调用. list,我们将结果包装在Just构造函数中:

   secondSmallest (x1:x2:xs) | x1 <= x2 = Just (secondSmallest' (x1, x2) xs)
   

2. 如果列表包含至少两个元素但第一个元素大于第二个元素,那么我们将第一个元素作为第二个元素,将第二个元素作为最小元素,我们再次执行对secondSmallest'函数的调用,并将其包装导致Just构造函数:

                             | otherwise = Just (secondSmallest' (x2, x1) xs)
   

3. 如果列表包含较少的项目,我们无法计算第二个最小值,因为没有第二个最小值,所以我们返回Nothing:

   secondSmallest _ = Nothing
   

所以我们得到:

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

注意,这secondSmallest'实际上是一个fold模式,所以我们可以这样写:

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)