时间戳

首页 > 解决方案 > 按值 (a, b) 的差异对 Int 对列表进行排序

haskell - 按值 (a, b) 的差异对 Int 对列表进行排序

问题描述

如何按升序list对Int值的差异进行排序？|first - second|

为了计算差异，我编写了这段代码：

ab :: (Int, Int) -> Int
ab (x, y) = if x - y >= 0 then (x - y)
            else (x - y) * (-1)

我想使用quicksort我得到的值：

sort :: [(Int,Int)] -> [(Int,Int)]
sort [] = []
sort (x:xs) = sort smallerOrEqual ++ [x] ++ sort larger
          where smallerOrEqual = [a | a <- xs, a <= x]
                larger = [a | a <- xs, a > x]

问题是如何将我的ab函数构建到the排序函数中？我尝试了几种方法，但总是遇到编译器错误。

标签： haskelltupleslist-comprehensionquicksort

解决方案

让我们只使用标准库函数来做到这一点！

首先，有一个通用版本的排序函数，命名为sortBy（我将使用 GHCi 的精彩:t命令展示相关函数的类型）：

ghci> import Data.List
ghci> :t sortBy
sortBy :: (a -> a -> Ordering) -> [a] -> [a]

的第一个参数sortBy表明，要比较元素，我们需要一个排序谓词——一个函数，它接受列表的两个元素并判断第一个元素是否更大。在许多情况下，包括您在内，您不必自己定义这样的函数。相反，您可以使用“<em>衡量”列表元素的重要性的函数。例如，你有一个列表元素，(x,y)它的度量是|x-y|——这正是你的ab函数，但请记住，我们希望它通过标准函数来定义。

目前，我们有两个任务：1）定义类型的度量函数(Int, Int) -> Int；2）学习如何把它变成一个排序谓词。我告诉过后者是微不足道的，因为它可以通过标准函数来完成comparing：

ghci> import Data.Ord
ghci> :t comparing
comparing :: Ord a => (b -> a) -> b -> b -> Ordering

所以我的建议是，comparing ab它与 的第一个参数完美匹配sortBy。不让我们转向另一个任务：ab通过标准函数进行定义。

考虑-函数的类型：

ghci> :t (-)
(-) :: Num a => a -> a -> a

如果你用Int( a¹) 代替你几乎得到你想要的类型，即Int -> Int -> Int. 在这里，我们遇到了将一个函数从两个参数 ( (-)) 转换为作用于对的函数的非常频繁的任务。幸运的是，有一个标准函数可以做到这一点，即uncurry：

ghci> :t uncurry (-)
uncurry (-) :: Num c => (c, c) -> c

这就是我们需要的！现在我们只需要使用abs计算函数来管道它|·|，我们很好。我们将函数组合成.. 结果解决方案是这个：

import Data.List (sortBy)
import Data.Ord  (comparing)

sortAbsPairs :: [(Int,Int)] -> [(Int,Int)]
sortAbsPairs = sortBy (comparing $ abs . uncurry (-))

假设您将其保存在 GHCi 中，您可以尝试一下sort.hs：

ghci>:l sort.hs
Ok, one module loaded.
ghci> sortAbsPairs [(8,20), (5, 10), (1,2)]
    [(1, 2), (5, 10), (8, 20)]

(¹) 您实际上可以通过设置一个名为的语言扩展来要求 GHCi 用类型替换函数的类型参数TypeApplications：

ghci> :set -XTypeApplications
ghci> :t (-) @Int
(-) @Int :: Int -> Int -> Int

推荐阅读