Comment créer une fonction récursive anonyme générant une séquence paresseuse en Clojure?

Question

Modifier: J'ai découvert une réponse partielle à ma propre question en écrivant ceci, mais je pense qu'elle peut facilement être améliorée, donc je vais quand même la publier. Peut-être qu'il existe une meilleure solution ?

Je cherche un moyen facile de définir des fonctions récursives dans une forme let sans avoir recours à letfn. C'est probablement une demande déraisonnable, mais la raison pour laquelle je cherche cette technique est que j'ai un mélange de données et de fonctions récursives qui dépendent les unes des autres de manière à nécessiter beaucoup d'assertions let et letfn imbriquées.

Je voulais écrire les fonctions récursives qui génèrent des séquences paresseuses de cette manière (en utilisant la séquence de Fibonacci comme exemple) :

(let [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  (take 10 fibs))

Mais il semble qu'en clojure, fibs ne peut pas utiliser son propre symbole pendant la liaison. La manière évidente de contourner cela est d'utiliser letfn.

(letfn [(fibo [] (lazy-cat [0 1] (map + (fibo) (rest (fibo)))))]
  (take 10 (fibo)))

Mais comme je l'ai dit plus tôt, cela conduit à beaucoup d'imbrications gênantes et d'alternance entre let et letfn.

Pour faire cela sans letfn et en utilisant simplement let, j'ai commencé par écrire quelque chose qui utilise ce que je pense être le U-combinateur (je viens de découvrir le concept aujourd'hui) :

(let [fibs (fn [fi] (lazy-cat [0 1] (map + (fi fi) (rest (fi fi)))))]
  (take 10 (fibs fibs)))

Mais comment se débarrasser de la redondance de (fi fi) ?

C'est à ce moment-là que j'ai découvert la réponse à ma propre question après une heure de lutte et d'ajout progressif de morceaux au combinateur Q.

(let [Q (fn [r] ((fn [f] (f f)) (fn [y] (r (fn [] (y y))))))
      fibs (Q (fn [fi] (lazy-cat [0 1] (map + (fi) (rest (fi))))))]
  (take 10 fibs))

Comment s'appelle ce combinateur Q que j'utilise pour définir une séquence récursive ? On dirait le combinateur Y sans arguments x. Est-ce la même chose ?

(defn Y [r] 
  ((fn [f] (f f)) 
   (fn [y] (r (fn [x] ((y y) x))))))

Y a-t-il une autre fonction dans clojure.core ou clojure.contrib qui fournit la fonctionnalité de Y ou Q ? Je ne peux pas imaginer que ce que je viens de faire soit idiomatique...

Answer 1

Letrec

J'ai récemment écrit une macro letrec pour Clojure, voici un Gist. Il agit comme le letrec de Scheme (si vous connaissez), ce qui signifie que c'est un croisement entre let et letfn : vous pouvez lier un ensemble de noms à des valeurs mutuellement récursives, sans que ces valeurs ne soient des fonctions (les séquences paresseuses sont également possibles), tant qu'il est possible d'évaluer la tête de chaque élément sans se référer aux autres (c'est le jargon d'Haskell - ou peut-être théorique -; ici, "tête" peut signifier par exemple l'objet séquence paresseuse lui-même, sans forcing impliqué).

Vous pouvez l'utiliser pour écrire des choses comme

(letrec [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  fibs)

ce qui est normalement uniquement possible au niveau supérieur. Voir le Gist pour plus d'exemples.

Comme indiqué dans le texte de la question, cela pourrait être remplacé par

(letfn [(fibs [] (lazy-cat [0 1] (map + (fibs) (rest (fibs)))))]
  (fibs))

pour le même résultat en temps exponentiel; la version letrec a une complexité linéaire (tout comme la forme top-level (def fibs (lazy-cat [0 1] (map + fibs (rest fibs))))).

iterate

Les séquences auto-récursives peuvent souvent être construites avec iterate - notamment lorsqu'une plage fixe de décalage en arrière suffit pour calculer n'importe quel élément donné. Voir clojure.contrib.lazy-seqs pour un exemple de comment calculer fibs avec iterate.

clojure.contrib.seq

c.c.seq fournit une fonction intéressante appelée rec-seq, permettant des choses comme

(take 10 (cseq/rec-seq fibs (map + fibs (rest fibs))))

Il a la limitation de permettre uniquement de construire une seule séquence auto-récursive, mais il pourrait être possible de s'inspirer de son code source pour des idées d'implémentation permettant des scénarios plus diversifiés. Si une seule séquence auto-récursive non définie au niveau supérieur est ce que vous recherchez, c'est la solution idiomatique.

combinators

Quant aux combinators tels que ceux affichés dans le texte de la question, il est important de noter qu'ils sont entravés par l'absence d'optimisation des appels récursifs terminaux (TCO) sur la JVM (et donc dans Clojure, qui choisit d'utiliser directement les conventions d'appel de la JVM pour une performance optimale).

niveau supérieur

Il est également possible de placer les "choses" mutuellement récursives au niveau supérieur, éventuellement dans leur propre espace de noms. Cela ne fonctionne pas très bien si ces "choses" doivent être paramétrées d'une manière ou d'une autre, mais des espaces de noms peuvent être créés dynamiquement si nécessaire (voir clojure.contrib.with-ns pour des idées d'implémentation).

commentaires finaux

Je reconnais volontiers que l'astuce letrec est loin d'être idiomatique en Clojure et je l'éviterais dans le code de production si autre chose pouvait fonctionner (et comme il y a toujours l'option du niveau supérieur...). Cependant, c'est (à mon avis!) agréable à manipuler et cela semble assez bien fonctionner. Je suis personnellement intéressé à découvrir ce qui peut être accompli sans letrec et dans quelle mesure une macro letrec rend les choses plus faciles / propres... Je n'ai pas encore formé d'opinion à ce sujet. Donc, voilà. Encore une fois, pour le cas de la séquence auto-récursive unique, iterate ou contrib pourraient être la meilleure solution.

Answer 2

fn prend un argument de nom facultatif avec ce nom lié à la fonction dans son corps. En utilisant cette fonctionnalité, vous pourriez écrire fibs comme suit :

(def fibs ((fn generateur [a b] (lazy-seq (cons a (generateur b (+ a b))))) 0 1))