如果数字出现在Haskell的同一列表中,则从[[Int]]列表中删除元素

我有这样的事情:

[[1,3,2],[5,6],[3,8],[10,11],[13,6]]

我想过滤掉第三个和最后一个列表,以便它变为:

[[1,3,2],[5,6],[10,11]]

逻辑是删除列表,如果任何数字"出现在"之前(在[3,8]数字3出现在第一个列表中的情况下).

我只能想到非FP方法来做到这一点.我的目标是以"好的方式"学习Haskell.如何才能做到这一点？

这个怎么样:你使用像Data.HashSet这样的累加器,然后使用某种过滤方法,如:

import Data.HashSet
import Data.Hashable

somefilter :: (Hashable a, Ord a) => [[a]] -> [[a]]
somefilter = sf empty

sf :: (Hashable a, Ord a) => Set a -> [[a]] -> [[a]]
sf hs (x:xs) | any (flip member hs) x = tl
             | otherwise = x : tl
             where tl = sf (foldr insert hs x) xs
sf _ [] = []

那么演示:

*Main> somefilter [[1,3,2],[5,6],[3,8],[10,11],[13,6]]
[[1,3,2],[5,6],[10,11]]

您当然可以使用另一个数据结构(列表,树集等)来存储您到目前为止遇到的值.HashSet由于查找和插入时间复杂度低,A 只是一个合理的选择.

编辑

很明显,时间复杂度对于懒惰编程来说并不容易.如果您打算生成整个列表,则可以从文档中Data.IntMap获取时间复杂度.

鉴于元件的总数量为Ñ(不要与数量相混淆列表),并且我们考虑的比特数Int W¯¯固定(32或64),两者都insert和lookup在恒定的时间就完成了.这意味着总时间复杂度为O(N).

对于nubBy解决方案,虽然时间复杂度intersect可能在O(mn)中运行,其中m是一个列表中的项目数,n是另一个列表中的元素数.这是针对所有先前的每个列表完成的.因此,如果存在O(k)列表,则时间复杂度为O(k ² a ²),其具有列表中的平均项目数.由于ak = N,因此时间复杂度约为O(N ²).

编辑2

根据您的评论,您可以重写该功能以满足新规范:

import Data.HashSet
import Data.Hashable

somefilter2 :: (Hashable a, Ord a) => [[a]] -> [[a]]
somefilter2 = sf2 empty

sf2 :: (Hashable a, Ord a) => Set a -> [[a]] -> [[a]]
sf2 hs (x:xs) | any (flip member hs) x = sf2 hs xs
              | otherwise = x : sf2 (foldr insert hs x) xs
sf2 _ [] = []

随着之间的区别somefilter和somefilter2:

*Main> somefilter [[1,3,2],[5,6],[3,8],[10,11],[8],[13,6]]
[[1,3,2],[5,6],[10,11]]
*Main> somefilter2 [[1,3,2],[5,6],[3,8],[10,11],[8],[13,6]]
[[1,3,2],[5,6],[10,11],[8]]

在递归部分只有一个区别sf:现在你只添加元素Set,以防你" 发出 "一个元素.