列表元素的所有可能組合

Question

我需要獲取列表元素的所有可能組合。我嘗試瞭解決方案here但它不能編譯。請幫我想出解決辦法：

subseq :: [a] -> [[a]] 
subseq [] = [] 
subseq (x:xs) = map (x :) $ subseq xs 

基本上這是Data.List的subsequences功能的重寫。雖然我不明白source中的版本。我在上面的函數背後的基本原理是這樣的。

將cons算子應用於所有元素。這應該會產生一個非確定性的結果。但是，我得到的結果是一個空的列表。請幫忙。

Answer 1

讓我們從基礎案例開始。空集的功率集是包含空集的集。所以你需要用subseq [] = [[]]替換subseq [] = []。現在你說的是空集的力量是空的，事實並非如此。

你的其他案例也缺少一些東西。您需要將其更改爲subseq (x:xs) = (subseq xs) ++ map (x :) (subseq xs)。用簡單的英語，這意味着你採取不包含第一項的子集（subseq xs）和包含它的子集（map (x :) (subseq xs)）。

如果你省略了(subseq xs)部分，你所得到的只是一個只包含原始列表的列表，因爲你只考慮了每個元素的子列表。