haskell - suma - recorrer listas en scheme

Seq.zip en F#puede requerir un elemento de secuencia aparentemente extra para completar

Question

Vamos a Seq.zip dos secuencias F #, una representada por una lista y la otra - por Seq.filter aplicado a una secuencia infinita:

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

regresa como se esperaba

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

Sin embargo,

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

se bloquea al tratar de obtener un tercer miembro no existente que puede pasar Seq.filter y eventualmente explotar fsi:

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

aunque el otro argumento representado por la lista de letras sugiere que solo dos elementos filtrados serían suficientes para realizar un zip a la especificación de la función.

Si recurrimos a Haskell para la comparación de la implementación, el equivalente

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

completa sin ningún problema produciendo

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

Como el comportamiento de implementación de Haskell parece intuitivamente correcto, ¿cuál es la justificación para el comportamiento observado de la implementación de F # Seq.zip?

ACTUALIZAR:

No noté que Haskell

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

no se completa de manera similar a F #.

En pocas palabras: es imposible implementar la función Zip capaz de comprimir secuencias de longitudes definidas e indefinidas en orden de argumento de manera agnóstica. La implementación de F # Zip simplemente prefiere el comportamiento de orden invariante a argumento sobre el orden de argumento de Haskell dependiente.

Answer 1

Basado en mi lectura de la fuente (https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/seq.fs en la línea 900) esto es lo que sucede:

La función relevante está en Seq.fs y se llama revamp2 (esto es lo que se llama Seq.zip)

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

Ahora cuando llamamos a .MoveNext () en la secuencia devuelta por esto, llama a MoveNext () en AMBAS de las secuencias de entrada.

Hacerlo de esta manera ha hecho que gran parte del otro código sea más simple, pero ha causado su problema: .MoveNext () no regresará para la secuencia infinita filtrada, sino que regresará para la secuencia finita, lo que lleva a un ciclo infinito.

Answer 2

La razón por la cual no se bloquea en Haskell es porque la implementación de zip resulta ser más estricta en su primer argumento que en el segundo.

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

Como los patrones se revisan de izquierda a derecha, esto da el siguiente comportamiento.

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

Dado que filter (<2) [0..] es semánticamente equivalente a 0 : 1 : ⊥ your, tu ejemplo es después de dos iteraciones

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

Si cambiamos el orden de los argumentos a zip (filter (<2) [0..]) ["A", "B"] , obtenemos

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

No sé mucho sobre F #, pero sospecho que algo similar está sucediendo allí.

Tenga en cuenta que no hay forma de definir zip modo que zip [] undefined y zip undefined [] devuelvan [] , ya que primero debe verificar uno de los argumentos, y es imposible verificarlo en contra de ⊥ debido a la monotonía .

Answer 3

No sé cómo lo hace Haskell, y estoy de acuerdo en que parece intuitivamente correcto (excepto que me pregunto qué pasaría en Haskell si cambiabas la lista de longitud fija y la lista de duración indeterminada), pero puedo mostrarte por qué funciona de esta manera en F #. Puede ver en el archivo de código fuente F # seq.fs que el detalle de implementación significativo está en 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()
          }

Entonces Seq.zip intentará mover ambas secuencias a su tercer elemento antes de decidir si el zip está completo, por lo tanto Seq.initInfinite (fun i -> i) |> Seq.filter ((>) 2) se atasca tratando de encontrar el tercer elemento "para siempre" (hasta Error: Enumeration based on System.Int32 exceeded System.Int32.MaxValue ).

Answer 4

Stephen Swensen ya respondió la pregunta.

La solución a partir de ahora parece usar Seq.take ya que conoce la longitud de una de las secuencias.

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