Create lazily

Question

I want to calculate the strength of the set. Because I do not need all the power at one time, it is better to create it lazily.

For instance:

powerset (set ["a"; "b"; "c"]) = seq { set []; set ["a"]; set ["b"]; set ["c"]; set ["a"; "b"]; set ["a"; "c"]; set ["b"; "c"]; set ["a";"b"; "c"]; } 

Since the result is a sequence, I prefer it in that order. How can I do this ideally in F #?

EDIT:

This is what I am going to use (based on BLUEPIXY answer):

 let powerset s = let rec loop nl = seq { match n, l with | 0, _ -> yield [] | _, [] -> () | n, x::xs -> yield! Seq.map (fun l -> x::l) (loop (n-1) xs) yield! loop n xs } let xs = s |> Set.toList seq { for i = 0 to List.length xs do for x in loop i xs -> set x } 

Thank you all for the excellent input.

Answer 1

 let rec comb nl = match n, l with | 0, _ -> [[]] | _, [] -> [] | n, x::xs -> List.map (fun l -> x ::l) (comb (n - 1) xs) @ (comb n xs) let powerset xs = seq { for i = 0 to List.length xs do for x in comb i xs -> set x } 

Demo

 > powerset ["a";"b";"c"] |> Seq.iter (printfn "%A");; set [] set ["a"] set ["b"] set ["c"] set ["a"; "b"] set ["a"; "c"] set ["b"; "c"] set ["a"; "b"; "c"] val it : unit = () 

Answer 2

From F # to scientists , slightly modified to be lazy

 let rec powerset s = seq { match s with | [] -> yield [] | h::t -> for x in powerset t do yield! [x; h::x] } 

Answer 3

Here's a different approach, using math instead of recursion:

 let powerset st = let lst = Set.toList st seq [0..(lst.Length |> pown 2)-1] |> Seq.map (fun i -> set ([0..lst.Length-1] |> Seq.choose (fun x -> if i &&& (pown 2 x) = 0 then None else Some lst.[x])))