haskell 分组问题

group :: Ord a => [(a, [b])] -> [(a, [b])]

我想查找所有具有相同 fst 的对，并合并它们，方法是将所有 bs 列表附加到它们具有相同 a 的地方并丢弃不需要的对等等......

我得到了:

group ((s, ls):(s', ls'):ps) =
    if s == s'
    then group ((s, ls++ls'):ps)
    else (s, ls) : group ((s', ls'):ps)
group p = p

但显然这不会削减它，因为它不会对所有内容进行分组。

编辑:
例子

[("a", as),("c", cs), ("c", cs3), ("b", bs),("c", cs2), ("b", bs2)]

会输出

[("a", as),("c", cs++cs2++cs3),("b", bs++bs2)]

最佳答案

barkmadley's answer 的两种替代解决方案:

正如 Tirpen 在评论中指出的那样，解决这个问题的最佳方法取决于输入列表元组中不同的第一个元素的数量 m。对于 m barkmadley 的小值，使用 Data.List.partition 是可行的方法。然而，对于较大的值，算法的 O(n * m) 复杂度并不是那么好。在这种情况下，O(n log n) 类型的输入可能会更快。因此，

import Data.List (groupBy, sortBy)
combine :: (Ord a) => [(a, [b])] -> [(a, [b])]
combine = map mergeGroup . myGroup . mySort
  where
    mySort = sortBy (\a b -> compare (fst a) (fst b))
    myGroup = groupBy (\a b -> fst a == fst b)
    mergeGroup ((a, b):xs) = (a, b ++ concatMap snd xs)

这会在 barkmadley 的输入上产生 [("Dup",["2","3","1","5"]),("Non",["4"])]。

或者，我们可以调用 Data.Map 的帮助:

import Data.Map (assocs, fromListWith)
combine :: (Ord a) => [(a, [b])] -> [(a, [b])]
combine = assocs . fromListWith (++)

这将产生 [("Dup",["5","1","2","3"]),("Non",["4"])] ，这可能是也可能不是问题。如果是，那么还有两种解决方案:

首先使用 Data.List.reverse 反转输入:

import Data.List (reverse)
import Data.Map (assocs, fromListWith)
combine :: (Ord a) => [(a, [b])] -> [(a, [b])]
combine = assocs . fromListWith (++) . reverse

Prepend ( flip (++) ) 而不是 append ( (++) ) (感谢 barkmadley ；我更喜欢这个解决方案):

import Data.Map (assocs, fromListWith)
combine :: (Ord a) => [(a, [b])] -> [(a, [b])]
combine = assocs . fromListWith (flip (++))

这两个定义都会导致 combine 输出 [("Dup",["2","3","1","5"]),("Non",["4"])] 。
最后，请注意 combine 的所有这些定义都要求输入列表中元组的第一个元素是 Ord 类的实例。 barkmadley 的实现只需要这些元素是 Eq 的实例。因此，存在可以由他的代码处理但不能由我的代码处理的输入。

关于haskell 分组问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1714006/