Проблема реализации F # Seq

Ответ 1

Когда yield! появляется в позиции без хвоста, это существенно означает то же самое, что:

for v in <expr> do yield v

Проблема с этим (и почему это квадратичная) заключается в том, что для рекурсивных вызовов это создает цепочку итераторов с вложенными циклами for. Вам нужно перебрать всю последовательность, сгенерированную <expr> для каждого отдельного элемента, поэтому, если итерация является линейной, вы получаете квадратичное время (потому что линейная итерация происходит для каждого элемента).

Скажем, функция rwalk генерирует [ 9; 2; 3; 7 ]. На первой итерации рекурсивно сгенерированная последовательность имеет 4 элемента, поэтому вы должны перебирать более 4 элементов и добавлять 1. В рекурсивном вызове вы будете перебирать более 3 элементов и добавлять 1 и т.д. Используя диаграмму, вы можете как это квадратично:

x
x x 
x x x
x x x x

Кроме того, каждый из рекурсивных вызовов создает новый экземпляр объекта (IEnumerator), поэтому также существует некоторая стоимость памяти (хотя и линейная).

В положении хвоста компилятор/библиотека F # выполняет оптимизацию. Он "заменяет" текущий IEnumerable тем, который возвращается рекурсивным вызовом, поэтому ему не нужно перебирать его для генерации всех элементов - он просто возвращается (и это также снимает стоимость памяти).

Связанный.. Такая же проблема обсуждалась в дизайне С# lanaugage, и есть интересная статья об этом (их имя yield! равно yield foreach).

Ответ 2

Я не уверен, какой ответ вы ищете. Как вы заметили, комментарий не соответствует поведению компилятора. Я не могу сказать, является ли это экземпляром комментария, выходящего из синхронизации с реализацией или на самом деле это ошибка производительности (например, спецификация не вызывает особых требований к производительности).

Однако теоретически для компиляторного механизма должно быть возможно создать реализацию, которая работает на вашем примере в линейном времени. Фактически, даже такую ​​возможность можно построить в библиотеке, используя выражения вычислений. Здесь грубый пример, основанный в основном на бумаге Томаса, процитировал:

open System.Collections
open System.Collections.Generic

type 'a nestedState = 
/// Nothing to yield
| Done 
/// Yield a single value before proceeding
| Val of 'a
/// Yield the results from a nested iterator before proceeding
| Enum of (unit -> 'a nestedState)
/// Yield just the results from a nested iterator
| Tail of (unit -> 'a nestedState)

type nestedSeq<'a>(ntor) =
  let getEnumerator() : IEnumerator<'a> =
    let stack = ref [ntor]
    let curr = ref Unchecked.defaultof<'a>
    let rec moveNext() =
      match !stack with
      | [] -> false
      | e::es as l -> 
          match e() with
          | Done -> stack := es; moveNext()  
          | Val(a) -> curr := a; true
          | Enum(e) -> stack := e :: l; moveNext()
          | Tail(e) -> stack := e :: es; moveNext()
    { new IEnumerator<'a> with
        member x.Current = !curr
      interface System.IDisposable with
        member x.Dispose() = () 
      interface IEnumerator with
        member x.MoveNext() = moveNext()
        member x.Current = box !curr
        member x.Reset() = failwith "Reset not supported" }
  member x.NestedEnumerator = ntor
  interface IEnumerable<'a> with
    member x.GetEnumerator() = getEnumerator()
  interface IEnumerable with
    member x.GetEnumerator() = upcast getEnumerator()

let getNestedEnumerator : 'a seq -> _ = function
| :? ('a nestedSeq) as n -> n.NestedEnumerator
| s -> 
    let e = s.GetEnumerator()
    fun () ->
      if e.MoveNext() then
        Val e.Current
      else
        Done

let states (arr : Lazy<_[]>) = 
  let state = ref -1 
  nestedSeq (fun () -> incr state; arr.Value.[!state]) :> seq<_>

type SeqBuilder() = 
  member s.Yield(x) =  
    states (lazy [| Val x; Done |])
  member s.Combine(x:'a seq, y:'a seq) = 
    states (lazy [| Enum (getNestedEnumerator x); Tail (getNestedEnumerator y) |])
  member s.Zero() =  
    states (lazy [| Done |])
  member s.Delay(f) = 
    states (lazy [| Tail (f() |> getNestedEnumerator) |])
  member s.YieldFrom(x) = x 
  member s.Bind(x:'a seq, f) = 
    let e = x.GetEnumerator() 
    nestedSeq (fun () -> 
                 if e.MoveNext() then  
                   Enum (f e.Current |> getNestedEnumerator) 
                 else  
                   Done) :> seq<_>

let seq = SeqBuilder()

let rec walkr n = seq { 
  if n > 0 then
    return! walkr (n-1)
    return n
}

let rec walkl n = seq {
  if n > 0 then
    return n
    return! walkl (n-1)
}

let time = 
  let watch = System.Diagnostics.Stopwatch.StartNew()
  walkr 10000 |> Seq.iter ignore
  watch.Stop()
  watch.Elapsed

Обратите внимание, что мой SeqBuilder не является надежным; он пропускает несколько членов рабочего процесса и ничего не делает для удаления объекта или обработки ошибок. Тем не менее, он демонстрирует, что SequenceBuilder не нужно показывать квадратичное время работы на примерах, подобных вашим.

Также обратите внимание, что здесь существует компромисс между временным пространством - вложенный итератор для walkr n будет проходить через последовательность в O (n) времени, но для этого требуется пространство O (n).