Generieren von Teilmengen des Satzes. Faulheit?

Question

Ich habe eine Funktion geschrieben, die Teilmengen der Teilmenge erzeugt. Es verursachte Stapelüberlauf, wenn ich auf folgende Weise subsets [1..] benutze. Und es ist "normales" Verhalten, wenn es um "normale" (nicht faule) Sprachen geht. Und jetzt möchte ich meine Funktion verbessern, um faul zu sein.

P.S. Ich verstehe Faulheit nicht (und ich versuche es zu verstehen), also ist mein Problem vielleicht seltsam für dich - bitte erkläre es. :)

P.S. 2 Fühlen Sie sich frei, mir zu sagen, etwas über meine Behinderung in Haskell;)

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

Answer 1

Es gibt zwei Probleme mit dieser Funktion. Erstens rekuriert es zweimal, was es exponentiell ineffizienter als notwendig macht (wenn wir die exponentielle Anzahl der Ergebnisse ignorieren ...), weil jeder Teilbaum jedes Mal für alle überlappenden Teilmengen neu berechnet wird; dies kann durch let ing der rekursive Aufruf denselben Wert festgelegt werden: bereits Dieses

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

erlauben Sie length $ subsets' [1..25] in wenigen Sekunden zu berechnen, während length $ subsets [1..25] nimmt ... na ja, ich habe nicht warten;)

Das andere Problem ist, dass mit Ihrer Version, wenn Sie es eine unendliche Liste geben, wird es auf die unendlichen Schwanz dieser Liste zuerst rekursieren. Um alle endlichen Teilmengen auf sinnvolle Weise zu erzeugen, müssen wir zwei Dinge sicherstellen: erstens müssen wir jede Menge aus kleineren Mengen aufbauen (um die Terminierung zu gewährleisten), und zweitens sollten wir sicherstellen, dass die Reihenfolge 0.ist (dh nicht erzeuge die Liste [[1], [2], ...] zuerst und komme nie zum Rest). Dazu gehen wir von [[]] und rekursiv das aktuelle Element, um alles fügen wir bereits erstellt haben, und dann die neue Liste für den nächsten Schritt denken Sie daran:

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

die in dieser Reihenfolge ergibt:

*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

Sie nicht alle die Teilmengen einer unendlichen Menge erzeugen kann: sie bilden eine unzählbare Menge. Kardinalität macht es unmöglich.

Allenfalls können Sie versuchen, alle endlichen Untergruppen zu generieren. Dafür können Sie nicht von aus fortfahren, da Sie nie [] erreichen werden. Sie müssen induktiv vom Anfang der Liste statt vom Ende fortfahren.

Answer 3

Eine rechte fache Lösung wäre:

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) 

dann:

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