# Stack safe Function composition

Dec 10, 2016 · 4 min read

Executing composition of many functions is not stack safe. For example:

`// if we have a list of many functionsconst fs = Array(100000).fill().map((_,idx) => x => x + idx)// and we want to compose themconst compose = (f,g) => x => f(g(x))// we can either use compose to create a new function which is// composition of other functions, which is not stack safefs.reduce(compose)(1)// or we can "interpret" the list of functions step by step // in a stack safe wayfs.reduceRight((arg,f) => f(arg),1) // 4999950001`

To fix this issue we need a way to compose functions such that instead of creating another function (which when used requires extra stack frame leading to stack overflow), we collect those small functions as list of functions, which then could be executed in a stack safe way.

Here we create a special type `Func a b` which expresses computations from values of type `a` to values of type `b` (similar to `(->)`).

`// type Func a b where//   One  :: (a -> b) -> Func a b//   Pipe :: Func a z -> Func z b -> Func a bconst Func = taggedSum({  One: ['f'],  Pipe: ['x', 'y'],})`

The representation we have is like a binary tree where data is on leafs. we could have used Linked List like structure instead, but Lists have bad performance during left associated concatenation, so using it would lead us to bad performance during composition. actually the bed performance issue could be fixed using Difference list (DList), but it represents elements of List using Functions and concatenation using Function composition, which could lead us to same stack overflow issue we want to solve. By representation `Func` with binary tree complexity of `compose` is `O(1)` and for `lower` it’s `O(n)` where `n` is number of functions in whole composition.

Now we can make it an instance of `Category` (actually we don’t yet have Category defined in Fantasy land but hope we’ll get it soon)

`// :: (a -> b) -> Func a bFunc.lift = Func.One// :: Ɐ a. Func a aFunc.id = Func.lift(a => a)// :: Func b c ~> Func a b -> Func a cFunc.prototype.compose = function(f) {  return Func.Pipe(f, this)}`

Now we can lift normal functions from `a` to `b` into `Func a b` and compose them! the composition builds up a tree of functions which could be inspected/interpreted in a stack safe way.

`// here we take a Func value and then visit each node in stack safe// way and build Array of Functions in correct order.// complexity of this function is `O(1)`//// :: Func a z -> [a->b, b->c, ..., x->y, y->z]const toArrayOfFunctions = function(root) {  const fs = []  const stack = []  while (true) {    if (root.tag == 'One'){      fs.push(root.f)      if (stack.length == 0) {        break      } else {        root = stack.pop()      }    } else {      stack.push(root.y)      root = root.x    }  }  return fs}// :: Func a b ~> () -> (a -> b)Func.prototype.lower = function() {  // we precompute `fs` here so that executing result multiple times  // does not recomputes it again  const fs = toArrayOfFunctions(this)  return x => fs.reduce((arg, f) => f(arg), x)}// :: Func a b ~> () -> a -> bFunc.prototype.call = function(x) {  return this.lower()(x)}`

To get feeling how it works lets see a small example:

`const ab = Func.lift(a => [a, 'b'])const bc = Func.lift(b => [b, 'c'])const ac = bc.compose(ab)const cd = Func.lift(c => [c, 'd'])const de = Func.lift(d => [d, 'e'])const ce = de.compose(cd)const ae = ce.compose(ac)const ez = Func.lift(e => [e, 'z'])const az = ez.compose(ae)console.log(toString(az)) /*Func.Pipe(  Func.Pipe(    Func.Pipe(      Func.One(a => [a, 'b']),      Func.One(b => [b, 'c'])    ),    Func.Pipe(      Func.One(c => [c, 'd']),      Func.One(d => [d, 'e'])    )  ),  Func.One(e => [e, 'z'])) */console.log(toString(toArrayOfFunctions(az))) /*[ a => [a, 'b'], b => [b, 'c'], c => [c, 'd'], d => [d, 'e'], e => [e, 'z']] */console.log(toString(az.call('a'))) /*[[[[["a", "b"], "c"], "d"], "e"], "z"] */`

Now we can go back to our initial example and fix it:

`const fs = Array(100000).fill()  .map((_, idx) => Func.lift(x => x + idx))const f = fs.reduce((ab, bc) => bc.compose(ab))f.call(1)) // 4999950001`

I think Func could be abstracted into a Free Category, which I tried to find but couldn’t, so there are things to explore in this direction. In general Free structures represent computations as data which then could be inspected and interpreted in a clever way. Func is a nice example of how this technique could be useful to fix stack size issue we had initially.

P.S. I came to this idea from this discussion

P.S.S. You might wanna take a look at safareli/purescript-stacksafe-function

Don’t miss the next article 🦄