Haskell中如何对元组列表使用groupBy按元组第二个元素分组

针对你的需求，根据输入列表的有序性不同，有两种高效的标准实现，都依赖Haskell base库自带的函数，不需要额外安装第三方包。

输入已按第二个元素排序（你的示例属于这种情况） #

如果同分组键的元素已经在列表里连续排列，直接用Data.List.groupBy做线性扫描即可，时间复杂度O(n)，是最优效率：

import Data.List (groupBy)
import Data.Function (on)

groupSnd :: Eq b => [(a, b)] -> [[(a, b)]]
groupSnd = groupBy ((==) `on` snd)

调用groupSnd [(3,2),(17,2),(50,3),(64,3)]就能直接得到你期望的输出结果。
这里on函数的作用是把相等判断的逻辑作用到两个元组的第二个元素上：即两个元组只要snd返回值相等，就判定为同组。

输入未按第二个元素排序 #

如果输入中同键元素是分散的（比如[(3,2), (50,3), (17,2)]），直接用groupBy会得到错误结果，此时先按分组键做排序再分组即可，时间复杂度O(n log n)，是通用场景下的高效实现：

import Data.List (groupBy, sortOn)
import Data.Function (on)

groupSndUnsorted :: Ord b => [(a, b)] -> [[(a, b)]]
groupSndUnsorted = groupBy ((==) `on` snd) . sortOn snd

sortOn snd会先把所有元组按第二个元素升序排列，保证同键元素连续，后续分组逻辑和上面完全一致。

补充：无顺序要求的分组场景 #

如果你不需要保留分组的原有顺序，也可以用Data.Map.Strict做聚合插入，时间复杂度同样是O(n log n)，适合分组键没有天然排序关系的场景：

import qualified Data.Map.Strict as M

groupSndMap :: Ord b => [(a, b)] -> [[(a, b)]]
groupSndMap = M.elems . foldr (\pair m -> M.insertWith (++) (snd pair) [pair] m) M.empty

内容的提问来源于stack exchange，提问作者Elfi