Schema: implementazione di n-argomento comporre usando fold

Question

Sto cercando di trovare l'implementazione "migliore" di un multi-argomento "componi" in Scheme (so che è incorporato in alcune implementazioni, ma suppongo per il momento che sono usando uno che non ha questo).

Per una funzione di composizione 2-argomento ho questo:

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

Questo ha il vantaggio che se il più a destra funzione richiede argomenti aggiuntivi, questi possono ancora essere passati attraverso la funzione combinata. Questo ha la piacevole proprietà che la composizione della funzione di identità su qualcosa non modifica la funzione.

Ad esempio:

(define identity 
    (lambda (x) x)) 

(define list1 
    (compose identity list)) 

(define list2 
    (compose identity list1)) 

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

ora per fare un "n-argomento" comporre avrei potuto fare questo:

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

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

Ma questo non è più conserva quel simpatico "identità" di proprietà:

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

Il problema è che la funzione "iniziale" utilizzata per il comando foldr. Ha costruito:

(compose identity (compose list identity)) 

Quindi ... Non sono sicuro che il modo migliore intorno a questo. "Foldl" sembrerebbe essere l'alternativa naturale meglio, perché voglio che iniziare con "identità" sul sinistra non il destra ...

Ma un'implementazione ingenuo:

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

che funziona (hanno per invertire l'ordine delle applicazioni di funzione):

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

non risolve il problema perché ora finisco per dover mettere la funzione identità a sinistra!

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

E 'come, ho bisogno di usare "foldr" ma hanno bisogno di un po' diverso valore "iniziale" rispetto alla funzione identità ... o una funzione identità migliore? Ovviamente sono confuso qui!

Mi piacerebbe implementarlo senza dover scrivere un "loop" ricorsivo coda esplicito ... sembra che ci dovrebbe essere un modo elegante per farlo, sono solo bloccato.

Answer 1

Si potrebbe desiderare di provare this version (utilizza reduce da 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)) 

Non è scienza missilistica: quando ho postato questo sul canale IRC#scheme, Eli notato che questo è l'implementazione standard di compose . :-) (Come bonus, ha funzionato bene anche con i tuoi esempi.)

Answer 2

Anche se sarebbe stato bello per la lista "vuoto" di devolvere alla funzione identità, rendendo questo sembra essere il risultato di seguito, che non è troppo male:

(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

Il problema qui è che stai provando a mischiare procedure di diversa appartenenza. Probabilmente vuoi elencare curry e poi fare questo:

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

Ma non è proprio molto soddisfacente.

Si potrebbe considerare una funzione di n-ario identità:

(define id-n 
    (lambda xs xs)) 

quindi è possibile creare una procedura di composizione appositamente per la composizione di funzioni n-ario:

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

Comporre un numero arbitrario di n- ary funziona con:

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

Quali opere:

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

EDIT: Aiuta a pensare in termini di tipi. Inventiamo una notazione di tipo per i nostri scopi. Indicheremo il tipo di coppie come (A . B) e il tipo di elenchi come [*], con la convenzione che [*] equivale a (A . [*]) dove A è il tipo di car dell'elenco (ovvero una lista è una coppia di un atomo e una lista). Indichiamo inoltre funzioni come (A => B) che significa "prende una A e restituisce una B". I numeri => e . si associano entrambi a destra, quindi (A . B . C) equivale a (A . (B . C)).

Ora poi ... dato che, ecco il tipo di list (leggi :: come "ha tipo"):

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

Ed ecco identità:

identity :: A => A 

C'è una differenza in natura . Il tipo di list è costituito da due elementi (ad esempio il tipo di elenco ha il tipo * => * => *) mentre il tipo di identity viene costruito da un tipo (il tipo di identità ha tipo * => *).

Composizione ha questo tipo:

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

vediamo cosa succede quando si applica a composelist e identity. A unifica con il dominio della funzione list, quindi deve essere una coppia (o la lista vuota, ma lo sorveglieremo). C unifica con il dominio della funzione identity, quindi deve essere un atomo. La composizione dei due quindi, deve essere una funzione che prende un atomo C e produce una lista B. Questo non è un problema se diamo solo gli atomi di questa funzione, ma se gli diamo liste, si strozzerà perché aspetta solo un argomento.

Ecco come curry aiuta:

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

Applicare curry-list e si può vedere cosa succede. L'input per list si unifica con (A . B). La funzione risultante prende un atomo (l'auto) e restituisce una funzione. Quella funzione a sua volta prende il resto dell'elenco (il cdr di tipo B) e alla fine restituisce l'elenco.

È importante notare che la funzione al curry list è dello stesso tipo di identity, quindi è possibile comporli senza problemi. Funziona anche nell'altro modo. Se crei una funzione di identità che prende coppie, può essere composta dalla normale funzione list.

Answer 4

L'OP ha menzionato (in un commento alla mia risposta) che la sua implementazione di Schema non ha call-with-values. Ecco un modo per simularlo (se si riesce a garantire che il proprio codice non venga mai utilizzato nel proprio programma: è possibile sostituirlo con (void), (if #f #f) o qualsiasi altra cosa che non è utilizzata e supportata dalla propria implementazione):

(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)))) 

Ciò che fa è che finge un oggetto multivalore con un elenco intestato al simbolo <values>. Nel sito call-with-values, controlla se questo simbolo è presente e, in caso contrario, lo tratta come un singolo valore.

Se la funzione più a sinistra nella catena può eventualmente restituire un valore multiplo, è necessario preparare il codice chiamante per decomprimere l'elenco intestato a <values>. (Naturalmente, se la tua implementazione non ha più valori, questo probabilmente non ti preoccuperà molto.)