Haskell，找到具有最小第二个元素的tupel，如果存在具有两个相同值的第二个元素的tupel，则用第一个元素排序
示例： 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)
任何帮助表示赞赏。
回答
我建议只实现比较功能，然后使用 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)
回答
Haskell 已经有一个Ord元素对的Ord实例，每个元素都有实例，但是对的实例在第二个元素之前比较第一个元素。已经发布的一种解决方案是使用minimumBy并提供您自己的比较函数，但另一种是swap自由使用：
import Data.Tuple (swap)
myMin :: (Ord a, Ord b) => [(a, b)] -> (a, b)
myMin = swap . minimum . fmap swap
如果您非常关心性能，您可能会担心我们会遍历列表两次。解决这个问题的一种方法是使用coerce类型安全的强制转换而不是fmaping 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。）
- I think your first solution implements the function asked for, but the refinements using Down are all incorrect because they still look at the first element first, not the second.
THE END
二维码