отфильтрованный список декартовых продуктов без промежуточного списка

Question

Я пытаюсь создать отфильтрованное декартово произведение из определенного списка списков. Наивное решение заключается в следующем:

import Data.Traversable (sequence) 

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

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

Проходит достаточно мощный, чтобы сделать это без создания промежуточного списка? Есть ли идиоматический способ сделать это?

Answer 1

traverse здесь кодирует рисунок, который predicate имеет форму all foo для некоторых foo. Затем filteredCartesianProduct - traverse (filter foo).

Если predicate говорит да для каждого префикса любого списка, на котором он говорит, что да, у вас есть шаблон с возвратами:

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

Интересно, как избавиться от запаха ++ [_].