Haskell.按元组列表中的第二个元素排序

Question

我有一个代码histogram，它显示了字符串中所有字符的数量。

histogram :: String -> [(Char, Int)]
histogram = foldr help [] where
help x [] = [(x,1)] 
help x ((y,z):yzs)
| x == y = (y,z+1) : yzs 
| otherwise = (y,z) : help x yzs

但结果显示在一个混乱的顺序。我想按列表的第二个元素(即按数字)对结果进行排序。为此，我实现了ssort代码，但它只按第一个元素(char)排序。

import Data.List (minimum, delete)
ssort :: Ord t => [t] -> [t]
ssort [] = []
ssort xs = x : ssort (remove x xs) where
x = minimum xs
remove :: Eq a => a -> [a] -> [a]
remove _ [] = [] 
remove y (x:xs) | y == x = xs 
| otherwise = x : remove y xs

输入:Ssort [('a'，1)， ('g'， 6)， ('o'，2)， ('f'，0)]

输出:[(' a ', 1), (f, 0)、("g",6),(' o ', 2)](而不是[(f, 0)、(' a ', 1), (' o ', 2),("g",6)])

我也不想使用任何其他内置函数，如sort, sortOn和sortBy，我想实现我自己的函数。

如何使它只比较第二个元素?

Answer 1

您可以提供您自己的minimumBy定义:

minimumBy2 :: Ord t2 => [(t1, t2)] -> (t1, t2)
minimumBy2 (h:t) = go h t where
go x [] = x
go x (h0:t0) = go (min x h0) t0
minimumBy2 [] = error "minimumBy2: Empty list"

你可以用它来代替ssort中的minimum，它应该可以工作。

Answer 2

假设您也不想使用minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a。

可以利用元组的比较方式——先比较第一个元素，然后比较第二个元素。因此，你可以先交换直方图中的所有元素，然后排序，最后交换回来:

ssortOn2 :: (Ord t1, Ord t2) => [(t1, t2)] -> [(t1, t2)]
ssortOn2 = map swap . ssort . map swap 

(其他函数保持不变)