F#中的Seq.zip可能需要看似额外的序列元素才能完成

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的不存在的第3个成员:

 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实现的观察行为的正当性是什么？

更新:

我没注意到Haskell

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

没有像F#那样完成.

结论:不可能实现Zip函数,该函数能够以参数顺序无关的方式压缩已定义和未定义长度的序列.F#Zip实现只是优先于Haskell参数顺序依赖的参数顺序行为的不变量.

Answer 1

我不知道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在决定拉链是否完整之前,会尝试将两个序列移动到第三个元素,因此Seq.initInfinite (fun i -> i) |> Seq.filter ((>) 2)试图找到第三个元素"永远"(直到Error: Enumeration based on System.Int32 exceeded System.Int32.MaxValue).

Answer 2

之所以没有在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 []两者都返回[],因为你必须首先检查其中一个参数,并且由于单调性而无法检查⊥ .