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

Question

J'expérimente un style plus fonctionnel dans mon JavaScript ; par conséquent, j'ai remplacé les boucles for par des fonctions utilitaires telles que map et reduce. Cependant, je n'ai pas trouvé de remplacement fonctionnel pour les boucles while puisque l'optimisation des appels de queue n'est généralement pas disponible pour JavaScript. (D'après ce que je comprends, ES6 empêche les appels de queue de déborder de la pile mais n'optimise pas leurs performances).

J'explique ce que j'ai essayé ci-dessous, mais le TLDR est : Si je n'ai pas d'optimisation des appels de queue, quelle est la manière fonctionnelle d'implémenter les boucles while ?

Ce que j'ai essayé :

Création d'une fonction d'utilité "pendant" :

function while(func, test, data) {
  const newData = func(data);
  if(test(newData)) {
    return newData;
  } else {
    return while(func, test, newData);
  }
}

L'optimisation des appels de queue n'étant pas disponible, je pourrais réécrire ceci comme suit :

function while(func, test, data) {
  let newData = *copy the data somehow*
  while(test(newData)) {
    newData = func(newData);
  }
  return newData;
}

Cependant, à ce stade, j'ai l'impression d'avoir rendu mon code plus compliqué/confus pour tous ceux qui l'utilisent, puisque je dois me trimballer une fonction utilitaire personnalisée. Le seul avantage pratique que je vois est que cela m'oblige à rendre la boucle pure ; mais il semble qu'il serait plus simple d'utiliser une boucle while normale et de s'assurer que tout reste pur.

J'ai également essayé de trouver un moyen de créer une fonction génératrice qui imite les effets de la récursion/du bouclage, puis d'effectuer une itération sur cette fonction à l'aide d'une fonction utilitaire comme find ou reduce. Cependant, je n'ai pas encore trouvé une façon lisible de le faire.

Enfin, le remplacement des boucles for par des fonctions utilitaires rend plus évident ce que j'essaie d'accomplir (par exemple, faire quelque chose à chaque élément, vérifier si chaque élément passe un test, etc.) ). Cependant, il me semble qu'une boucle while exprime déjà ce que j'essaie d'accomplir (par exemple, itérer jusqu'à ce que nous trouvions un nombre premier, itérer jusqu'à ce que la réponse soit suffisamment optimisée, etc.

Après tout cela, ma question générale est la suivante : si j'ai besoin d'une boucle while, que je programme dans un style fonctionnel et que je n'ai pas accès à l'optimisation des appels de queue, quelle est la meilleure stratégie ?

Answer 1

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, l'extrait 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 les répétitions, mais seulement légèrement. Au lieu de renvoyer une valeur directement ou de répéter immédiatement, nous allons renvoyer un de nos deux types de trampoline, Bounce o 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

Currying ralentit aussi un peu les choses, mais nous pouvons y remédier en utilisant une fonction auxiliaire pour la récursion. Cette fonction est également intéressante car elle cache les détails de l'implémentation du trampoline et n'attend pas de l'appelant qu'il 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))
}

---

Style Clojure loop / recur

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

Clojure crée une interface trampoline spécialisée qui utilise une paire de fonctions, loop y 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, alors nous allons voir à quoi cela ressemble avec la monade de continuation. Réutilisation de loop y recur nous mettons en place un système de sécurité pour les piles cont qui peut enchaîner les opérations en utilisant chain et exécuter des séquences d'opérations en utilisant runCont . Pour repeat c'est absurde (et lent), mais c'est cool de voir la mécanique de cont à l'œuvre 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 place parmi les autres techniques. Cependant, la plupart des implémentations du Y combinator ne sont pas stack-safe et débordent si la fonction fournie par l'utilisateur se répète trop souvent. Puisque cette réponse a pour but de préserver un comportement sûr pour la pile, 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 et sûre pour la pile, 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

---

L'aspect pratique 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 for o while boucle, mais la cache derrière une interface fonctionnelle

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

Il est vrai que cette fonction est peut-être un exemple artificiel - toutes les fonctions récursives ne peuvent pas être converties en une fonction de type for o while mais dans un tel scénario où c'est possible, il est probablement préférable de le faire comme ça. Gardez les trampolines et les continuations pour les cas difficiles où une simple boucle ne suffit pas.

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, alors c'est fait travailler, mais seulement de façon paradoxale. Si votre ensemble de données est petit, vous n'avez pas besoin de setTimeout car il n'y aura pas de dépassement 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 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 redoutable stratégie

Ce que notre repeat ressemblerait à l'utilisation de setTimeout - remarquez qu'il est également défini dans un style de passage continu - c'est-à-dire que nous devons appeler repeat avec un rappel ( 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 à fonctionner que j'ai renoncé à essayer de le mesurer. Je ne l'ai pas inclus dans les benchmarks ci-dessous car il est trop lent pour être considéré comme une approche viable.

---

Promesses

Les promesses ont la capacité de chaîner des calculs et sont sûres en pile. Cependant, la réalisation d'une pile sûre repeat l'utilisation de Promises signifie que nous devrons abandonner notre valeur de retour synchrone, de la même manière que nous l'avons fait avec l'utilisation des setTimeout . Je présente ceci comme une "solution" parce qu'elle fait résoudre le problème, contrairement setTimeout mais 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 pas autant que celles de la monade de continuation. setTimeout exemple ci-dessus

Il est intéressant de noter que dans cette solution, les détails de l'implémentation de Promise sont complètement cachés à l'appelant. Une seule continuation est fournie comme quatrième argument et est appelée 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))

---

Repères

Sérieusement, le while La boucle est une lot plus rapide - comme presque 100x plus rapide (en comparant le meilleur au pire - mais sans inclure les réponses asynchrones : setTimeout y 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 nouvelles syntaxes ES6, mais vous pouvez mettre en œuvre un trampoline dans la version la plus ancienne possible de JavaScript. while et des fonctions de première classe

Ci-dessous, nous utilisons un javascript de l'âge de pierre pour démontrer que la récursion infinie est possible et performante sans nécessairement en sacrifiant une valeur de retour synchrone - 100,000,000 récursions dans le cadre de 6 secondes - il s'agit d'une différence considérable 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 à l'aide de JavaScript de l'âge de pierre

Si Si, pour une raison ou une autre, vous souhaitez une récursion infinie non bloquante (asynchrone), vous pouvez vous appuyer sur les éléments suivants setTimeout pour différer un 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 de non-blocage. A while la boucle et les fonctions de première classe sont toujours la seule exigence fondamentale pour obtenir une récursion sûre pour la pile sans sacrifier les performances.

Dans un programme moderne, étant donné les Promesses, nous substituerions l'option setTimeout appel pour une seule promesse.

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

Answer 2

Un meilleur loop / recur motif

Il y a deux choses que je n'aime pas à propos de la loop / recur décrit dans le réponse acceptée . Notez que j'aime bien l'idée derrière le loop / recur modèle. Cependant, je n'aime pas la façon dont il a été mis en œuvre. Voyons donc d'abord comment je l'aurais mis en œuvre.

// 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 cela avec le loop / recur modèle 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 deuxième loop la fonction utilise paramètres par défaut (c'est-à-dire a? ) et unions non balisées (c'est-à-dire Recur a ∪ b ). Ces deux caractéristiques sont en contradiction avec le paradigme de la programmation fonctionnelle.

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

El 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);
};

En outre, il permet 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 en eta. De plus, il vous oblige à renommer les paramètres parce que 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 car elles effacent des informations importantes, c'est-à-dire des informations sur la provenance des données. Par exemple, parce que mon Result le type est étiqueté je peux distinguer Return(Recur(0)) de Recur(0) .

D'autre part, parce que la variante de droite de Recur a ∪ b n'est pas balisé, si b est spécialisé pour Recur a c'est à dire si le type est spécialisé en Recur a ∪ Recur a alors il est impossible de déterminer si le Recur a vient du côté gauche ou du côté droit.

Une critique pourrait être que b ne sera jamais spécialisé pour Recur a et donc il n'est pas important que b est non balisé. 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 cela 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");

Les unions non balisées ne sont donc pas sûres. Cependant, même si nous prenions soin d'éviter les pièges des unions non balisées, je préférerais toujours les unions balisées car les balises fournissent des informations utiles lors de la lecture et du débogage du programme. À mon avis, les balises rendent le programme plus compréhensible et plus facile à déboguer.

Conclusion

Pour citer le Zen du python .

L'explicite est préférable à l'implicite.

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

El Trampoline monade

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

El Trampoline est un cousin plus puissant de la monade Loop qui est simplement la loop convertie en monade. Commençons donc par comprendre le Loop monade. Ensuite, nous verrons le problème principal de la Loop et comment la monade Trampoline 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 un Loop y un runLoop fonction. La structure de données renvoyée par Loop est une monade, et le pure y bind implémentent son interface monadique. Nous utilisons le pure y bind pour écrire une implémentation simple de la fonction Fonction d'Ackermann .

Malheureusement, le ack n'est pas sûre pour la pile parce qu'elle s'appelle récursivement jusqu'à ce qu'elle atteigne une fonction pure valeur. Au lieu de cela, nous voudrions ack pour renvoyer un Recur comme une structure de données pour ses cas inductifs. Cependant, Recur Les valeurs sont de type Result au lieu de Loop . Ce problème est résolu par le 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)));

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

Un autre avantage de Trampoline est qu'il peut être utilisé pour définir des fonctions récursives mutuellement sûres. Par exemple, voici une implémentation de la fonction Séquence féminine et masculine de Hofstadter fonctions.

// 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 problème de l'écriture de code monadique est L'enfer du rappel . Toutefois, ce problème 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 fonction. Il nous permet d'appeler une fonction qui renvoie un Trampoline sans l'exécuter réellement. Cela nous permet de construire de plus grandes Trampoline puis d'exécuter l'ensemble du calcul lorsque cela est nécessaire.

Conclusion

Si vous souhaitez écrire des fonctions à sécurité intégrée indirectement ou mutuellement récursives, ou des fonctions à sécurité intégrée monadiques, utilisez la fonction Trampoline monade. Si vous souhaitez écrire des fonctions non monadiques directement récursives et sûres pour la pile, utilisez la fonction loop / recur / return modèle.

Answer 3

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 sûre pour la pile, nous devons considérer deux cas :

• cas de base
• cas récurrent

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, il faut donc en créer un ou se rabattre sur Object codages.

Objet codé

// 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 codée

Sinon, nous pouvons créer une véritable union balisée avec un encodage de fonction. Notre style est maintenant 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));

Answer 4

Voir aussi déplier qui (d'après les documents de Ramda)

Construit une liste à partir d'une valeur de départ. Accepte une fonction iterator, qui renvoie soit false pour arrêter l'itération soit un tableau de longueur 2 contenant la valeur à ajouter à la liste résultante et la valeur de départ à utiliser utilisée lors du prochain appel à la fonction iterator.

var r = n => f => x => x > n ? false : [x, f(x)];
var repeatUntilGreaterThan = n => f => R.unfold(r(n)(f), 1);
console.log(repeatUntilGreaterThan(10)(x => x + 1));

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.22.1/ramda.min.js"></script>

Answer 5

J'ai beaucoup réfléchi à cette question. Récemment, je suis tombé sur le besoin d'une boucle while fonctionnelle.

Il me semble que la seule chose que veut vraiment cette question est un moyen de mettre en ligne une boucle while. Il existe un moyen de le faire en utilisant une fermeture.

"some string "+(a=>{
   while(comparison){
      // run code
   }
   return result;
})(somearray)+" some more"

Sinon, si ce que vous voulez est quelque chose qui enchaîne un tableau, vous pouvez utiliser la méthode reduce.

somearray.reduce((r,o,i,a)=>{
   while(comparison){
      // run code
   }
   a.splice(1); // This would ensure only one call.
   return result;
},[])+" some more"

Rien de tout cela ne transforme notre boucle while en une fonction. Mais cela nous permet d'utiliser une boucle en ligne. Et je voulais juste partager cela avec tous ceux que cela pourrait aider.