list - 在 Haskell 中加入列表

Question

所以我一直在练习 Haskell，而且我做得很好，直到我被困在这个练习中。基本上我想要一个函数来接收这样的列表:

xs = [("a","b"),("a","c"),("b","e")]

返回这样的东西:

xs = [("a",["b","c"]), ("b",["e"])].

我想出了这段代码:

list xs = [(a,[b])|(a,b) <- xs]

但问题是这不符合我的要求。我想它很接近，但不正确。

这是返回的内容:

xs = [("a",["b"]),("a",["c"]),("b",["e"])] 

Answer 1

如果您不关心最终列表中元组的顺序，最有效的方法(不会重新发明轮子)是使用 Map 类型containers包中的Data.Map:

import Data.Map as Map

clump :: Ord a => [(a,b)] -> [(a, [b])]
clump xs = Map.toList $ Map.fromListWith (flip (++)) [(a, [b]) | (a,b) <- xs]

main = do print $ clump [("a","b"),("a","c"),("b","e")]

如果你确实关心结果顺序，你可能不得不做一些丑陋的事情，并且 O(n^2) 像这样:

import Data.List (nub)

clump' :: Eq a => [(a,b)] -> [(a, [b])]
clump' xs = [(a, [b | (a', b) <- xs, a' == a]) | a <- nub $ map fst xs]

main = do print $ clump' [("a","b"),("a","c"),("b","e")]