有条件地合并列表元素
问题描述:
我仍然是haskell的新手,但我努力学习它。但是现在我明白了,我认为我必须学习haskell的全新章节。有条件地合并列表元素
所以这是一个包含这些数字Int的列表的列表:
[[5,6,14],[1,2,9],[11,12,13],[6,13,14],[5,13,14]]
在开始的时候所有内部列表包含三个数字。目标是将所有重叠列表合并为更大的列表:
[[5,6,14],[1,2,9],[11,12,13],[6,13,14],[5,13,14]]
merging elements at index 0 and 3 because of the common 6 in both lists.
[[5,6,14,13],[1,2,9],[11,12,13],[5,13,14]]
merging elements at index 0 and 2 because of the common 13 in both lists.
[[5,6,14,13,11,12],[1,2,9],[5,13,14]]
merging elements at index 0 and 2 because of the common 5,13 & 14 in both lists.
[[5,6,14,13,11,12],[1,2,9]]
而这应该是函数的结果。列表内部列表的顺序与最内部列表中元素的顺序无关。
我知道如何在任何其他命令式语言中对其进行编码,但在这里我卡住了。
答
使用List
数据结构来做到这一点的一种方法如下。最初写的谓词功能找出如果两个列表中有它们之间没有任何共同的要素:
hasCommon :: Eq a => [a] -> [a] -> Bool
hasCommon xs ys = not . null $ intersect xs ys
λ> hasCommon [1,2,3] [3]
True
λ> hasCommon [1,2,3] [4]
False
现在,你可以实现一个solve
功能,这将给你你想要的功能:
solve :: Eq a => [[a]] -> [[a]]
solve xs = case xs' of
[] -> []
x'@(x:[]) -> x'
x'@(x1:x2:[]) -> x'
x'@(x1:x2:xs) -> x1:(solve (x2:xs))
where xs' = aux (head xs) (tail xs) []
aux :: Eq a => [a] -> [[a]] -> [[a]] -> [[a]]
aux acc [] temp = (acc:temp)
aux acc (y:ys) temp = if (acc `hasCommon` y)
then aux (union acc y) (ys ++ temp) []
else aux acc ys (y:temp)
主要部分功能是aux
。该函数接受三个参数。该函数的第一个参数是输入列表的首字母,用于将其与输入列表的其余部分进行比较。 aux
函数的第二个参数是输入列表的tail
。第三个参数是临时变量,用于跟踪已经处理的元素。您可以在函数中处理两种情况:如果输入列表的尾部为空,则返回[acc] ++ temp
,这将保留您的结果。这将在现在将要描述的另一种情况下建立起来。在另一种情况下,您检查输入列表的头部是否与输入列表尾部的头部有任何共同元素。如果它有任何共同的元素,那么看看我如何将值传递给aux
函数。基本上我用ys ++ temp
填充第二个输入,以便我们遍历已遍历的元素。第一个参数是xs
和y
的联合。在这种情况下的其他部分是不言自明的。
演示在ghci
:
λ> solve [[5,6,14],[1,2,9],[11,12,13],[6,13,14],[5,13,14]]
[[5,6,14,13,11,12],[1,2,9]]
λ> solve [[5,6,14],[18,19,20],[5,13,14],[1,2,9],[17,18,19],[20,21,22]]
[[5,6,14,13],[18,19,20,21,22,17],[1,2,9]]
不在于它回答你的问题,但你应该知道,Haskell的列表('[A]')是*不*阵列,而是链表,而这些的当然具有与阵列完全不同的性能特征。如果你真的想要数组(可能不是这种情况下),请查看[vector](https://hackage.haskell.org/package/vector),这几乎是目前阵列的典型选择。 – gspr
你似乎也会做很多会员测试。也许你想考虑['Set'](http://hackage.haskell.org/package/containers-0.5.6.3/docs/Data-Set.html),这种检查可以在对数时间完成。 – gspr
下面是一个草图:1)编写一个函数,如果它们有交集,则合并两个集合。 2)编写一个函数,从两个列表中产生所有元素对的列表。 3)将函数从1传递到2,直到它找到一对可以完成它的事情。如果你在没有做任何事情的情况下遍历2的所有列表,你就完成了。 – gspr