已過濾的列表笛卡爾產品沒有中間列表

我試圖從給定的列表中創建一個已過濾的笛卡爾產品。天真的解決方案如下：已過濾的列表笛卡爾產品沒有中間列表

import Data.Traversable (sequence) 

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

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

是否可以穿越足夠強大的功能來做到這一點，而無需創建中間列表？有沒有一種慣用的方式來做到這一點？

來源

2017-01-29 lanskey

假設您的'predicate'函數的簽名是正確的，那麼'filteredPowerSet'的實現是不正確的。你爲什麼用'sequence'編寫'filter predicate'？這不是檢查。你的實現不應該是'filteredPowerSet = filter predicate'？ – liminalisht

聲明的類型意味着你已經接收（或至少期待）一個powerset，而不是一個集合，作爲參數。 – chepner

我收到一個列表清單，如[[1,2]，[3,4,5]]，序列產生以下內容：[[1,3]，[1,4]，[1,5]， [2,3]，[2,4]，[2,5]。 – lanskey

traverse這裏編碼的模式predicate的形式all foo對於某些foo。然後，filteredCartesianProduct是traverse (filter foo)。

如果predicate說是關於它說，是的，你已經得到了回溯模式的所有列表中的每個前綴：

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

我不知道如何擺脫++ [_]氣味。

來源

2017-01-29 19:39:19 Gurkenglas

已過濾的列表笛卡爾產品沒有中間列表

回答

相關問題