Skip to content

Comment remplacer les boucles while par une alternative de programmation fonctionnelle sans optimisation des appels de queue ?

Faites tout votre possible pour bien comprendre le code avant de l'utiliser dans votre projet, si vous avez quelque chose à apporter, vous pouvez le laisser dans les commentaires.

Solution :

Un exemple en JavaScript

Voici un exemple utilisant JavaScript. Actuellement, la plupart des navigateurs ne prennent pas en charge l'optimisation des appels de queue et, par conséquent, le snippet suivant échouera.

const repeat = n => f => x =>
  n === 0 ? x : repeat (n - 1) (f) (f(x))

console.log(repeat(1e3) (x => x + 1) (0)) // 1000
console.log(repeat(1e5) (x => x + 1) (0)) // Error: Uncaught RangeError: Maximum call stack size exceeded


Trampolines

Nous pouvons contourner cette limitation en modifiant la façon dont nous écrivons repeat, mais seulement légèrement. Au lieu de retourner une valeur directement ou de répéter immédiatement, nous retournerons un de nos deux types de trampolines, Bounce ou Done. Ensuite, nous utiliserons notre trampoline pour gérer la boucle.

// trampoline
const Bounce = (f,x) => ({ isBounce: true, f, x })

const Done = x => ({ isBounce: false, x })

const trampoline = ({ isBounce, f, x }) => {
  while (isBounce)
    ({ isBounce, f, x } = f(x))
  return x
}

// our revised repeat function, now stack-safe
const repeat = n => f => x =>
  n === 0 ? Done(x) : Bounce(repeat (n - 1) (f), f(x))

// apply trampoline to the result of an ordinary call repeat
let result = trampoline(repeat(1e6) (x => x + 1) (0))

// no more stack overflow
console.log(result) // 1000000

La récursion ralentit aussi un peu les choses, mais nous pouvons y remédier en utilisant une fonction auxiliaire pour la récursion. C'est bien aussi parce que cela cache le détail de l'implémentation du trampoline et ne s'attend pas à ce que l'appelant fasse rebondir la valeur de retour. Cela fonctionne environ deux fois plus vite que la fonction ci-dessus repeat

// aux helper hides trampoline implementation detail
// runs about 2x as fast
const repeat = n => f => x => {
  const aux = (n, x) =>
    n === 0 ? Done(x) : Bounce(x => aux (n - 1, x), f (x))
  return trampoline (aux (n, x))
}

Clojure-style loop/recur

Les trampolines sont sympas et tout mais c'est un peu ennuyeux d'avoir à se soucier d'appeler trampoline sur la valeur de retour de votre fonction. Nous avons vu que l'alternative était d'utiliser une aide auxiliaire, mais allez, c'est un peu ennuyeux aussi. Je suis sûr que certains d'entre vous ne sont pas très enthousiastes à propos de la fonction Bounce et Done aussi.

Clojure crée une interface trampoline spécialisée qui utilise une paire de fonctions, loop et recur - cette paire de tandem se prête à une expression remarquablement élégante d'un programme.

Oh et c'est très rapide, aussi

const recur = (...values) =>
  ({ recur, values })

const loop = run =>
{ let r = run ()
  while (r && r.recur === recur)
    r = run (...r.values)
  return r
}

const repeat = n => f => x =>
  loop
    ( (m = n, r = x) =>
        m === 0
          ? r
          : recur (m - 1, f (r))
    )

console.time ('loop/recur')
console.log (repeat (1e6) (x => x + 1) (0)) // 1000000
console.timeEnd ('loop/recur')              // 24 ms

Au début, ce style vous semblera étranger, mais avec le temps, je constate qu'il est le plus cohérent tout en produisant des programmes durables. Les commentaires ci-dessous vous aideront à vous familiariser avec cette syntaxe riche en expressions -

const repeat = n => f => x =>
  loop  // begin a loop with
    ( ( m = n   // local loop var m: counter, init with n
      , r = x   // local loop var r: result, init with x
      ) =>
        m === 0 // terminating condition
          ? r   // return result
          : recur    // otherwise recur with 
             ( m - 1 // next m value
             , f (r) // next r value
             )
    )

La monade de continuation

C'est l'un de mes sujets préférés tho, donc nous allons voir à quoi cela ressemble avec la monade de continuation. Réutilisation de loop et recurnous implémentons une continuation sûre pour la pile cont qui peut séquencer les opérations en utilisant chain et exécuter des séquences d'opérations en utilisant runCont. Pour repeatcela n'a pas de sens (et est lent), mais c'est cool de voir les mécanismes de l'opération cont au travail dans cet exemple simple -

const identity = x =>
  x

const recur = (...values) =>
  ({ recur, values })

const loop = run =>
{ let r = run ()
  while (r && r.recur === recur)
    r = run (...r.values)
  return r
}

// cont : 'a -> 'a cont
const cont = x =>
  k => recur (k, x)

// chain : ('a -> 'b cont) -> 'a cont -> 'b cont
const chain = f => mx =>
  k => recur (mx, x => recur (f (x), k))

// runCont : ('a -> 'b) -> a cont -> 'b
const runCont = f => mx =>
  loop ((r = mx, k = f) => r (k))

const repeat = n => f => x =>
{ const aux = n => x =>
    n === 0 // terminating condition
      ? cont (x) // base case, continue with x
      : chain             // otherise
          (aux (n - 1))   // sequence next operation on
          (cont (f (x)))  // continuation of f(x)

  return runCont  // run continuation
    (identity)    // identity; pass-thru
    (aux (n) (x)) // the continuation returned by aux
}

console.time ('cont monad')
console.log (repeat (1e6) (x => x + 1) (0)) // 1000000
console.timeEnd ('cont monad')              // 451 ms


Y combinateur

Le Y combinator est mon combinateur d'esprit ; cette réponse serait incomplète sans lui donner une certaine place parmi les autres techniques. Cependant, la plupart des implémentations du Y combinator ne sont pas stack-safe et déborderont si la fonction fournie par l'utilisateur se répète trop souvent. Puisque cette réponse a pour but de préserver le comportement stack-safe, nous implémenterons bien sûr Y d'une manière sûre - encore une fois, en s'appuyant sur notre fidèle trampoline.

Y démontre la possibilité d'étendre la récursion infinie synchrone facile à utiliser, stack-safe, sans encombrer votre fonction.

const bounce = f => (...xs) =>
  ({ isBounce: true, f, xs })

const trampoline = t => {
  while (t && t.isBounce)
    t = t.f(...t.xs)
  return t
}

// stack-safe Y combinator
const Y = f => {
  const safeY = f =>
    bounce((...xs) => f (safeY (f), ...xs))
  return (...xs) =>
    trampoline (safeY (f) (...xs))
}

// recur safely to your heart's content
const repeat = Y ((recur, n, f, x) =>
  n === 0
    ? x
    : recur (n - 1, f, f (x)))

console.log(repeat (1e5, x => x + 1, 0)) // 10000


Praticité avec while boucle

Mais soyons honnêtes : cela fait beaucoup de cérémonies alors que nous négligeons l'une des solutions potentielles les plus évidentes : utiliser une boucle for ou while mais la cacher derrière une interface fonctionnelle

A toutes fins utiles, cette repeat fonctionne de manière identique à celles fournies ci-dessus - sauf que celle-ci est environ un ou deux gadzillion fois plus rapide (à l'exception de la fonction loop/recur ). Heck, il est sans doute beaucoup plus facile à lire aussi.

D'accord, cette fonction est peut-être un exemple artificiel - toutes les fonctions récursives ne peuvent pas être converties en une fonction de type for ou while aussi facilement, mais dans un tel scénario où c'est possible, il est probablement préférable de simplement le faire comme ça. Gardez les trampolines et les continuations pour le levage lourd quand une simple boucle ne fera pas l'affaire.

const repeat = n => f => x => {
  let m = n
  while (true) {
    if (m === 0)
      return x
    else
      (m = m - 1, x = f (x))
  }
}

const gadzillionTimes = repeat(1e8)

const add1 = x => x + 1

const result = gadzillionTimes (add1) (0)

console.log(result) // 100000000


setTimeout n'est PAS une solution au problème de débordement de pile.

OK, donc fait fonctionne, mais seulement paradoxalement. Si votre ensemble de données est petit, vous n'avez pas besoin de... setTimeout car il n'y aura pas de débordement de pile. Si votre ensemble de données est grand et que vous utilisez setTimeout comme mécanisme de récursion sûr, non seulement vous rendez impossible le retour synchrone d'une valeur depuis votre fonction, mais elle sera si F lente que vous ne voudrez même pas utiliser votre fonction

Certaines personnes ont trouvé un site de préparation aux questions d'entretien qui encourage cette stratégie épouvantable

Ce que notre repeat ressemblerait en utilisant setTimeout - remarquez qu'il est également défini dans le style de passage de continuation - c'est-à-dire que nous devons appeler repeat avec un callback (k) pour obtenir la valeur finale

// do NOT implement recursion using setTimeout
const repeat = n => f => x => k =>
  n === 0
    ? k (x)
    : setTimeout (x => repeat (n - 1) (f) (x) (k), 0, f (x))

// be patient, this one takes about 5 seconds, even for just 1000 recursions
repeat (1e3) (x => x + 1) (0) (console.log)

// comment the next line out for absolute madness
// 10,000 recursions will take ~1 MINUTE to complete
// paradoxically, direct recursion can compute this in a few milliseconds
// setTimeout is NOT a fix for the problem
// -----------------------------------------------------------------------------
// repeat (1e4) (x => x + 1) (0) (console.log)

Je ne peux pas assez insister sur le fait que c'est mauvais. Même 1e5 prend tellement de temps à s'exécuter que j'ai renoncé à essayer de le mesurer. Je ne l'inclus pas dans les benchmarks ci-dessous parce que c'est juste trop lent pour être même considéré comme une approche viable.


Promesses

Les promesses ont la capacité de chaîner des calculs et sont stack-safe. Cependant, la réalisation d'une pile sûre repeat en utilisant les Promesses signifie que nous devrons abandonner notre valeur de retour synchrone, de la même manière que nous l'avons fait en utilisant la méthode setTimeout. Je fournis ceci comme une "solution" parce que cela... fait résoudre le problème, contrairement à setTimeoutmais d'une manière très simple par rapport au trampoline ou à la monade de continuation. Comme vous pouvez l'imaginer, les performances sont un peu mauvaises, mais loin d'être aussi mauvaises que celles de la monade de continuation. setTimeout ci-dessus

Il est intéressant de noter que dans cette solution, le détail de la mise en œuvre de Promise est complètement caché à l'appelant. Une seule continuation est fournie comme 4ème argument et son appel lorsque le calcul est terminé.

const repeat = n => f => x => k =>
  n === 0
    ? Promise.resolve(x).then(k)
    : Promise.resolve(f(x)).then(x => repeat (n - 1) (f) (x) (k))

// be patient ...
repeat (1e6) (x => x + 1) (0) (x => console.log('done', x))


Benchmarks

Sérieusement, le while est une beaucoup plus rapide - comme presque 100x plus rapide (en comparant le meilleur au pire - mais sans inclure les réponses asynchrones : setTimeout et Promise)

// sync
// -----------------------------------------------------------------------------
// repeat implemented with basic trampoline
console.time('A')
console.log(tramprepeat(1e6) (x => x + 1) (0))
console.timeEnd('A')
// 1000000
// A 114 ms

// repeat implemented with basic trampoline and aux helper
console.time('B')
console.log(auxrepeat(1e6) (x => x + 1) (0))
console.timeEnd('B')
// 1000000
// B 64 ms

// repeat implemented with cont monad
console.time('C')
console.log(contrepeat(1e6) (x => x + 1) (0))
console.timeEnd('C')
// 1000000
// C 33 ms

// repeat implemented with Y
console.time('Y')
console.log(yrepeat(1e6) (x => x + 1) (0))
console.timeEnd('Y')
// 1000000
// Y 544 ms

// repeat implemented with while loop
console.time('D')
console.log(whilerepeat(1e6) (x => x + 1) (0))
console.timeEnd('D')
// 1000000
// D 4 ms

// async
// -----------------------------------------------------------------------------

// repeat implemented with Promise
console.time('E')
promiserepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('E')
// 1000000
// E 2224 ms

// repeat implemented with setTimeout; FAILED
console.time('F')
timeoutrepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('F')
// ...
// too slow; didn't finish after 3 minutes

JavaScript de l'âge de pierre

Les techniques ci-dessus sont démontrées à l'aide des syntaxes ES6 plus récentes, mais vous pourriez mettre en œuvre un trampoline dans la version la plus ancienne possible de JavaScript - il suffit d'utiliser la fonction while et des fonctions de première classe

Ci-dessous, nous utilisons le JavaScript de l'âge de pierre pour démontrer que la récursion infinie est possible et performante sans les éléments suivants nécessairement sacrifier une valeur de retour synchrone - 100,000,000 récursions en dessous 6 secondes - c'est une différence spectaculaire par rapport à setTimeout qui ne peut que 1,000 récursions dans le même laps de temps.

function trampoline (t) {
  while (t && t.isBounce)
    t = t.f (t.x);
  return t.x;
}

function bounce (f, x) {
  return { isBounce: true, f: f, x: x };
}

function done (x) {
  return { isBounce: false, x: x };
}

function repeat (n, f, x) {
  function aux (n, x) {
    if (n === 0)
      return done (x);
    else 
      return bounce (function (x) { return aux (n - 1, x); }, f (x));
  }
  return trampoline (aux (n, x));
}

console.time('JS1 100K');
console.log (repeat (1e5, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100K');
// 100000
// JS1 100K: 15ms

console.time('JS1 100M');
console.log (repeat (1e8, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100M');
// 100000000
// JS1 100K: 5999ms

Récursion infinie non bloquante en utilisant le JavaScript de l'âge de pierre.

Si, pour une raison quelconque, vous voulez une récursion infinie non-bloquante (asynchrone), nous pouvons compter sur setTimeout pour différer une cadre unique au début du calcul. Ce programme utilise également le javascript de l'âge de pierre et calcule 100 000 000 de récursions en moins de 8 secondes, mais cette fois-ci de manière non bloquante.

Cela démontre qu'il n'y a rien de spécial à avoir une exigence non bloquante. A while boucle et des fonctions de première classe sont toujours la seule exigence fondamentale pour obtenir une récursion stack-safe sans sacrifier les performances.

Dans un programme moderne, étant donné les Promesses, nous substituerions la boucle setTimeout à la boucle setTimeout.setTimeoutà un appel à une seule Promise.

function donek (k, x) {
  return { isBounce: false, k: k, x: x };
}

function bouncek (f, x) {
  return { isBounce: true, f: f, x: x };
}

function trampolinek (t) {
  // setTimeout is called ONCE at the start of the computation
  // NOT once per recursion
  return setTimeout(function () {
    while (t && t.isBounce) {
      t = t.f (t.x);
    }
    return t.k (t.x);
  }, 0);
}

// stack-safe infinite recursion, non-blocking, 100,000,000 recursions in under 8 seconds
// now repeatk expects a 4th-argument callback which is called with the asynchronously computed result
function repeatk (n, f, x, k) {
  function aux (n, x) {
    if (n === 0)
      return donek (k, x);
    else
      return bouncek (function (x) { return aux (n - 1, x); }, f (x));
  }
  return trampolinek (aux (n, x));
}

console.log('non-blocking line 1')
console.time('non-blocking JS1')
repeatk (1e8, function (x) { return x + 1; }, 0, function (result) {
  console.log('non-blocking line 3', result)
  console.timeEnd('non-blocking JS1')
})
console.log('non-blocking line 2')

// non-blocking line 1
// non-blocking line 2
// [ synchronous program stops here ]
// [ below this line, asynchronous program continues ]
// non-blocking line 3 100000000
// non-blocking JS1: 7762ms

Un meilleur loop/recur modèle

Il y a deux choses que je n'aime pas dans le motif loop/recur décrit dans la réponse acceptée. Notez que j'aime en fait l'idée derrière le pattern loop/recur . Cependant, je n'aime pas la façon dont il a été mis en œuvre. Donc, regardons d'abord la façon dont je l'aurais implémenté.

// Recur :: a -> Result a b
const Recur = (...args) => ({ recur: true, args });

// Return :: b -> Result a b
const Return = value => ({ recur: false, value });

// loop :: (a -> Result a b) -> a -> b
const loop = func => (...args) => {
    let result = func(...args);
    while (result.recur) result = func(...result.args);
    return result.value;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));

console.time("loop/recur/return");
console.log(repeat(1e6, x => x + 1, 0));
console.timeEnd("loop/recur/return");

Comparez ceci avec le modèle loop/recur pattern décrit dans la réponse susmentionnée.

// recur :: a -> Recur a
const recur = (...args) => ({ recur, args });

// loop :: (a? -> Recur a ∪ b) -> b
const loop = func => {
    let result = func();
    while (result && result.recur === recur) result = func(...result.args);
    return result;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((m = n, r = x) => m === 0 ? r : recur(m - 1, f(r)));

console.time("loop/recur");
console.log(repeat(1e6, x => x + 1, 0));
console.timeEnd("loop/recur");

Si vous remarquez, la signature de type de la seconde loop utilise des paramètres par défaut (c'est-à-dire a?) et des unions non balisées (c'est-à-dire Recur a ∪ b). Ces deux caractéristiques sont en désaccord avec le paradigme de la programmation fonctionnelle.

Problème avec les paramètres par défaut

Le site loop/recur dans la réponse susmentionnée utilise des paramètres par défaut pour fournir les arguments initiaux de la fonction. Je pense que c'est un abus des paramètres par défaut. Vous pouvez tout aussi bien fournir des arguments initiaux en utilisant ma version de loop.

// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((n, x) => n === 0 ? Return(x) : Recur(n - 1, f(x)))(n, x);

// or more readable
const repeat = (n, f, x) => {
    const repeatF = loop((n, x) => n === 0 ? Return(x) : Recur(n - 1, f(x)));
    return repeatF(n, x);
};

De plus, elle permet la conversion en eta lorsque tous les arguments sont passés.

// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)))(n, f, x);

// can be η-converted to
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));

En utilisant la version de loop avec les paramètres par défaut ne permet pas la conversion eta. De plus, cela vous oblige à renommer les paramètres car vous ne pouvez pas écrire. (n = n, x = x) => ... en JavaScript.

Problème avec les unions non balisées.

Les unions non balisées sont mauvaises parce qu'elles effacent des informations importantes, c'est-à-dire les informations d'où proviennent les données. Par exemple, parce que mon Result est balisé, je peux distinguer Return(Recur(0)) de Recur(0).

D'autre part, parce que la variante de droite du type Recur a ∪ b n'est pas étiquetée, si b est spécialisé en Recur ac'est-à-dire si le type est spécialisé en Recur a ∪ Recur a.Recur a ∪ Recur aalors il est impossible de déterminer si le type Recur a provient du côté gauche ou du côté droit.

Une critique pourrait être que b ne sera jamais spécialisé en Recur aet que, par conséquent, il importe peu que b ne soit pas étiqueté. Voici un contre-exemple simple à cette critique.

// recur :: a -> Recur a
const recur = (...args) => ({ recur, args });

// loop :: (a? -> Recur a ∪ b) -> b
const loop = func => {
    let result = func();
    while (result && result.recur === recur) result = func(...result.args);
    return result;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((m = n, r = x) => m === 0 ? r : recur(m - 1, f(r)));

// infinite loop
console.log(repeat(1, x => recur(1, x), "wow, such hack, much loop"));

// unreachable code
console.log("repeat wasn't hacked");

Comparez ceci avec ma version de repeat qui est à l'épreuve des balles.

// Recur :: a -> Result a b
const Recur = (...args) => ({ recur: true, args });

// Return :: b -> Result a b
const Return = value => ({ recur: false, value });

// loop :: (a -> Result a b) -> a -> b
const loop = func => (...args) => {
    let result = func(...args);
    while (result.recur) result = func(...result.args);
    return result.value;
};

// repeat :: (Int, a -> a, a) -> a
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));

// finite loop
console.log(repeat(1, x => Recur(1, x), "wow, such hack, much loop"));

// reachable code
console.log("repeat wasn't hacked");

Ainsi, les unions non balisées ne sont pas sûres. Cependant, même si nous faisions attention à éviter les pièges des unions non balisées, je préférerais toujours les unions balisées parce que les balises fournissent des informations utiles lors de la lecture et du débogage du programme. IMHO, les balises rendent le programme plus compréhensible et plus facile à déboguer.

Conclusion

Pour citer le Zen de Python.

L'explicite est meilleur que l'implicite.

Les paramètres par défaut et les unions non balisées sont mauvais parce qu'ils sont implicites, et peuvent conduire à des ambiguïtés.

Le site Trampoline monade

Maintenant, je voudrais changer de vitesse et parler des monades. La réponse acceptée démontre une monade de continuation stack-safe. Cependant, si vous avez seulement besoin de créer une fonction récursive monadique stack-safe, alors vous n'avez pas besoin de la pleine puissance de la monade de continuation. Vous pouvez utiliser la fonction Trampoline monade.

Le site Trampoline est un cousin plus puissant de la monade Loop qui n'est que le loop convertie en monade. Donc, commençons par comprendre la fonction Loop monad. Ensuite, nous verrons le principal problème de la fonction Loop et comment la monade Trampoline monade peut être utilisée pour résoudre ce problème.

// Recur :: a -> Result a b
const Recur = (...args) => ({ recur: true, args });

// Return :: b -> Result a b
const Return = value => ({ recur: false, value });

// Loop :: (a -> Result a b) -> a -> Loop b
const Loop = func => (...args) => ({ func, args });

// runLoop :: Loop a -> a
const runLoop = ({ func, args }) => {
    let result = func(...args);
    while (result.recur) result = func(...result.args);
    return result.value;
};

// pure :: a -> Loop a
const pure = Loop(Return);

// bind :: (Loop a, a -> Loop b) -> Loop b
const bind = (loop, next) => Loop(({ first, loop: { func, args } }) => {
    const result = func(...args);
    if (result.recur) return Recur({ first, loop: { func, args: result.args } });
    if (first) return Recur({ first: false, loop: next(result.value) });
    return result;
})({ first: true, loop });

// ack :: (Int, Int) -> Loop Int
const ack = (m, n) => {
    if (m === 0) return pure(n + 1);
    if (n === 0) return ack(m - 1, 1);
    return bind(ack(m, n - 1), n => ack(m - 1, n));
};

console.log(runLoop(ack(3, 4)));

Notez que loop a été divisé en une Loop et une runLoop fonction. La structure de données retournée par Loop est une monade, et la fonction pure et bind implémentent son interface monadique. Nous utilisons la fonction pure et bind pour écrire une implémentation simple de la fonction d'Ackermann.

Malheureusement, la fonction ack n'est pas stack safe parce qu'elle s'appelle récursivement jusqu'à ce qu'elle atteigne une valeur de pure valeur. Au lieu de cela, nous voudrions ack renvoie une Recur pour ses cas inductifs. Cependant, Recur sont de type Result au lieu de Loop. Ce problème est résolu par la fonction Trampoline monade.

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// pure :: a -> Trampoline a
const pure = Return;

// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
    Bounce(args => bind(first.func(...args), next))(first.args) :
    next(first.value);

// ack :: (Int, Int) -> Trampoline Int
const ack = Bounce((m, n) => {
    if (m === 0) return pure(n + 1);
    if (n === 0) return ack(m - 1, 1);
    return bind(ack(m, n - 1), n => ack(m - 1, n));
});

console.log(trampoline(ack(3, 4)));

Le site Trampoline est une combinaison de Loop et de Result. Le site Loop et Recur ont été combinés en un seul constructeur de données Bounce en un seul constructeur de données. Le site runLoop a été simplifiée et renommée en trampoline. Le site pure et bind ont également été simplifiées. En effet, pure est juste Return. Enfin, nous appliquons Bounce à l'implémentation originale de la ack .

Un autre avantage de Trampoline est qu'elle peut être utilisée pour définir des fonctions récursives mutuellement sûres pour la pile. Par exemple, voici une implémentation des fonctions de séquence Female et Male de Hofstadter.

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// pure :: a -> Trampoline a
const pure = Return;

// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
    Bounce(args => bind(first.func(...args), next))(first.args) :
    next(first.value);

// female :: Int -> Trampoline Int
const female = Bounce(n => n === 0 ? pure(1) :
    bind(female(n - 1), f =>
        bind(male(f), m =>
            pure(n - m))));

// male :: Int -> Trampoline Int
const male = Bounce(n => n === 0 ? pure(0) :
    bind(male(n - 1), m =>
        bind(female(m), f =>
            pure(n - f))));

console.log(Array.from({ length: 21 }, (_, n) => trampoline(female(n))).join(" "));
console.log(Array.from({ length: 21 }, (_, n) => trampoline(male(n))).join(" "));

Le principal point douloureux de l'écriture de code monadique est l'enfer des callbacks. Cependant, cela peut être résolu en utilisant des générateurs.

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// pure :: a -> Trampoline a
const pure = Return;

// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
    Bounce(args => bind(first.func(...args), next))(first.args) :
    next(first.value);

// bounce :: (a -> Generator (Trampoline b)) -> a -> Trampoline b
const bounce = func => Bounce((...args) => {
    const gen = func(...args);

    const next = data => {
        const { value, done } = gen.next(data);
        return done ? value : bind(value, next);
    };

    return next(undefined);
});

// female :: Int -> Trampoline Int
const female = bounce(function* (n) {
    return pure(n ? n - (yield male(yield female(n - 1))) : 1);
});

// male :: Int -> Trampoline Int
const male = bounce(function* (n) {
    return pure(n ? n - (yield female(yield male(n - 1))) : 0);
});

console.log(Array.from({ length: 21 }, (_, n) => trampoline(female(n))).join(" "));
console.log(Array.from({ length: 21 }, (_, n) => trampoline(male(n))).join(" "));

Enfin, les fonctions mutuellement récursives démontrent également l'avantage d'avoir une fonction séparée. trampoline séparée. Cela nous permet d'appeler une fonction retournant une Trampoline sans l'exécuter réellement. Cela nous permet de construire de plus grandes Trampoline et d'exécuter ensuite le calcul complet lorsque cela est nécessaire.

Conclusion

Si vous voulez écrire des fonctions stack-safe indirectement ou mutuellement récursives, ou des fonctions stack-safe monadiques, alors utilisez la fonction Trampoline monade. Si vous voulez écrire des fonctions non monadiques directement récursives stack-safe alors utilisez la monade Trampoline. loop/recur/return le motif.

La programmation au sens du paradigme fonctionnel signifie que nous sommes guidés par des types pour exprimer nos algorithmes.

Pour transformer une fonction récursive de queue en une version stack-safe, nous devons considérer deux cas :

  • cas de base
  • cas récursif

Nous devons faire un choix et cela va bien avec les unions balisées. Cependant, Javascript ne dispose pas d'un tel type de données, donc soit nous devons en créer un, soit nous rabattre sur... Object codages.

Objet Encodé

// simulate a tagged union with two Object types

const Loop = x =>
  ({value: x, done: false});

const Done = x =>
  ({value: x, done: true});

// trampoline

const tailRec = f => (...args) => {
  let step = Loop(args);

  do {
    step = f(Loop, Done, step.value);
  } while (!step.done);

  return step.value;
};

// stack-safe function

const repeat = n => f => x =>
  tailRec((Loop, Done, [m, y]) => m === 0
    ? Done(y)
    : Loop([m - 1, f(y)])) (n, x);

// run...

const inc = n =>
  n + 1;

console.time();
console.log(repeat(1e6) (inc) (0));
console.timeEnd();

Fonction encodée

Alternativement, nous pouvons créer une véritable union balisée avec un encodage de fonction. Maintenant, notre style est beaucoup plus proche des langages fonctionnels matures :

// type/data constructor

const Type = Tcons => (tag, Dcons) => {
  const t = new Tcons();
  t.run = cases => Dcons(cases);
  t.tag = tag;
  return t;
};

// tagged union specific for the case

const Step = Type(function Step() {});

const Done = x =>
  Step("Done", cases => cases.Done(x));

const Loop = args =>
  Step("Loop", cases => cases.Loop(args));

// trampoline

const tailRec = f => (...args) => {
  let step = Loop(args);

  do {
    step = f(step);
  } while (step.tag === "Loop");

  return step.run({Done: id});
};

// stack-safe function

const repeat = n => f => x => 
  tailRec(step => step.run({
    Loop: ([m, y]) => m === 0 ? Done(y) : Loop([m - 1, f(y)]),
    Done: y => Done(y)
  })) (n, x);

// run...

const inc = n => n + 1;
const id = x => x;

console.log(repeat(1e6) (inc) (0));

Si vous pensez que notre message a été utile, il serait très utile que vous le partagiez avec plus de juniors de cette manière, vous nous aiderez à diffuser notre contenu.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.