Haskell，找到具有最小第二个元素的元组，如果存在具有两个相同第二个值的元组，则使用第一个元素进行排序

Question

示例：mymin1 [(3,7),(7,6),(6,6),(5,6)]应返回(5,6)

这是我的代码：

mymin1 [(x,y)]=(x,y)
mymin1 ((x,y):(x1,y1):xs)
|y>y1 = mymin1 ((x1,y1):xs)
|y<=y1 =mymin1 ((x,y):xs)
|y==y1 = if x>x1 then mymin1((x1,y1):xs) else mymin1((x,y):xs)

返回(7,6)

任何帮助都将不胜感激。

Answer 1

我建议只实现比较函数，然后使用Data.List.minimumBy。使用Data.Ord.comparing和Data.Tuple.swap.可以很容易地实现比较函数

myMin :: (Ord a, Ord b) => [(a, b)] -> (a, b)
myMin = minimumBy (comparing swap)

由于DDub的回答谈到了性能问题，但实际上没有计时，所以我编写了一个基准套件来比较这三种方法(我的方法和DDub回答中的两种方法(。我还添加了另一个使用minimumBy的版本，但手动构建了一个自定义比较器，以防comparing swap:中有开销

{-# LANGUAGE TypeApplications #-}
module Main where
import Criterion.Main
import Data.Coerce (coerce)
import Data.List (minimumBy)
import Data.Ord (comparing)
import Data.Tuple (swap)
newtype Swap a b = Swap { getSwap :: (a,b) } deriving Eq
instance (Ord a, Ord b) => Ord (Swap a b) where
compare (Swap (a, b)) (Swap (c, d)) = compare (b,a) (d,c)
fmapMin, coerceMin, comparingMin, primitiveMin :: (Ord a, Ord b) => [(a, b)] -> (a, b)
fmapMin = swap . minimum . fmap swap
coerceMin = getSwap . minimum @[] . coerce
comparingMin = minimumBy (comparing swap)
primitiveMin = minimumBy cmp
where cmp (a, x) (b, y) = case compare x y of
EQ -> compare a b
result -> result
input :: [(Int, Int)]
input = [(abs $ 25 - x, abs $ x - 25) | x <- [0..50]]
main :: IO ()
main = defaultMain $ [env (pure input) (xs ->
bgroup "min"
[ bench "fmap" $ nf fmapMin xs
, bench "coerce" $ nf coerceMin xs
, bench "comparing" $ nf comparingMin xs
, bench "primitive" $ nf primitiveMin xs
])
]

我在评论中猜测，DDub的两个答案可能表现相似，但事实上DDub是对的：使用胁迫的解决方案要好得多。coerce解决方案和我的两个minimumBy解决方案的性能基本上无法区分。结果如下：

benchmarking min/fmap
time                 580.6 ns   (577.9 ns .. 583.3 ns)
1.000 R²   (1.000 R² .. 1.000 R²)
mean                 580.9 ns   (579.1 ns .. 584.2 ns)
std dev              8.058 ns   (5.348 ns .. 12.76 ns)
variance introduced by outliers: 13% (moderately inflated)
benchmarking min/coerce
time                 195.9 ns   (195.0 ns .. 196.7 ns)
1.000 R²   (1.000 R² .. 1.000 R²)
mean                 196.1 ns   (195.2 ns .. 197.9 ns)
std dev              4.159 ns   (2.337 ns .. 7.982 ns)
variance introduced by outliers: 29% (moderately inflated)
benchmarking min/comparing
time                 193.5 ns   (193.2 ns .. 194.0 ns)
1.000 R²   (1.000 R² .. 1.000 R²)
mean                 193.9 ns   (193.4 ns .. 195.1 ns)
std dev              2.529 ns   (1.302 ns .. 4.541 ns)
variance introduced by outliers: 13% (moderately inflated)
benchmarking min/primitive
time                 194.1 ns   (193.5 ns .. 194.8 ns)
1.000 R²   (1.000 R² .. 1.000 R²)
mean                 194.5 ns   (193.8 ns .. 196.2 ns)
std dev              3.447 ns   (1.640 ns .. 6.429 ns)
variance introduced by outliers: 22% (moderately inflated)

Answer 2

Haskell已经为每个都有Ord实例的元素对提供了一个Ord实例，但对的实例会比较第一个元素和第二个元素。已经发布的一个解决方案是使用minimumBy并提供自己的比较功能，但另一个是自由使用swap：

import Data.Tuple (swap)
myMin :: (Ord a, Ord b) => [(a, b)] -> (a, b)
myMin = swap . minimum . fmap swap

---

如果您非常关心性能，您可能会担心我们会遍历列表两次。解决此问题的一种方法是使用coerce执行类型安全强制，而不是使用fmap或swap，但这意味着我们需要一个可强制为(a,b)的数据类型。如果你正在做很多这样的比较，你可以考虑创建：

newtype Swap a b = Swap { getSwap :: (a,b) }
deriving(Eq)
instance (Ord a, Ord b) => Ord (Swap a b) where
compare (Swap (a, b)) (Swap (c, d)) = compare (b,a) (d,c)

这样，您就可以将myMin写为：

{-# LANGUAGE TypeApplications #-}
import Data.Coerce (coerce)
myMin :: (Ord a, Ord b) => [(a, b)] -> (a, b)
myMin = getSwap . minimum @[] . coerce

(注意，由于minimum在容器类型上是多态的，并且我们使用的是coerce，因此我们需要告诉GHC我们使用的容器类型。因此，我们在minimum之后使用类型应用程序@[]。(