¿Por qué se define foldl de forma extraña en Racket?

Question

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 la raqueta, (foldl - 0 '(1 2 3 4)) es 2, porque la raqueta "inteligente" calcula así: (4 - (3 - (2 - (1 - 0)))), que de hecho es 2.

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

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

entonces podríamos raqueta en 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é es foldl en la raqueta definido de una manera tan extraña (no estándar y no intuitiva), de manera diferente que en cualquier otro idioma?

Answer 1

Desde la raqueta documentation, la descripción de foldl: se mencionan

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

Dos puntos de interés de tu pregunta:

los LST de entrada se recorren de izquierda a derecha

y

foldl procesa los LST en el espacio constante

voy a especular sobre cómo la implementación para los que podría ser similar, con una lista única para simplificar:

(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 se puede ver , se cumplen los requisitos de recorrido de izquierda a derecha y espacio constante (observe la recursión de cola en iter), pero el pedido de los argumentos para 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 proc de esta manera:

(proc acc (car lst)) 

A continuación, el resultado sería:

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

Mi punto es que la documentación para foldl no hace suposiciones sobre el orden de evaluación de los argumentos para proc, solo h para 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 deseada para su expresión simplemente escribiendo esto:

(- 0 1 2 3 4) 
> -10 

Answer 2

de Raqueta foldl y foldr (y también SRFI-1'sfold y fold-right) tienen la propiedad de que

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

Supongo que el orden de los argumentos fue elegido por ese motivo.

Answer 3

• La definición Haskell es no uniforme. En Racket, la función para ambos pliegues tiene el mismo orden de entradas y, por lo tanto, puede simplemente 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 con el fin de hacer una comparación adecuada se debe evitar estos ejemplos numéricos de juguete donde tanto de las variables tipo son números enteros.)

• Esto tiene el buen subproducto donde se le anima para elegir 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 usado 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 es generalmente una mala elección en un lenguaje perezosa.

• Otra diferencia es que la versión de Haskell es más limitada que la versión de Racket de la manera habitual: opera en exactamente 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).

• Por último, es incorrecto suponer que Racket divergió de "muchos otros lenguajes funcionales", ya que doblar está lejos de ser un truco nuevo y Racket tiene raíces que son mucho más antiguas que Haskell (o estos otros lenguajes). La pregunta podría ir en sentido contrario: ¿Por qué el foldl de Haskell se define de forma extraña? (Y no, (-) no es una buena excusa.)

actualización histórico:

Dado que esto parece molestar a la gente una y otra vez, lo 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 menciona el "plegado" de ningún tipo. En cambio, Lisp tiene reduce, que es muy poco uniforme, especialmente si se tiene en cuenta su tipo. Por ejemplo, :from-end es un argumento de palabra clave que determina si es un escaneo a la izquierda o a la derecha y usa diferentes funciones de acumulador, lo que significa que el tipo de acumulador depende de esa palabra clave.Esto se suma a otros hacks: por lo general, 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 se usa generalmente para lo que su nombre indica: reducir una lista de valores en un solo valor, donde los dos tipos suelen ser 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 reduce y las operaciones posteriores de plegado.

• 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 el uniform types version (es decir, qué raqueta utiliza).

• La siguiente referencia es Bird & Wadler's ItFP (1988), que usa different types (como en Haskell). Sin embargo, ellos note in the appendix que Miranda tiene el mismo tipo (como en Racket).

• Miranda después en switched the argument order (es decir, se movió de la orden de Raqueta a la 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ó un montón de 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 Haskell y utiliza different types

• supongo que "¿Cómo los programas de diseño" (también conocido como HTDP) fue escrito aproximadamente en el mismo período, y eligieron la same type. Sin embargo, no hay motivación o explicación, y de hecho, después de ese ejercicio, simplemente se menciona como one of the built-in functions.

  La implementación de Racket del fold operations fue, por supuesto, el "built-in" que se menciona aquí.

• Luego vino SRFI-1, y la opción fue utilizar la misma versión (como Racket). Esta decisión was question por John David Stone, que apunta a un comentario en el que dice SRFI

  Nota: Esquema del MIT y Haskell flip fin de arg F para sus reduce y fold funciones.

  Olin tarde addressed this: todo lo que dijo fue:

  Buen punto, pero quiero coherencia entre las dos funciones. estado primer valor: SrfI-1, SML estado último valor: Haskell

  nota en particular de su uso de Estado-valor, lo que sugiere una vista en la tipos coherente son un punto posiblemente más importante que orden del operador

Answer 4

"de manera diferente que en cualquier otro lenguaje"

Como contraejemplo, Standard ML (ML es un lenguaje funcional muy antigua e influyente) 's foldl también funciona de esta manera: http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL