セットのサブセットを生成する。怠惰？

Question

私はサブセットのサブセットを生成する関数を書いています。 subsets [1..]で使用すると、スタックオーバーフローが発生しました。それは "普通の"（怠惰な）言語になると "正常な"振る舞いです。そして今、私は自分の機能を怠惰に改善したいと思います。

P.S.私は怠惰を理解していません（そして私はそれを理解しようとします）ので、おそらく私の問題はあなたのために奇妙です - 説明してください。 :)

P.S. 2私はHaskellでの私の障害について何かを言うこと自由に感じ;）

subsets :: [a] -> [[a]] 
subsets (x:xs) = (map (\ e -> x:e) (subsets xs)) ++ (subsets xs) 
subsets [] = [[]] 

Answer 1

この機能には2つの問題があります。まず、を2回、を再帰的に返します。これは、重複するサブセットのたびに各サブツリーが再計算されるため、指数関数的に必要以上に不便になります。これは再帰呼び出しが同じ値であるINGのletで固定することができます。

subsets' :: [a] -> [[a]] 
subsets' [] = [[]] 
subsets' (x:xs) = let s = subsets' xs 
        in map (x:) s ++ s 

これはすでによく、私は待っていなかった... length $ subsets [1..25]がかかる中に、数秒でlength $ subsets' [1..25]を計算できるようになります。）

他の問題は、あなたのバージョンで無限のリストを与えると、そのリストのが最初に無限小尾に再発することです。意味のある方法ですべての有限部分集合を生成するには、まず、小さな集合から各集合を構築して（終了を保証するため）、次にフェアの順序を保証する必要があります。最初にリスト[[1], [2], ...]を生成し、残りの部分は決して得られない）。このために、我々は[[]]から開始し、再帰的に我々がすでに生成されているすべてのものに現在の要素を追加し、次のステップのための新しいリストを覚えている：

*Main> take 100 $ subsets'' [1..] 
[[],[1],[2],[2,1],[3],[3,1],[3,2],[3,2,1],[4],[4,1],[4,2],[4,2,1],[4,3],[4,3,1],[4,3,2],[4,3,2,1],[5],[5,1],[5,2],[5,2,1],[5,3],[5,3,1],[5,3,2],[5,3,2,1],[5,4],[5,4,1],[5,4,2],[5,4,2,1],[5,4,3],[5,4,3,1],[5,4,3,2],[5,4,3,2,1],[6],[6,1],[6,2],[6,2,1],[6,3],[6,3,1],[6,3,2],[6,3,2,1],[6,4],[6,4,1],[6,4,2],[6,4,2,1],[6,4,3],[6,4,3,1],[6,4,3,2],[6,4,3,2,1],[6,5],[6,5,1],[6,5,2],[6,5,2,1],[6,5,3],[6,5,3,1],[6,5,3,2],[6,5,3,2,1],[6,5,4],[6,5,4,1],[6,5,4,2],[6,5,4,2,1],[6,5,4,3],[6,5,4,3,1],[6,5,4,3,2],[6,5,4,3,2,1],[7],[7,1],[7,2],[7,2,1],[7,3],[7,3,1],[7,3,2],[7,3,2,1],[7,4],[7,4,1],[7,4,2],[7,4,2,1],[7,4,3],[7,4,3,1],[7,4,3,2],[7,4,3,2,1],[7,5],[7,5,1],[7,5,2],[7,5,2,1],[7,5,3],[7,5,3,1],[7,5,3,2],[7,5,3,2,1],[7,5,4],[7,5,4,1],[7,5,4,2],[7,5,4,2,1],[7,5,4,3],[7,5,4,3,1],[7,5,4,3,2],[7,5,4,3,2,1],[7,6],[7,6,1],[7,6,2],[7,6,2,1]] 

Answer 2

あなたは無限集合のすべてサブセットを生成することができません：彼らは非可算集合を形成します。カーディナリティはそれを不可能にします。

ほとんどすべて有限のサブセットを生成しようとすることができます。そのため、[]には到着することはないので、[]以降の誘導では進めません。あなたはリストの始めから誘導の代わりに誘導的に進める必要があります。

Answer 3

：この順序になり

subsets'' :: [a] -> [[a]] 
subsets'' l = [[]] ++ subs [[]] l 
    where subs previous (x:xs) = let next = map (x:) previous 
           in next ++ subs (previous ++ next) xs 
     subs _ [] = [] 

右折りソリューションは次のようになります。その後、

powerset :: Foldable t => t a -> [[a]] 
powerset xs = []: foldr go (const []) xs [[]] 
    where go x f a = let b = (x:) <$> a in b ++ f (a ++ b) 

：

\> take 8 $ powerset [1..] 
[[],[1],[2],[2,1],[3],[3,1],[3,2],[3,2,1]]