Transducteur : un modèle de composition de fonctions puissant

alias : Transducteur : Un modèle de composition de fonctions puissant
carnet : Transducteur : 一种强大的函数组合模式

carte et filtre

La sémantique de map est le « mappage », ce qui signifie effectuer une seule fois une transformation sur tous les éléments d'un ensemble.

  const list = [1, 2, 3, 4, 5]

  list.map(x => x + 1)
  // [ 2, 3, 4, 5, 6 ]

  function map(f, xs) {
    const ret = []
    for (let i = 0; i < xs.length; i++) {
      ret.push(f(xs[i]))
    }
    return ret
  }

  map(x => x + 1, [1, 2, 3, 4, 5])
  // [ 2, 3, 4, 5, 6 ]

Ce qui précède utilise intentionnellement une instruction for pour exprimer clairement que l'implémentation de map repose sur le type de collection.
Exécution séquentielle ;
Évaluation immédiate, pas paresseuse.
Regardons le filtre :

  function filter(f, xs) {
    const ret = []
    for (let i = 0; i < xs.length; i++) {
      if (f(xs[i])) {
        ret.push(xs[i])
      }
    }
    return ret
  }

  var range = n => [...Array(n).keys()]

  filter(x => x % 2 === 1, range(10))
  // [ 1, 3, 5, 7, 9 ]

De même, l'implémentation du filtre dépend également du type de collection spécifique, et l'implémentation actuelle nécessite que xs soit un tableau.
Comment la carte peut-elle prendre en charge différents types de données ? Par exemple, Set , Map et les types de données personnalisés.
Il existe une manière conventionnelle : elle s'appuie sur l'interface (protocole) de la collection.
Différents langages ont des implémentations différentes, JS a un support natif relativement faible à cet égard, mais c'est également réalisable :
Effectuez une itération à l'aide de Symbol.iterator .
Utilisez Object#constractor pour obtenir le constructeur.
Alors, comment pouvons-nous prendre en charge de manière abstraite différents types de données en mode push ?
Imitant la bibliothèque ramdajs, il peut s'appuyer sur la fonction personnalisée @@transducer/step .

  function map(f, xs) {
    const ret = new xs.constructor()  // 1. construction
    for (const x of xs) { // 2. iteration
      ret['@@transducer/step'](f(x))  // 3. collection
    }
    return ret
  }

  Array.prototype['@@transducer/step'] = Array.prototype.push
  // [Function: push]

  map(x => x + 1, [1, 2, 3, 4, 5])
  // [ 2, 3, 4, 5, 6 ]

  Set.prototype['@@transducer/step'] = Set.prototype.add
  // [Function: add]

  map(x => x + 1, new Set([1, 2, 3, 4, 5]))
  // Set (5) {2, 3, 4, 5, 6}

En utilisant cette méthode, nous pouvons implémenter des fonctions telles que carte , filtre , etc., qui sont plus axiales.
La clé est de déléguer des opérations telles que la construction, l'itération et la collection à des classes de collection spécifiques, car seule la collection elle-même sait comment effectuer ces opérations.

  function filter(f, xs) {
    const ret = new xs.constructor()
    for (const x of xs) {
      if (f(x)) {
        ret['@@transducer/step'](x)
      }
    }
    return ret
  }

  filter(x => x % 2 === 1, range(10))
  // [ 1, 3, 5, 7, 9 ]

  filter(x => x > 3, new Set(range(10)))
  // Set (6) {4, 5, 6, 7, 8, 9}

composer

Il y aura quelques problèmes lorsque la carte et le filtre ci-dessus seront utilisés en combinaison.

  range(10)
    .map(x => x + 1)
    .filter(x => x % 2 === 1)
    .slice(0, 3)
  // [ 1, 3, 5 ]

Bien que seulement 5 éléments soient utilisés, tous les éléments de la collection seront parcourus.
Chaque étape générera un objet de collection intermédiaire.
Nous utilisons compose pour implémenter à nouveau cette logique

  function compose(...fns) {
    return fns.reduceRight((acc, fn) => x => fn(acc(x)), x => x)
  }

Pour prendre en charge la composition, nous implémentons des fonctions telles que la carte et un filtre sous forme de curry .

  function curry(f) {
    return (...args) => data => f(...args, data)
  }

  var rmap = curry(map)
  var rfilter = curry(filter)

  function take(n, xs) {
    const ret = new xs.constructor()
    for (const x of xs) {
      if (n <= 0) {
        break
      }
      n--
      ret['@@transducer/step'](x)
    }
    return ret
  }
  var rtake = curry(take)

  take(3, range(10))
  // [ 0, 1, 2 ]

  take(4, new Set(range(10)))
  // Set (4) {0, 1, 2, 3}

  const takeFirst3Odd = compose(
    rtake(3),
    rfilter(x => x % 2 === 1),
    rmap(x => x + 1)
  )

  takeFirst3Odd(range(10))
  // [ 1, 3, 5 ]

Jusqu'à présent, notre implémentation est claire et concise dans son expression mais inutile en termes d'exécution.

La forme de la fonction

Transformateur

La fonction carte dans la version curry est comme ceci :

  const map = f => xs => ...

C'est-à-dire map(x => ...) renvoie une fonction à paramètre unique.

  const list = [1, 2, 3, 4, 5]

  list.map(x => x + 1)
  // [ 2, 3, 4, 5, 6 ]

Les fonctions avec un seul paramètre peuvent être facilement composées.
Plus précisément, l'entrée de ces fonctions est des "données", la sortie est les données traitées et la fonction est un transformateur de données (Transformer).

  function map(f, xs) {
    const ret = []
    for (let i = 0; i < xs.length; i++) {
      ret.push(f(xs[i]))
    }
    return ret
  }

  map(x => x + 1, [1, 2, 3, 4, 5])
  // [ 2, 3, 4, 5, 6 ]

  function filter(f, xs) {
    const ret = []
    for (let i = 0; i < xs.length; i++) {
      if (f(xs[i])) {
        ret.push(xs[i])
      }
    }
    return ret
  }

Transformer est une fonction à paramètre unique, pratique pour la composition de fonctions.

  var range = n => [...Array(n).keys()]

Réducteur

Un réducteur est une fonction à deux paramètres qui peut être utilisée pour exprimer une logique plus complexe.

  filter(x => x % 2 === 1, range(10))
  // [ 1, 3, 5, 7, 9 ]

somme

  function map(f, xs) {
    const ret = new xs.constructor()  // 1. construction
    for (const x of xs) { // 2. iteration
      ret['@@transducer/step'](f(x))  // 3. collection
    }
    return ret
  }

carte

  Array.prototype['@@transducer/step'] = Array.prototype.push
  // [Function: push]

  map(x => x + 1, [1, 2, 3, 4, 5])
  // [ 2, 3, 4, 5, 6 ]

filtre

  Set.prototype['@@transducer/step'] = Set.prototype.add
  // [Function: add]

prendre

Comment mettre en œuvre take  ? Cela nécessite reduce pour avoir une fonctionnalité similaire à break .

  map(x => x + 1, new Set([1, 2, 3, 4, 5]))
  // Set (5) {2, 3, 4, 5, 6}

  function filter(f, xs) {
    const ret = new xs.constructor()
    for (const x of xs) {
      if (f(x)) {
        ret['@@transducer/step'](x)
      }
    }
    return ret
  }

  filter(x => x % 2 === 1, range(10))
  // [ 1, 3, 5, 7, 9 ]

Transducteur

Enfin, nous rencontrons notre protagoniste
Réexaminez d'abord la mise en œuvre précédente de la carte

  filter(x => x > 3, new Set(range(10)))
  // Set (6) {4, 5, 6, 7, 8, 9}

Nous devons trouver un moyen de séparer la logique qui dépend du tableau (Array) mentionné ci-dessus et de la résumer dans un Reducer .

  range(10)
    .map(x => x + 1)
    .filter(x => x % 2 === 1)
    .slice(0, 3)
  // [ 1, 3, 5 ]

La construction a disparu, l'itération a disparu et la collection d'éléments a également disparu.
Grâce à un réducteur , notre carte ne contient que la logique au sein de ses responsabilités.
Jetez un autre coup d'œil au filtre

  function compose(...fns) {
    return fns.reduceRight((acc, fn) => x => fn(acc(x)), x => x)
  }

Avis rfilter et le type de retour de rmap ci-dessus :

  function curry(f) {
    return (...args) => data => f(...args, data)
  }

Il s'agit en fait d'un Transfomer , avec les paramètres et les valeurs de retour étant Reducer , c'est Transducer .
Transformer est composable, donc Transducer est également composable.

  var rmap = curry(map)
  var rfilter = curry(filter)

  function take(n, xs) {
    const ret = new xs.constructor()
    for (const x of xs) {
      if (n <= 0) {
        break
      }
      n--
      ret['@@transducer/step'](x)
    }
    return ret
  }
  var rtake = curry(take)

dans et transduire

Cependant, comment utiliser le transducteur ?

  take(3, range(10))
  // [ 0, 1, 2 ]

  take(4, new Set(range(10)))
  // Set (4) {0, 1, 2, 3}

Nous devons implémenter l'itération et la collecte à l'aide d'un réducteur.

  const takeFirst3Odd = compose(
    rtake(3),
    rfilter(x => x % 2 === 1),
    rmap(x => x + 1)
  )

  takeFirst3Odd(range(10))
  // [ 1, 3, 5 ]

Cela peut fonctionner maintenant, et nous avons également remarqué que l'itération est "à la demande". Bien qu'il y ait 100 éléments dans la collection, seuls les 10 premiers éléments ont été itérés.
Ensuite, nous encapsulerons la logique ci-dessus dans une fonction.

  const map = f => xs => ...

  type Transformer = (xs: T) => R

Couler

Générateur de Fibonacci.

Supposons que nous ayons une sorte de collecte de données asynchrone, telle qu'un générateur de Fibonacci infini asynchrone.

  data ->> map(...) ->> filter(...) ->> reduce(...) -> result

  function pipe(...fns) {
    return x => fns.reduce((ac, f) => f(ac), x)
  }

  const reduce = (f, init) => xs => xs.reduce(f, init)

  const f = pipe(
    rmap(x => x + 1),
    rfilter(x => x % 2 === 1),
    rtake(5),
    reduce((a, b) => a + b, 0)
  )

  f(range(100))
  // 25

Nous devons implémenter la fonction into qui prend en charge les structures de données ci-dessus.
Publiez la version tableau du code à côté comme référence :

  type Transformer = (x: T) => T

Voici notre code d'implémentation :

  type Reducer = (ac: R, x: T) => R

L'opération de collecte est la même, l'opération d'itération est différente.

  // add is an reducer
  const add = (a, b) => a + b
  const sum = xs => xs.reduce(add, 0)

  sum(range(11))
  // 55

La même logique s'applique à différentes structures de données.

Ordres

Vous, qui êtes attentifs, remarquerez peut-être que l'ordre des paramètres de la version composée basée sur curry et de la version basée sur le réducteur sont différents.

version curry

  const list = [1, 2, 3, 4, 5]

  list.map(x => x + 1)
  // [ 2, 3, 4, 5, 6 ]

  function map(f, xs) {
    const ret = []
    for (let i = 0; i < xs.length; i++) {
      ret.push(f(xs[i]))
    }
    return ret
  }

L'exécution de la fonction est associative à droite.

version transducteur

  map(x => x + 1, [1, 2, 3, 4, 5])
  // [ 2, 3, 4, 5, 6 ]

  function filter(f, xs) {
    const ret = []
    for (let i = 0; i < xs.length; i++) {
      if (f(xs[i])) {
        ret.push(xs[i])
      }
    }
    return ret
  }

Référence

Les transducteurs arrivent
Transducteurs - Référence Clojure

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!