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

Question

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

我的代码是这样的:

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

，这是occurences(函数)返回的列表的第二个元素的第一次排序。我应该如何在第一个元素上加上第二个排序(升序)?

Answer 1

Data.Ord模块提供了一个Downnewtype，其目的仅仅是反转排序。

还提供了一个comparing函数:

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)]
λ> 

转换函数返回的值然后使用它们自己的"自然"顺序排序。在本例中，这是有序类型对的字典顺序。

总的来说，代码需要Ord a约束:

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

Answer 2

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

对元组中的第二个值排序看起来像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

我知道其余的答案更短，但我建议您在使用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

Answer 4

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 ......

对吧?

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

_{一个建议，只使用对您来说容易和自然的阅读和编写的无点代码，并且修改。}