recursion - pairs racket

¿Por qué se define foldl de una manera extraña en Racket? (4)

En Haskell, como en muchos otros lenguajes funcionales, la función foldl se define de manera que, por ejemplo, foldl (-) 0 [1,2,3,4] = -10 .

Esto está bien, porque foldl (-) 0 [1, 2,3,4] es, por definición, ((((0 - 1) - 2) - 3) - 4) .

Pero, en Racket, (foldl - 0 ''(1 2 3 4)) es 2, porque Racket "inteligentemente" calcula así: (4 - (3 - (2 - (1 - 0)))) , que de hecho es 2.

Por supuesto, si definimos la función auxiliar flip, así:

(define (flip bin-fn) (lambda (x y) (bin-fn y x)))

entonces podríamos en Racket lograr el mismo comportamiento que en Haskell: en lugar de (foldl - 0 ''(1 2 3 4)) podemos escribir: (foldl (flip -) 0 ''(1 2 3 4))

La pregunta es: ¿por qué se foldl en racket de una manera tan extraña (no estándar y no intuitiva), de manera diferente que en cualquier otro idioma?

"diferentemente que en cualquier otro idioma"

Como contraejemplo, el foldl estándar ML (ML es un lenguaje funcional muy antiguo e influyente) también funciona de esta manera: http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL

De la documentation Racket, la descripción de foldl :

(foldl proc init lst ...+) → any/c

Se mencionan dos puntos de interés para su pregunta:

los lsts de entrada se atraviesan de izquierda a derecha

foldl procesa los lsts en espacio constante

Voy a especular sobre cómo podría ser la implementación de eso, con una lista única por simplicidad:

(define (my-foldl proc init lst) (define (iter lst acc) (if (null? lst) acc (iter (cdr lst) (proc (car lst) acc)))) (iter lst init))

Como puede ver, se cumplen los requisitos de recorrido transversal de izquierda a derecha y espacio constante (observe la repetición de cola en iter ), pero el orden de los argumentos para el proc nunca se especificó en la descripción. Por lo tanto, el resultado de llamar al código anterior sería:

(my-foldl - 0 ''(1 2 3 4)) > 2

Si hubiéramos especificado el orden de los argumentos para el proc de esta manera:

(proc acc (car lst))

Entonces el resultado sería:

(my-foldl - 0 ''(1 2 3 4)) > -10

Mi punto es que la documentación de foldl no hace suposiciones sobre el orden de evaluación de los argumentos para proc , solo tiene que garantizar que se use un espacio constante y que los elementos de la lista se evalúen de izquierda a derecha.

Como nota al margen, puede obtener el orden de evaluación deseado para su expresión simplemente escribiendo esto:

(- 0 1 2 3 4) > -10

Racket''s foldl y foldr (y también SRFI-1''s fold y fold-right ) tienen la propiedad de

(foldr cons null lst) = lst (foldl cons null lst) = (reverse lst)

Yo especulo que el orden de los argumentos fue elegido por esa razón.

La definición de Haskell no es uniforme . En Racket, la función de ambos pliegues tiene el mismo orden de entradas y, por lo tanto, puede reemplazar foldl por foldr y obtener el mismo resultado. Si haces eso con la versión de Haskell obtendrás un resultado diferente (por lo general), y puedes verlo en los diferentes tipos de los dos.
(De hecho, creo que para hacer una comparación adecuada debe evitar estos ejemplos numéricos de juguetes donde las dos variables de tipo son enteros).
Esto tiene un buen subproducto en el que se recomienda elegir entre foldl o foldr según sus diferencias semánticas. Supongo que con el pedido de Haskell es probable que elija según la operación. Tiene un buen ejemplo para esto: ha utilizado foldl porque quiere restar cada número, y esa es una opción "obvia" que es fácil pasar por alto el hecho de que foldl suele ser una mala elección en un lenguaje perezoso.
Otra diferencia es que la versión de Haskell es más limitada que la versión de Racket de la manera habitual: opera exactamente en una lista de entrada, mientras que Racket puede aceptar cualquier cantidad de listas. Esto hace que sea más importante tener un orden de argumento uniforme para la función de entrada).
Finalmente, es incorrecto suponer que Racket se separó de "muchos otros lenguajes funcionales", ya que el plegado está lejos de ser un truco nuevo, y Racket tiene raíces que son mucho más antiguas que Haskell (o estos otros lenguajes). Por lo tanto, la pregunta podría ir a otro lado : ¿por qué se define el foldl de Haskell de una manera extraña? (Y no, (-) no es una buena excusa).

Actualización histórica:

Como esto parece molestar a la gente una y otra vez, hice un poco de trabajo de campo. Esto no es definitivo de ninguna manera, solo mi adivinación de segunda mano. Siéntase libre de editar esto si sabe más, o mejor aún, envíe un correo electrónico a las personas relevantes y pregunte. Específicamente, no sé las fechas en que se tomaron estas decisiones, por lo que la siguiente lista está en orden.

Primero estaba Lisp, y no se mencionaba el "plegamiento" de ningún tipo. En cambio, Lisp tiene una reduce que no es uniforme, especialmente si se tiene en cuenta su tipo. Por ejemplo :from-end es un argumento de palabra clave que determina si se trata de un escaneo a la izquierda o a la derecha y usa diferentes funciones de acumulación, lo que significa que el tipo de acumulador depende de esa palabra clave. Esto se suma a otros hacks: generalmente, el primer valor se saca de la lista (a menos que especifique un :initial-value ). Finalmente, si no especifica un :initial-value , y la lista está vacía, en realidad aplicará la función en cero argumentos para obtener un resultado.
Todo esto significa que reduce generalmente se usa para lo que su nombre sugiere: reducir una lista de valores en un solo valor, donde los dos tipos son generalmente los mismos. La conclusión aquí es que está cumpliendo una especie de propósito similar al plegado, pero no es tan útil como la construcción de iteración de la lista genérica que se obtiene al plegar. Supongo que esto significa que no hay una relación fuerte entre las operaciones de reduce y las posteriores.
El primer lenguaje relevante que sigue a Lisp y tiene un doblez adecuado es ML. La elección que se hizo allí, como se señala en la respuesta de newacct a continuación, fue para ir con la versión de tipos uniformes (es decir, lo que raqueta usa).
La siguiente referencia es Bird & Wadler''s ItFP (1988), que utiliza diferentes tipos (como en Haskell). Sin embargo, anotan en el apéndice que Miranda tiene el mismo tipo (como en Racket).
Miranda luego cambió el orden de los argumentos (es decir, pasó del orden de Racket al de Haskell). Específicamente, ese texto dice:
ADVERTENCIA: esta definición de foldl difiere de la de versiones anteriores de Miranda. El de aquí es el mismo que en Bird y Wadler (1988). La antigua definición tenía los dos argumentos de ''op'' invertidos.
Haskell tomó muchas cosas de Miranda, incluidos los diferentes tipos. (Pero por supuesto no conozco las fechas así que tal vez el cambio de Miranda se debió a Haskell.) En cualquier caso, es claro en este punto que no hubo consenso, por lo tanto, la pregunta revertida anterior es válida.
OCaml fue con la dirección de Haskell y usa diferentes tipos
Supongo que "Cómo diseñar programas" (también conocido como HtDP) se escribió aproximadamente en el mismo período y eligieron el mismo tipo . Sin embargo, no hay motivación ni explicación, y de hecho, después de ese ejercicio, simplemente se menciona como una de las funciones incorporadas .
La implementación de Racket de las operaciones de fold fue, por supuesto, los "built-ins" que se mencionan aquí.
Luego vino SRFI-1 , y la opción fue usar la misma versión (como Racket). Esta decisión fue cuestionada por John David Stone, quien señala un comentario en el SRFI que dice
Nota: MIT Scheme y Haskell invierten el orden ar de F para sus funciones de reduce y fold .
Olin luego se dirigió a esto : todo lo que dijo fue:
Buen punto, pero quiero consistencia entre las dos funciones. primero-valor de estado: srfi-1, valor de estado SML último: Haskell
Nótese en particular su uso del valor de estado , que sugiere una vista donde los tipos consistentes son un punto posiblemente más importante que el orden del operador.