haskell 分组问题

Question

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)]

Answer 1

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)

这将产生 [("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

前置( flip (++) )而不是附加( (++) )(感谢 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 的实例。 .因此，存在可以由他的代码处理但不能由我的代码处理的输入。