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

Question

我正在尝试从给定的列表列表中创建过滤的笛卡尔积。天真的解决方案如下：

import Data.Traversable (sequence)

predicate :: [T] -> Bool
predicate = ...

filteredCartesianProduct :: [[T]] -> [[T]]
filteredCartesianProduct = filter predicate . sequence

traversable 是否足够强大，可以在不创建中间列表的情况下完成它？有没有一种惯用的方法来做到这一点？

Answer 1

traverse这里对具有somepredicate形式的模式进行编码。那么，是。all foofoofilteredCartesianProducttraverse (filter foo)

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

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

我想知道如何去除++ [_]气味。