When you think your functional code is stack safe
Tags: javascript, node, functional, learning
Published: 2020-10-04 14:29:24

---
title: When you think your functional code is stack safe
published: true
description: 
tags: #javascript #nodejs #functional #learning
//cover_image: https://direct_url_to_image.jpg
---

Recursion is a functional primitive and thus we try to avoid it, because ultimately it is only a nasty imperative loop in disguise. In FP we usually use folds and only resort to recursion if folding is not expressive enough.

In Javascript we additionally need to take care of stack-safety. It is therefore a smart strategy to implement folds with specific trampolines suitable for each type:

```javascript
// Foldable

const arrFold = f => init => xs => {
  let acc = init;
  
  for (let i = 0; i < xs.length; i++) // trampoline
    acc = f(acc) (xs[i], i);

  return acc;
};

// identity

const id = x => x;

// function composition

const comp = f => g => x => f(g(x));

const compn = arrFold(comp) (id); // variadic

// MAIN

const inc = x => x + 1;

compn([inc, inc, inc, inc, inc]) (0); // 5
```
[run code](https://repl.it/@ftor/WoefulAmpleRatio)

You may think yourself safe with `arrFold` being implemented as a stack-safe trampoline. However, you are not:

```javascript
// MAIN

const inc = x => x + 1;

const xs = Array(1e5).fill(inc);

const foo = compn(xs); // still okay

foo(0); // stack overflow
```
[run code](https://repl.it/@scriptum/VelvetyAntiqueDeclaration#index.js)

Composing means to combine two functions to a description of a new function, which is only evaluated if the required argument is provided. So iteratively composing builds up a huge description of descriptions waiting to be run.

What can we do about it? We need a way to break the composition apart. We've already used trampolines. It seems to be the proper tool:

```javascript
// trampoline for deferred function call trees

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

  while (step.tag !== "Base")
    step = f(...step.args);

  return init => {
    let {f, x} = step.x(init);

    while (step = f(x)) {
      if (step && step.tag === "Call") {
        step = step.f(step.x);

        if (step && step.tag === "Call") {
          ({f, x} = step);
          continue;
        }
        
        else break;
      }

      else break;
    }

    return step;
  }
};

const Base = x =>
  ({tag: "Base", x});

const Call = f => x =>
  ({tag: "Call", f, x});

const Step = (...args) =>
  ({tag: "Step", args});

// function composition

const comp = f => g => x => f(g(x));

const compn = xs => // variadic
  postRec((i, acc) =>
    i === xs.length
      ? Base(acc)
      : Step(i + 1, Call(comp(acc) (xs[i]))))
        (0, Call(id));

// MAIN

const inc = x => x + 1;

const xs = Array(1e5).fill(inc);

compn(xs) (0); // 100000
```
[run code](https://repl.it/@scriptum/FittingIdolizedIntegers#index.js)

`postRec` isn't a beauty. It reveals all its ugly operational semantics. Javascript was never about beauty but to get things done, I guess.

Anayway, in FP we often have to deal with descriptions of computations that create huge deferred function call trees. Having a specialized trampoline at our disposal allows us to get serious about FP in JS.

If you want to learn more about FP in JS take a look at my course on Github.