Haskell 生成预过滤排列

Question

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

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），而实际上只有很少的过滤排列。

Answer 1

用 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 来自 this answer.

测试：

> 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] 等

生成输出

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

Haskell 生成预过滤排列

Haskell generating pre-filtered permutations

recursion

haskell

filtering

permutation

recursive-backtracking