Как создать набор мощности (комбинации) бесконечного набора в F # с использованием последовательностей?

Question

Вот моя неудачная попытка решить эту проблему, и любая помощь будет признательна.

Я попытался найти лучший алгоритм для набора мощности, который работал в нетерпеливых списках.Эта часть, кажется, работает нормально.Часть, с которой у меня возникли проблемы, - это перевод ее для работы с последовательностями, чтобы она могла запускаться в потоковых \ бесконечных списках.Мне действительно не нравится синтаксис 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 #, а я просто не нашел его.

Answer 2

Я недавно задал похожий вопрос на Генерация powerset лениво и получил несколько хороших ответов.

Для powerset конечных множеств ответ @Daniel в приведенной выше ссылке является эффективным решением и, вероятно, соответствует вашей цели.Вы можете придумать контрольный пример, чтобы сравнить его подход с вашим.

Что касается powerset бесконечных множеств, то здесь немного математики.Согласно теореме Кантора , набор мощностей счетно бесконечного множества неисчислимо бесконечен .Это означает, что нет способа перечислить powerset всех целых чисел (который счетно бесконечен) даже ленивым образом.Интуиция одинакова для действительных чисел;поскольку действительное число неисчислимо бесконечно, мы не можем фактически моделировать их, используя бесконечные последовательности.

Следовательно, не существует алгоритма для перечисления мощности набора счетно бесконечного множества.Или такой алгоритм просто не имеет смысла.

Answer 3

Это своего рода шутка, но на самом деле она даст правильный результат для бесконечной последовательности (просто это невозможно доказать - эмпирически, а не математически).

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