过滤列表没有中间列表的笛卡尔积

Question

我正在尝试从给定的列表列表中创建一个过滤的笛卡尔产品。朴素的解决方案如下：

import Data.Traversable (sequence)
predicate :: [T] -> Bool
predicate = ...
filteredCartesianProduct :: [[T]] -> [[T]]
filteredCartesianProduct = filter predicate . sequence

可遍历是否足够强大，无需创建中间列表即可完成此操作？有没有惯用的方法可以做到这一点？

Answer 1

traverse在这里编码的模式，即predicate具有某些foo all foo的形式。然后，filteredCartesianProduct traverse (filter foo).

如果predicate对任何列表的每个前缀都说"是"，那么你就有了回溯模式：

filteredCartesianProduct = foldlM (accum factor -> [new | x <- factor, let new = accum ++ [x], predicate new]) []

我想知道如何摆脱++ [_]气味。