How to create a power set (combination) of an infinite set in F # using sequences?

Question

Here is my unsuccessful attempt to resolve any help.

I tried to come up with a better power-up algorithm that worked on eager lists. This part seems to be working fine. The part I am having problems with is translating it to work with sequences so that it can run it in streaming / endless lists. I really don't like the output syntax because I don't understand it very well, but I would prefer to use it without using the yield syntax.

//All Combinations of items in a list //ie the Powerset given each item is unique //Note: lists are eager so can't be used for infinite let listCombinations xs = List.fold (fun acc x -> List.collect (fun ys -> ys::[x::ys]) acc) [[]] xs //This works fine (Still interested if it could be faster) listCombinations [1;2;3;4;5] |> Seq.iter (fun x -> printfn "%A" x) //All Combinations of items in a sequence //ie the Powerset given each item is unique //Note: Not working let seqCombinations xs = Seq.fold (fun acc x -> Seq.collect (fun ys -> seq { yield ys yield seq { yield x yield! ys} }) acc) Seq.empty xs //All Combinations of items in a sequence //ie the Powerset given each item is unique //Note: Not working (even wrong type signature) let seqCombinations2 xs = Seq.fold (fun acc x -> Seq.collect (fun ys -> Seq.append ys (Seq.append x ys)) acc) Seq.empty xs //Sequences to test on let infiniteSequence = Seq.initInfinite (fun i -> i + 1) let finiteSequence = Seq.take 5 infiniteSequence //This should work easy since its in a finite sequence //But it does not, so their must be a bug in 'seqCombinations' above for xs in seqCombinations finiteSequence do for y in xs do printfn "%A" y //This one is much more difficult to get to work //since its the powerset on the infinate sequence //None the less If someone could help me find a way to make this work //This is my ultimate goal let firstFew = Seq.take 20 (seqCombinations infiniteSequence) for xs in firstFew do for y in xs do printfn "%A" y 

Answer 1

Your seqCombinations almost correct, but you did not translate it from the lists in the sequence correctly. The equivalent [[]] not Seq.empty , but Seq.singleton Seq.empty :

 let seqCombinations xs = Seq.fold (fun acc x -> Seq.collect (fun ys -> seq { yield ys yield seq { yield x yield! ys} }) acc) (Seq.singleton Seq.empty) xs 

The above code works for finite sequences. But for the infinite, he does not work, because he first tries to reach the end, which he obviously never does for infinite sequences.

If you need a function that will work with infinite sequences, I managed to figure out two ways, but none of them are particularly pleasant. One of them uses mutable state:

 let seqCombinations xs = let combs = ref [[]] seq { yield! !combs for x in xs do let added = List.map (fun ys -> x::ys) !combs yield! added combs := !combs @ added } 

Otherwise, the details of seq<T> are too much:

 open System.Collections.Generic let seqCombinations (xs : seq<_>) = let rec combs acc (e : IEnumerator<_>) = seq { if (e.MoveNext()) then let added = List.map (fun ys -> (e.Current)::ys) acc yield! added yield! combs (acc @ added) e } use enumerator = xs.GetEnumerator() seq { yield [] yield! combs [[]] enumerator } 

I think it would be much easier if you could handle endless sequences in the form of head and tail, for example, end lists in F # or any sequence in Haskell. But of course, maybe there is a good way to express this in F #, and I just did not find it.

Answer 2

I recently asked a similar question in lazily generating a graphics engine and got some nice answers.

For a force set of finite sets, @Daniel's answer in the link provided is an effective solution and is probably suitable for your purpose. You can come up with a test case to compare its approach and yours.

As for the many infinite sets, there is a bit of math here. According to Cantor’s theorem , the set of degrees of a countable infinite set is uncountably infinite. This means that there is no way to list the set of all integers (countably infinite) even in a lazy way. Intuition is the same for real numbers; since a real number is uncountably infinite, we cannot model them using infinite sequences.

Therefore, there is no algorithm to list a set of powers of a countable infinite set. Or this algorithm just doesn't make sense.

Answer 3

This is a kind of joke, but it will actually generate the correct result for an infinite sequence (it is simply that it cannot be proved empirically, not mathematically).

 let powerset s = seq { yield Seq.empty for x in s -> seq [x] }