list - 如何比较haskell列表中的内容，看看它们是否部分相同？

Question

这对我来说非常棘手。

给定一个很长的列表，

[[100,11,1,0,40,1],[100,12,3,1,22,23],[101,11,1,0,45,1],[101,12,3,1,28,30],[102,11,1,0,50,1],[102,12,3,1,50,50],[103,11,1,0,50,1],[103,12,3,1,50,50],[104,11,1,0,50,25],[104,12,3,1,50,50],[105,11,1,0,50,49],[105,12,3,0,30,30],[106,11,1,0,50,49],[106,12,3,0,25,26],[107,11,1,1,33,20],[107,12,3,0,25,26],[108,11,1,1,2,1],[108,12,3,1,20,24],[109,11,1,1,2,1],[109,12,3,1,28,31],[110,11,1,0,40,1],[110,12,3,1,22,23]..]

现在忽略每个列表的第一个数字，例如，如果两个列表尽管第一个数字相同，但仍然相同

[101,11,1,0,50,1] alike [102,11,1,0,50,1]

我们保留后一个列表，直到整个列表全部检查完毕。理想情况下，结果应该是这样的:

[[102,11,1,0,50,1],[103,12,3,1,50,50]..]

我的想法是用map去掉第一个数字，用nub和\\去掉所有重复的结果，把它变成like

[[11,1,0,50,1],[12,3,1,50,50],[12,3,1,50,50],[11,1,0,50,49],[12,3,0,25,26],[11,1,1,2,1],[11,1,0,40,1],[12,3,1,22,23],[11,1,0,45,1],[12,3,1,28,30]..]

并使用Set.isSubsetOf过滤掉原始列表。

但是，这个想法过于复杂且难以实现。由于我是 Haskell 的初学者，有没有更好的方法来排序？或者我可以使用递归函数来代替(但仍然需要努力)？

Answer 1

根据您的描述，我认为您想要获取最后列表的列表以拥有每个独特的尾部。你可以这样做:

lastUniqueByTail :: Eq a => [[a]] -> [[a]] 
lastUniqueByTail = reverse . nubBy ((==) `on` tail) . reverse

注意这只适用于非空列表的有限列表

在Data.Function模块中可以找到on，在Data.List中可以找到nubBy >.

这里是每个部分的解释，我们将从内到外进行工作:

• ((==) `on` tail) 此函数在两个列表之间执行比较，如果它们的尾部相等，则确定它们相等(即，它执行相等性检查，忽略第一个元素)。

  on 函数在这里发挥了大部分作用。它具有以下类型签名:

  on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
  

  它本质上定义为 (f `on` g) x y = f (g x) (g y)，因此替换我们提供的函数，我们得到 ((==) `on` tail) x y = (tail x) == (tail y).

• 然后，nubBy 与 nub 类似，只不过您可以为其提供一个比较器来测试相等性。我们给它上面定义的函数，以便它丢弃具有相同尾部的元素。

• 但是，与 nub 一样，nubBy 会在它找到的每个等价类中保留第一个元素。 (即，如果它在列表中找到两个相等的元素，它总是选择第一个)。我们想要最后一个这样的元素，这就是为什么我们必须首先反转(以便最后一个相等的元素成为第一个，因此被保留)。
• 最后，我们在最后反转，使顺序恢复到开始时的状态。