Schéma: Implémenter n-argument composer en utilisant pli

Question

J'essaie de trouver la "meilleure" implémentation d'un multi-argument "composer" dans Scheme (je sais que c'est un builtin dans certaines implémentations, mais supposons pour l'instant je suis en utilisant celui qui n'a pas cela).

Pour avoir cette fonction de composition 2 argument I:

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

Ceci a l'avantage que si le droit le plus fonction a besoin d'arguments supplémentaires, ceux-ci peuvent encore être passés par la fonction combinée. Cela a la propriété agréable que composer la fonction d'identité sur quelque chose ne change pas la fonction.

Par exemple:

(define identity 
    (lambda (x) x)) 

(define list1 
    (compose identity list)) 

(define list2 
    (compose identity list1)) 

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

Maintenant, pour faire un "n-argument" composé que je pouvais le faire: la propriété

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

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

Mais ce ne conserve plus que belle "identité":

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

Le problème est que la fonction "initiale" est utilisée pour la commande foldr. Il a construit:

(compose identity (compose list identity)) 

Alors ... Je ne suis pas sûr de la meilleure façon de contourner cela. « Foldl » semble être la meilleure alternative naturelle, parce que je veux qu'il commence par « identité » sur la gauche pas le droit ...

Mais une mise en œuvre naïve:

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

qui fonctionne (doivent inverser l'ordre des applications de fonction):

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

ne résout pas le problème parce que maintenant je finis par avoir à mettre la fonction d'identité sur la gauche!

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

Il est comme, je dois utiliser « foldr » mais ont besoin d'une autre valeur « initiale » que la fonction d'identité ... ou une meilleure fonction d'identité? De toute évidence, je suis confus ici!

Je voudrais l'implémenter sans avoir à écrire une "boucle" de queue-récursif explicite ... il semble qu'il devrait y avoir une manière élégante de faire ceci, je suis juste coincé.

Answer 1

Vous pouvez essayer this version (utilise 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)) 

Ce n'est pas sorcier: quand je posté sur le canal IRC#scheme, Eli a noté que c'est la mise en œuvre standard de compose . :-) (En bonus, il a également bien fonctionné avec vos exemples.)

Answer 2

Bien qu'il aurait été agréable pour la liste « vide » à transférer à la fonction d'identité, se rendre cela semble le résultat suivant, qui est pas trop mal:

(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 question est ici que vous essayez de mélanger des procédures d'arité différente. Vous voulez probablement curry liste, puis faire:

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

Mais ce n'est pas vraiment très satisfaisant.

Vous pourriez envisager une fonction d'identité n-aire:

(define id-n 
    (lambda xs xs)) 

Ensuite, vous pouvez créer une procédure de composition spécifiquement pour la composition des fonctions de n-aire:

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

Composer un nombre arbitraire de n fonctions ary avec:

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

qui fonctionne:

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

EDIT: Il aide à penser en termes de types. Inventons une notation de type pour nos objectifs. Nous allons désigner le type de paires comme (A . B), et le type de listes comme [*], avec la convention que [*] est équivalent à (A . [*]) où A est le type du car de la liste (ie une liste est une paire d'un atome et une liste). Notons en outre les fonctions (A => B) signifiant "prend un A et renvoie un B". Les => et . sont tous deux associés à droite, donc (A . B . C) est égal à (A . (B . C)).

Maintenant ... étant donné que, voici le type de list (lire :: comme "a le type"):

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

Et voici l'identité:

identity :: A => A 

Il y a une différence en nature . Le type list est construit à partir de deux éléments (le type de liste a le type * => * => *) tandis que le type identity est construit à partir d'un type (le type d'identité a le type * => *).

Composition a ce type:

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

Voyez ce qui se passe lorsque vous appliquez compose à list et identity. A unifie avec le domaine de la fonction list, il doit donc s'agir d'une paire (ou de la liste vide, mais nous allons passer au-dessus). C unifie avec le domaine de la fonction identity, donc ce doit être un atome. La composition des deux alors, doit être une fonction qui prend un atome C et donne une liste B. Ce n'est pas un problème si nous donnons seulement cette fonction à des atomes, mais si nous lui donnons des listes, il s'étrangle car il n'attend qu'un seul argument.

Voilà comment cari aide:

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

Appliquer curry-list et vous pouvez voir ce qui se passe. L'entrée à list unifie avec (A . B). La fonction résultante prend un atome (la voiture) et renvoie une fonction. Cette fonction prend à son tour le reste de la liste (le cdr de type B), et finalement donne la liste.De manière importante, la fonction list au curry est du même type que identity, donc ils peuvent être composés sans problème. Cela fonctionne aussi dans l'autre sens. Si vous créez une fonction d'identité qui prend des paires, elle peut être composée avec la fonction list régulière.

Answer 4

L'OP a mentionné (dans un commentaire à ma réponse) que son implémentation de Scheme n'a pas call-with-values. Voici un moyen de simuler (si vous pouvez vous assurer que le symbole <values> n'est jamais utilisé dans votre programme: vous pouvez le remplacer par (void), (if #f #f), ou ce que vous voulez qui n'est pas utilisé, et cela est supporté par votre implémentation):

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

Qu'est-ce que cela fait, c'est qu'il fausse un objet à valeurs multiples avec une liste qui est dirigée par le symbole <values>. Au site call-with-values, il vérifie si ce symbole est présent et, dans le cas contraire, il le traite comme une seule valeur.

Si la fonction la plus à gauche de votre chaîne peut éventuellement renvoyer une valeur multiple, votre code appelant doit être préparé pour décompresser la liste <values>. (Bien sûr, si votre implémentation n'a pas plusieurs valeurs, cela ne vous concernera probablement pas beaucoup.)