Esquema: Implementar n-argumentos componer utilizando fold

Question

Estoy tratando de encontrar la "mejor" implementación de una "redacción" de múltiples argumentos en Scheme (sé que es un built-in en algunas implementaciones, pero asumo por el momento que estoy usando uno que no tiene esto).

Para una función de composición 2-argumento tengo esto:

(define compose 
    (lambda (f g) 
    (lambda x 
     (f (apply g x))))) 

Esto tiene la ventaja de que si el extremo derecho función necesita argumentos adicionales, estos pueden todavía ser transmitidos a través de la función combinada. Esto tiene la agradable propiedad de que componer la función de identidad sobre algo no cambia la función.

Por ejemplo:

(define identity 
    (lambda (x) x)) 

(define list1 
    (compose identity list)) 

(define list2 
    (compose identity list1)) 

(list2 1 2 3) 
> (1 2 3) 

ahora para hacer una "n-argumento" Componer que podía hacer esto:

(define compose-n 
    (lambda args 
    (foldr compose identity args))) 

((compose-n car cdr cdr) '(1 2 3)) 
> 3 

Pero esto ya no conserva que linda propiedad "identidad":

((compose-n identity list) 1 2 3) 
> procedure identity: expects 1 argument, given 3: 1 2 3 

El problema es que la función "inicial" se utiliza para el comando foldr. Ha construido:

Así que ... No estoy seguro de la mejor manera de evitar esto. "Foldl" parece ser la mejor alternativa natural, porque quiero que comenzar con la "identidad" de la izquierda no el derecho ...

embargo, una aplicación ingenua:

(define compose-n 
    (lambda args 
    (foldl compose identity args))) 

que funciona (tiene que invertir el orden de las aplicaciones de función):

((compose-n cdr cdr car) '(1 2 3)) 
> 3 

no resuelve el problema, porque ahora me acaban de tener que poner la función de la identidad de la izquierda!

((compose-n cdr cdr car) '(1 2 3)) 
> procedure identity: expects 1 argument, given 3: 1 2 3 

Es como, tengo que utilizar "foldr", pero necesita algo de valor diferente "inicial" de la función identidad ... o una función identidad mejor? ¡Obviamente estoy confundido aquí!

Me gustaría implementarlo sin tener que escribir un explícito "bucle" recursivo de cola ... parece que debe haber una manera elegante de hacerlo, solo estoy atascado.

Answer 1

Es posible que desee probar this version (utiliza reduce de SRFI 1):

(define (compose . fns) 
    (define (make-chain fn chain) 
    (lambda args 
     (call-with-values (lambda() (apply fn args)) chain))) 
    (reduce make-chain values fns)) 

No es ciencia de cohetes: cuando he publicado esto en el canal de IRC#scheme, Eli señaló que esta es la implementación estándar de compose . :-) (Como beneficio adicional, también funcionó bien con sus ejemplos.)

Answer 2

Aunque habría sido agradable para la lista de "vacío" de delegar a la función identidad, la entrega de este parece ser el resultado de lo siguiente, que no es tan malo:

(define compose-n 
    (lambda (first . rest) 
    (foldl compose first rest))) 

((compose-n cdr cdr car) '(1 2 3)) 

((compose-n list identity identity) 1 2 3) 

Answer 3

La cuestión aquí es que estás tratando de mezclar procedimientos de diferente aridad. Probablemente desee curry list y luego haga esto:

(((compose-n (curry list) identity) 1) 2 3) 

Pero eso no es realmente muy satisfactorio.

Usted podría considerar una función de n-aria identidad:

(define id-n 
    (lambda xs xs)) 

continuación, puede crear un procedimiento de composición específica para la composición de funciones n-aria:

(define compose-nary 
    (lambda (f g) 
    (lambda x 
     (flatten (f (g x)))))) 

componer un número arbitrario de n- Funciones aria con:

(define compose-n-nary 
    (lambda args 
    (foldr compose-nary id-n args))) 

Que funciona:

> ((compose-n-nary id-n list) 1 2 3) 
(1 2 3) 

EDIT: Ayuda a pensar en términos de tipos. Inventemos una notación de tipo para nuestros propósitos. Denotaremos el tipo de pares como (A . B), y el tipo de listas como [*], con la convención de que [*] es equivalente a (A . [*]) donde A es el tipo de car de la lista (es decir, una lista es un par de un átomo y una lista). Señalemos aún más funciones como (A => B) que significa "toma una A y devuelve una B". El => y el . se asocian ambos a la derecha, por lo que (A . B . C) es igual a (A . (B . C)).

Ahora bien ... teniendo en cuenta que, aquí está el tipo de list (leer :: como "tiene que escribir"):

list :: (A . B) => (A . B) 

Y aquí es la identidad:

identity :: A => A 

Hay una diferencia en especie . El tipo list está formado por dos elementos (es decir, el tipo de lista tiene el tipo * => * => *), mientras que el tipo identity está construido a partir de un tipo (el tipo de identidad tiene el tipo * => *).

composición tiene este tipo:

compose :: ((A => B).(C => A)) => C => B 

ver lo que sucede cuando se aplica a composelist y identity. A se unifica con el dominio de la función list, por lo que debe ser un par (o la lista vacía, pero vamos a pasarlo por alto). C se unifica con el dominio de la función identity, por lo que debe ser un átomo. La composición de los dos entonces, debe ser una función que toma un átomo C y produce una lista B. Esto no es un problema si solo damos átomos a esta función, pero si le damos listas, se ahogará porque solo espera un argumento.

Así es como el curry ayuda a:

curry :: ((A . B) => C) => A => B => C 

Aplicar curry-list y se puede ver lo que sucede. La entrada a list se unifica con (A . B). La función resultante toma un átomo (el automóvil) y devuelve una función. Esa función, a su vez, toma el resto de la lista (el cdr del tipo B), y finalmente cede la lista.

Es importante destacar que la función al curry list es del mismo tipo que identity, por lo que se pueden componer sin problemas. Esto funciona a la inversa también. Si crea una función de identidad que toma pares, puede componerse con la función normal list.

Answer 4

El OP mencionó (en un comentario a mi respuesta) que su implementación de Scheme no tiene call-with-values. Aquí hay una manera de falsificarlo (si puede asegurarse de que el símbolo <values> nunca se use en su programa: puede reemplazarlo por (void), (if #f #f), o lo que quiera que no se use, y eso es compatible con su implementación):

(define (values . items) 
    (cons '<values> items)) 

(define (call-with-values source sink) 
    (let ((val (source))) 
    (if (and (pair? val) (eq? (car val) '<values>)) 
     (apply sink (cdr val)) 
     (sink val)))) 

Lo que hace es que falsifica un objeto multivalor con una lista encabezada por el símbolo <values>. En el sitio call-with-values, comprueba si este símbolo está allí, y si no, lo trata como un valor único.

Si la función más a la izquierda de su cadena puede devolver un valor múltiple, su código de llamada debe estar preparado para descomprimir la lista de <values>. (Por supuesto, si su implementación no tiene valores múltiples, probablemente esto no le preocupe mucho).