Haskell 生成预过滤排列

有没有办法生成预过滤的排列，而不是这样做：

filter condition $ permutations list

排列函数可以短路。例如 ：

perms [] = [[]]
perms xs = [ i:j | i <- xs, j <- perms $ delete i xs]

我尝试了一些明显的事情，例如：

perms xs = [ i:j | i <- xs, j <- filter condition $ perms $ delete i xs]

我以为会发生什么，这会引发一条链条，最终会到达[]然后继续工作，但一路过滤。然而，当给它提供一个很长的列表时，从而加快这个过程。这似乎不会发生，因为当尝试对 20 个项目列表进行排列时，它陷入了困境（ghci），而该列表实际上只有很少的实际过滤排列。

将其编码为do递归表示法非常简单。

foo :: ([a] -> Bool) -> [a] -> [[a]]
foo p xs = bar ([],xs)
   where
   bar (acc,[]) = return acc
   bar (acc,xs) = do
                   (x,ys) <- picks xs      -- shrink the domain (ys)
                   if ( p (x:acc) )        -- test soon
                     then bar (x:acc,ys)   -- loop
                     else mzero            -- fail early

picks [] = []
picks (x : xs) = (x, xs) : [(y, x : ys) | (y, ys) <- picks xs]

picks来自这个答案 https://stackoverflow.com/questions/12869097/splitting-list-into-a-list-of-possible-tuples/12872133#12872133.

Testing:

> foo (const True) [1..3]
[[3,2,1],[2,3,1],[3,1,2],[1,3,2],[2,1,3],[1,2,3]]

> foo (\(x:xs) -> not(null xs) || x > 1) [1..3]
[[3,1,2],[1,3,2],[2,1,3],[1,2,3]]

最后一个也立即开始产生输出[1..20], [1..300] etc.

我相信这可以用更高层次的东西来清楚地表达。