haskell分组问题

Question

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

我想查找具有相同fst的所有对,并将它们合并,通过将所有bs列表附加在一起,它们具有相同的a并丢弃unnessecary对等等...

我得到了:

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的两个替代解决方案:

• 正如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"])]了barkmadley的输入.

• 或者,我们可以在以下帮助下致电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.因此存在可以由他的代码处理的输入,但不是由我的代码处理.

Answer 2

import Data.List hiding (group)

group :: (Eq a) => [(a, [b])] -> [(a, [b])]
group ((s,l):rest) = (s, l ++ concatMap snd matches) : group nonmatches
    where
        (matches, nonmatches) = partition (\x-> fst x == s) rest
group x = x

这个函数产生结果:

group [("Dup", ["2", "3"]), ("Dup", ["1"]), ("Non", ["4"]), ("Dup", ["5"])]
    = [("Dup", ["2", "3", "1", "5"]), ("Non", ["4"])]

它的工作原理是将剩余的比特过滤成两个阵营,匹配的比特和不匹配的比特.然后它将那些匹配和递归的那些组合在一起.这实际上意味着您将在输入列表中的每个"键"的输出列表中有一个元组.