Transducteurs
Les transducteurs sont des transformations algorithmiques composables. Indépendants du contexte de leurs sources d'entrée et de sortie, ils spécifient uniquement l'essence de la transformation en termes d'élément individuel. Du fait de leur découplage des sources d'entrée et de sortie, les transducteurs peuvent être utilisés dans de nombreux processus : collections, flux, canaux, observables, etc. Ils se composent directement, sans nécessiter la connaissance des entrées ni la création d'agrégats intermédiaires.
Voir également l'article de blog introductif, cette vidéo et cette section de la FAQ concernant les cas d'utilisation pertinents des transducteurs.
Terminologie
Une fonction de réduction est le type de fonction que l'on passe à `reduce`. C'est une fonction prenant un résultat cumulé et une nouvelle entrée, et renvoyant un nouveau résultat cumulé :
- ;; signature de la fonction de réduction
- whatever, input -> whatever
Un transducteur (parfois appelé xform ou xf) est une transformation d'une fonction réductrice à une autre :
- ;; signature du transducteur
- (whatever, input -> whatever) -> (whatever, input -> whatever)
Définition de transformations avec des transducteurs
La plupart des fonctions séquentielles incluses dans Clojure possèdent une arité produisant un transducteur. Cette arité omet la collection d'entrées ; celles-ci sont fournies par le processus appliquant le transducteur. Remarque : cette arité réduite n'implique ni curryfication ni application partielle.
Par exemple :
- (filter odd?) ;; renvoie un transducteur qui filtre les nombres impairs
- (map inc) ;; renvoie un transducteur de mappage pour l'incrémentation
- (take 5) ;; renvoie un transducteur qui prendra les 5 premières valeurs
Les transducteurs se composent selon la composition de fonctions classique. Un transducteur effectue son opération avant de décider s'il doit appeler le transducteur qu'il englobe et, le cas échéant, combien de fois. La méthode recommandée pour composer des transducteurs est d'utiliser la fonction `comp` existante.
- (def xf
- (comp
- (filter odd?)
- (map inc)
- (take 5)))
Le transducteur xf est une pile de transformations appliquée par un processus à une série d'éléments d'entrée. Chaque fonction de la pile est exécutée avant l'opération qu'elle englobe. La composition du transformateur s'effectue de droite à gauche, mais construit une pile de transformations qui s'exécute de gauche à droite (le filtrage précède le cartographie dans cet exemple).
Pour vous en souvenir, l'ordre des fonctions du transducteur dans comp correspond à l'ordre des transformations de séquence dans ->>. La transformation ci-dessus est équivalente à la transformation de séquence :
- (->> coll
- (filter odd?)
- (map inc)
- (take 5))
Les fonctions suivantes produisent un transducteur lorsque la collection d'entrée est omise : map cat mapcat filter remove take take-while take-nth drop drop-while replace partition-by partition-all keep keep-indexed map-indexed distinct interpose dedupe random-sample
Utilisation des transducteurs
Les transducteurs peuvent être utilisés dans de nombreux contextes (voir ci-dessous comment en créer de nouveaux).
Transduire
L'une des méthodes les plus courantes pour utiliser les transducteurs consiste à utiliser la fonction `transduce`, analogue à la fonction `reduce` standard :
- (transduce xform f coll)
- (transduce xform f init coll)
La fonction `transduce` effectue immédiatement (et non paresseusement) une réduction sur `coll` avec le transducteur `xform` appliqué à la fonction de réduction `f`, en utilisant `init` comme valeur initiale si elle est fournie, ou `(f)` sinon. `f` fournit les informations nécessaires pour accumuler le résultat, ce qui se produit dans le contexte (potentiellement avec état) de la réduction.
- (def xf (comp (filter odd?) (map inc)))
- (transduce xf + (range 5))
- ;; => 6
- (transduce xf + 100 (range 5))
- ;; => 106
Le transducteur xf composé sera appelé de gauche à droite avec un appel final à la fonction de réduction f. Dans le dernier exemple, les valeurs d'entrée seront filtrées, puis incrémentées, et enfin additionnées.
eduction
Pour capturer le processus d'application d'un transducteur à une collection, utilisez la fonction `eduction`. Celle-ci prend en paramètres un nombre quelconque de transformations et une collection finale, et renvoie une application réductible/itérable du transducteur aux éléments de la collection. Ces applications seront effectuées à chaque appel de `reduce`/`iterator`.
- (def iter (eduction xf (range 5)))
- (reduce + 0 iter)
- ;; => 6
into
Pour appliquer un transducteur à une collection d'entrée et construire une nouvelle collection de sortie, utilisez into (utilisant efficacement reduce et transients si possible) :
- (into [] xf (range 1000))
sequence
Pour créer une séquence à partir de l'application d'un transducteur à une collection d'entrée, utilisez la séquence :
- (sequence xf (range 1000))
Les éléments de la séquence résultante sont calculés de manière incrémentale. Ces séquences consomment les données d'entrée progressivement, selon les besoins, et réalisent intégralement les opérations intermédiaires. Ce comportement diffère de celui des opérations équivalentes sur les séquences paresseuses.
Création de transducteurs
Les transducteurs ont la forme suivante (code personnalisé entre "...") :
- (fn [rf]
- (fn ([] ...)
- ([result] ...)
- ([result input] ...)))
De nombreuses fonctions de séquence principales (comme `map`, `filter`,...) prennent des arguments spécifiques à l'opération (un prédicat, une fonction, un compteur,...) et renvoient un transducteur de cette forme, englobant ces arguments. Dans certains cas, comme `cat`, la fonction principale est une fonction de transduction et ne prend pas de fonction de réduction (RF).
La fonction interne est définie avec trois arités utilisées à des fins différentes :
- `Init` (arité 0) : doit appeler l'arité `init` sur la RF de transformation imbriquée, qui appellera finalement le processus de transduction.
- `Step` (arité 2) : il s'agit d'une fonction de réduction standard, mais elle est censée appeler la RF `step` (arité 0) une ou plusieurs fois, selon les besoins du transducteur. Par exemple, `filter` choisira (en fonction du prédicat) d'appeler ou non `RF`. `map` l'appellera toujours une seule fois. `cat` peut l'appeler plusieurs fois en fonction des entrées.
- `Completion` (arité 1) : certains processus ne se terminent pas, mais pour ceux qui se terminent (comme la transduction), l'arité d'achèvement est utilisée pour produire une valeur finale et/ou vider l'état. Cette arité doit appeler l'arité d'achèvement rf exactement une fois.
Un exemple d'utilisation de la complétion est la fonction partition-all, devant vider le cache contenant tous les éléments restants à la fin de l'entrée. La fonction de complétion peut servir à convertir une fonction de réduction en une fonction de transduction en ajoutant une arité de complétion par défaut.
Arrêt anticipé
Clojure propose un mécanisme pour spécifier l'arrêt anticipé d'une réduction :
- `reduced` prend une valeur et renvoie une valeur réduite indiquant que la réduction doit s'arrêter.
- `reduced?` renvoie `true` si la valeur a été créée avec `reduced`.
- `deref` ou `@` peuvent être utilisés pour récupérer la valeur à l'intérieur d'une réduction.
Un processus utilisant des transducteurs doit vérifier et s'arrêter lorsque la fonction d'étape renvoie une valeur réduite (voir la section «Création de processus transductibles» pour plus de détails). De plus, une fonction d'étape de transducteur utilisant une réduction imbriquée doit vérifier et signaler les valeurs réduites lorsqu'elles sont rencontrées. (Voir l'implémentation de la fonction `cat` pour un exemple.)
Transducteurs avec état de réduction
Certains transducteurs (tels que «take», «partition-all»,...) nécessitent un état lors du processus de réduction. Cet état est créé à chaque application du transducteur par le processus transductible. Prenons l'exemple du transducteur « dedupe », qui fusionne une série de valeurs dupliquées en une seule. Ce transducteur doit conserver la valeur précédente pour déterminer si la valeur actuelle doit être transmise.
- (defn dedupe []
- (fn [xf]
- (let [prev (volatile! ::none)]
- (fn
- ([] (xf))
- ([result] (xf result))
- ([result input]
- (let [prior @prev]
- (vreset! prev input)
- (if (= prior input)
- result
- (xf result input))))))))
Dans la fonction deduplication, `prev` est un conteneur d'état entreposant la valeur précédente pendant la réduction. La valeur de `prev` est volatile pour des raisons de performance, mais pourrait également être un atome. La valeur de `prev` n'est initialisée qu'au démarrage du processus de transduction (par exemple, lors d'un appel à `transduce`). Les interactions avec état sont donc contenues dans le contexte du processus transductible.
Lors de l'étape de finalisation, un transducteur avec un état de réduction doit vider son état avant d'appeler la fonction de finalisation du transformateur imbriqué, sauf s'il a déjà reçu une valeur réduite de l'étape imbriquée, auquel cas l'état en attente doit être ignoré.
Création de processus transductibles
Les transducteurs sont conçus pour être utilisés dans de nombreux types de processus. Un processus transductible est défini comme une succession d'étapes où chaque étape reçoit une entrée. La source des entrées est spécifique à chaque processus (collection, itérateur, flux,...). De même, le processus doit choisir comment traiter les sorties produites par chaque étape.
Si vous utilisez des transducteurs dans un nouveau contexte, voici quelques règles générales à respecter :
- Si une fonction d'étape renvoie une valeur réduite, le processus transductible ne doit plus lui fournir d'entrées. La valeur réduite doit être libérée (déréférencée) avant la fin du processus.
- Un processus en cours de finalisation doit appeler l'opération de finalisation sur la valeur accumulée finale une seule fois.
- Un processus transducteur doit encapsuler les références à la fonction renvoyée par l'appel d'un transducteur ; ces références peuvent être conservées dans un état et leur utilisation inter-processus légers peut s'avérer dangereuse.