Haskell

Question

我有一个元组列表，我想按第二个元素（降序）排序，然后按第一个元素（升序）排序。

我的代码如下所示：

sortedOcc :: Eq a => [a] -> [(a, Int)]
sortedOcc = sortBy (flip compare `on` snd) . occurences

这是按 occurences（函数）返回的列表的第二个元素进行的第一次排序。我应该如何添加第一个元素的第二个排序（升序）？

Answer 1

sortBy 的签名是什么？

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

这意味着它的第一个参数必须具有类型 a -> a -> Ordering:

sortedOcc :: Eq a => [a] -> [(a, Int)]
sortedOcc = sortBy g . occurences

g :: a -> a -> Ordering
g = (flip compare `on` snd)

但这意味着

g :: a -> a -> Ordering
g x y = (flip compare `on` snd) x y
      = flip compare (snd x) (snd y)
      = compare (snd y) (snd x)

所以要将您的要求添加到组合中，我们只需将其写下来，

      = let test1 = compare (snd y) (snd x)
            test2 = compare (snd y) (snd x)
        in ......

对吗？

以上故意包含错误，您应该很容易修复。

_{忠告，只使用point-free代码，如果您阅读和书写容易自然，并且修改。}

Answer 2

我可能会在 Ordering 和函数类型上使用来写这个。

正如您已经确定的那样，按元组中的第二个值排序看起来像 flip compare `on` snd，而按第一个值排序看起来像 compare `on` fst。这些可以与 <>.

单向组合

d :: [(String , Int)]
d = [("b", 1), ("a", 1), ("c",3), ("d",4)] 

sortedD = sortBy ((flip compare `on` snd) <> (compare `on` fst)) d

Answer 3

Data.Ord 模块提供了一个 Down 新类型，其目的只是为了颠倒顺序。

它还提供了一个comparing function:

comparing :: Ord a => (b -> a) -> b -> b -> Ordering

必须先输入一些转换函数，然后才能传递给sortBy。

像这样：

$ ghci
 GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> sortBy  (comparing (\(a,v) -> (Down v, a)))   [(1,2),(1,3),(5,2),(5,3)]
 [(1,3),(5,3),(1,2),(5,2)]
 λ>

转换函数返回的值然后使用它们自己的“自然”顺序进行排序。在我们的例子中，这是有序类型对上的 lexicographic order。

总体而言，代码需要 Ord a 约束：

sortedOcc :: Ord a => [a] -> [(a, Int)]
sortedOcc = sortBy (comparing (\(a,v) -> (Down v, a)))  .  occurences

Answer 4

我知道其余的答案更短，但我建议您在使用已经 Haskell 实现的那些之前自己实现这些惰性函数，这样您就可以了解它是如何工作的。

-- Order a list of tuples by the first item
orderBy1stTupleItem :: Ord a => (a, b1) -> (a, b2) -> Ordering
orderBy1stTupleItem tup1 tup2
  | item1 > item2 = GT
  | item1 < item2 = LT
  | otherwise = EQ
  where
      item1 = fst tup1
      item2 = fst tup2

-- Order a list of tuples by the second item
orderBy2ndTupleItem :: Ord a1 => (a2, a1) -> (a3, a1) -> Ordering
orderBy2ndTupleItem tup1 tup2
  | item1 > item2 = GT
  | item1 < item2 = LT
  | otherwise = EQ
  where
      item1 = snd tup1
      item2 = snd tup2

-- Wrapper Function: Order a list of tuples by the first item and later by the second item
orderTuplesBy1stThenBy2ndItem :: (Ord a1, Ord a2) => [(a2, a1)] -> [(a2, a1)]
orderTuplesBy1stThenBy2ndItem listTuples = 
    sortBy orderBy2ndTupleItem (sortBy orderBy1stTupleItem listTuples)

例子

let exampleListTuples = [(1,2),(0,8),(6,1),(3,6),(9,1),(7,8),(0,9)]

然后让我们得到第一个列表，按每个元组的第一项排序：

> listOrderedByTuple1stItem = sortBy orderBy1stTupleItem exampleListTuples
> listOrderedByTuple1stItem
[(0,8),(0,9),(1,2),(3,6),(6,1),(7,8),(9,1)]

现在我们按每个元组的第二项对结果列表进行排序

> sortBy orderBy2ndTupleItem listOrderedByTuple1stItem
[(6,1),(9,1),(1,2),(3,6),(0,8),(7,8),(0,9)]

或者，您可以运行包装函数 orderTuplesBy1stThenBy2ndItem 如下：

> sortBy orderTuplesBy1stThenBy2ndItem exampleListTuples

Haskell - 按第一个第二个元素排序，然后按第一个元素排序

Haskell - Sort by first second element and then by first element

sorting