3

所以我一直在练习 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"])]
4

3 回答 3

1

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

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")]
于 2013-10-24T23:13:21.213 回答
1

您可以使用右折叠Data.Map.insertWith：

import Data.Map as M hiding (foldr)

main :: IO ()
main = print . M.toList
             $ foldr (\(k, v) m -> M.insertWith (++) k [v] m)
                     M.empty
                     [("a","b"),("a","c"),("b","e")]

输出：

./main
[("a",["b","c"]),("b",["e"])]
于 2013-10-24T23:19:22.167 回答
1

基本原则是您希望将“相似”元素组合在一起。

每当您想将元素组合在一起时，您都可以group使用Data.List. 在这种情况下，您希望自己指定什么是相似的，因此您需要使用该groupBy版本。中的大多数函数Data.List都有一个By-version 版本，可让您更详细地指定所需内容。

第1步

在您的情况下，您希望将“相似性”定义为“具有相同的第一个元素”。在 Haskell 中，“在一对上具有相同的第一个元素”意味着

(==) `on` fst

换句话说，一对的第一个元素相等。

因此，为了进行分组，我们将该要求提供给groupBy，如下所示：

groupBy ((==) `on` fst) xs

在您的示例中，这将使我们回到两组：

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

第2步

现在剩下的就是将这些列表变成对。这背后的基本原则是，如果我们让

ys = [("a","b"),("a","c")]

例如，取第一对的第一个元素，然后将所有对的第二个元素一起粉碎成一个列表。取第一对的第一个元素很容易！

fst (head ys) == "a"

获取所有第二个元素也相当容易！

map snd ys == ["b", "c"]

这两个操作一起给了我们想要的东西。

(fst (head ys), map snd ys) == ("a", ["b", "c"])

完成的产品

所以如果你愿意，你可以把你的聚集函数写成

clump xs = (fst (head ys), map snd ys)
  where ys = groupBy ((==) `on` fst) xs
于 2013-10-25T04:59:48.867 回答