Seq.zip в F # может потребовать, казалось бы, дополнительный элемент последовательности для завершения

Question

Давайте Seq.zip две последовательности F #, одна представленная списком, а другая - Seq.filter, примененная к бесконечной последовательности:

Seq.initInfinite (fun i -> i)
|> Seq.filter ((>) 3)
|> Seq.zip ["A";"B"]

возвращается как ожидалось

val it : seq<string * int> = seq [("A", 0); ("B", 1)]

Тем не менее,

Seq.initInfinite (fun i -> i)
|> Seq.filter ((>) 2)
|> Seq.zip ["A";"B"]

зависает при попытке получить несуществующего третьего члена, который может передать Seq.filter и в конечном итоге взорвать fsi:

 Error: Enumeration based on System.Int32 exceeded System.Int32.MaxValue.

хотя другой аргумент, представленный списком букв, намекает на то, что для выполнения функции zip со спецификацией функции будет достаточно двух отфильтрованных элементов.

Если мы обратимся к Haskell для сравнения реализации, то эквивалент

 zip ["A","B"] (filter (<2) [0..])

завершается без проблем, давая

[("A",0),("B",1)]

Поскольку поведение реализации Haskell кажется интуитивно правильным, каково оправдание наблюдаемого поведения реализации F # Seq.zip?

UPDATE:

Я не заметил, что Haskell

zip (filter (<2) [0..]) ["A","B"]

не завершается аналогично F #.

Итог: Невозможно реализовать функцию Zip, способную архивировать последовательности определенной и неопределенной длины в порядке, не зависящем от порядка аргументов. Реализация F # Zip просто предпочитает инвариант к поведению порядка аргументов по сравнению с зависимым от порядка аргументов Haskell.

Answer 1

Причина, по которой он не зависает в Haskell, заключается в том, что реализация zip оказывается более строгой в первом аргументе, чем во втором.

zip :: [a] -> [b] -> [(a,b)]
zip (a:as) (b:bs) = (a,b) : zip as bs
zip _      _      = []

Поскольку шаблоны провереныслева направо это дает следующее поведение:

*Main> zip [] undefined
[]
*Main> zip undefined []
*** Exception: Prelude.undefined

Так как filter (<2) [0..] семантически эквивалентно 0 : 1 : ⊥, ваш пример после двух итераций

("A", 0) : ("B", 1) : zip [] undefined =
("A", 0) : ("B", 1) : []

Если мы изменимпорядок аргументов zip (filter (<2) [0..]) ["A", "B"], мы получаем

(0, "A") : (1, "B") : zip undefined [] =
(0, "A") : (1, "B") : undefined

Я не знаю много о F #, но я подозреваю, что там происходит нечто подобное.

Обратите внимание, что нетспособ определения zip таким образом, чтобы zip [] undefined и zip undefined [] оба возвращали [], так как сначала нужно проверить один из аргументов, а проверить на against невозможно из-за монотонности .

Answer 2

Я не знаю, как это делает Haskell, и я согласен, что это кажется интуитивно правильным (за исключением того, что мне интересно, что произойдет в Haskell, если вы переключите список фиксированной длины и список неопределенной длины), но я могу показать вам, почему так работает в F #. В файле исходного кода F # seq.fs вы можете видеть, что существенная деталь реализации находится в IEnumerable.map2:

  let map2 f (e1 : IEnumerator<_>) (e2 : IEnumerator<_>) : IEnumerator<_>=
      upcast 
          {  new MapEnumerator<_>() with
                 member this.DoMoveNext curr = 
                    let n1 = e1.MoveNext()
                    let n2 = e2.MoveNext()
                    if n1 && n2 then
                       curr <- f e1.Current e2.Current
                       true
                    else 
                       false
                 member this.Dispose() = e1.Dispose(); e2.Dispose()
          }

Поэтому Seq.zip попытается переместить обе последовательности в свой третий элемент, прежде чем решить, завершен ли zip, поэтому Seq.initInfinite (fun i -> i) |> Seq.filter ((>) 2) застревает, пытаясь найти третий элемент "навсегда" (до Error: Enumeration based on System.Int32 exceeded System.Int32.MaxValue).

Answer 3

Основываясь на моем чтении источника (https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/seq.fs примерно в строке 900), вот что происходит:

Соответствующая функция находится в Seq.fs и называется revamp2 (это то, что вызывается Seq.zip)

let revamp2 f (ie1 : seq<_>) (source2 : seq<_>) =
        mkSeq (fun () -> f (ie1.GetEnumerator()) (source2.GetEnumerator()))

Теперь, когда мы вызываем .MoveNext () для последовательности, возвращаемой этим, он вызывает MoveNext () ОБА входных последовательностей.

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

Answer 4

Стивен Свенсен уже ответил на вопрос.

В настоящее время в решении, похоже, используется Seq.take, поскольку вы знаете длину одной из последовательностей.

Seq.initInfinite (fun i -> i)
|> Seq.filter ((>) 2)
|> Seq.zip ["A";"B"]
|> Seq.take 2