f# - 懒惰地生成powerset

Question

我想计算一组的幂集。因为我一次不需要整个powerset，所以最好懒惰地生成它。

例如：

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"];
}

由于结果是一个序列，所以我更喜欢上面的顺序。如何在 F# 中以惯用的方式做到这一点？

编辑：

这就是我要使用的（基于 BLUEPIXY 的回答）：

let powerset s =
    let rec loop n l =
        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
    }

感谢大家的出色投入。

Answer 1

let rec comb n l =
  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
  }

演示

> 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

来自F# for Scientists，稍微修改为懒惰

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

Answer 3

这是另一种方法，使用数学而不是递归：

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])))