如何使用序列在F#中创建无限集的幂集(组合)？

Question

这是我对这个问题的失败尝试,任何帮助将不胜感激.

我试图找到最好的算法,用于在热切列表上工作的电源组.这部分似乎工作正常.我遇到问题的部分是将它转换为与Sequences一起使用,以便它可以在流\无限列表上运行它.我真的不喜欢yield语法,因为我不太了解它但我宁愿不使用yield语法.

//All Combinations of items in a list
//i.e. 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
//i.e. 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
//i.e. 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

你seqCombinations几乎是正确的,但你没有正确地将它从列表翻译成序列.相当于[[]]不是Seq.empty,但是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

上面的代码适用于有限序列.但是对于无限的,它不起作用,因为它首先试图到达终点,这显然从来没有为无限序列做过.

如果你想要一个可以使用无限序列的函数,我设法找到两种方法,但它们都不是特别好.其中一个使用可变状态:

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
    }

另一个是关于处理细节的太多seq<T>:

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
    }

我认为如果你可以将无限序列视为头部和尾部,比如F#中的有限列表或Haskell中的任何序列,这将会容易得多.但是有可能在F#中有一种很好的表达方式,而我却找不到它.