Effect.ts

// modified from https://github.com/safareli/purescript-effect/blob/fast/src/Effect.js
/*
A computation of type `Effect<a>` in runtime is represented by a function which when
invoked performs some effect and results some value of type `a`.
With trivial implementation of `Effect` we have an issue with stack usage, as on each `bind`
you create new function which increases size of stack needed to execute whole computation.
For example if you write `forever` recursively like this, stack will overflow:
``` purs
function forever(f: Effect<A>): Effect<never> = chain(f, _ => f)
```
Solution to the stack issue is to change runtime representation of Effect from function 
to some "free like structure" (Defunctionalization), for example if we were to write new
Effect structure which is stack safe we could do something like this:
``` haskell
data EffectSafe a
  = Effect (Effect a)
  | Pure a
  | exists b. Map (b -> a) (EffectSafe b)
  | exists b. Apply (EffectSafe b) (EffectSafe (b -> a))
  | exists b. Bind (b -> EffectSafe a) (EffectSafe b)
```
implementing Functor Applicative and Monad instances would be trivial, and instead of
them constructing new function they create new node of EffectSafe tree structure
which then needs to be interpreted.
We could implement `EffectSafe` in Typescript but in terms of compatibility when the world
you would need to convert `Effect<A>` to `() => A` and vice versa. 
Because In JS, function is an object, so we can set arbitrary properties on it. i.e. we can
use function as object, like look up some properties without invoking it. It means we can use
function as representation of `Effect`, and be able get benefits of the free-ish representation.
So we would assume an `Effect a` to be normal effectful function, but it could also have
`tag` property which could be 'PURE', 'MAP', 'APPLY' or 'BIND',
depending on the tag, we would expect certain properties to contain certain type of values:
``` js
type Effect<A>
  =           { (): A }
  |           { (): A, tag: "PURE",  _0: A }
  | forall Z. { (): A, tag: "MAP",   _0: (v: Z) => A,          _1: Effect<Z> }
  | forall Z. { (): A, tag: "APPLY", _0: Effect<Z>,            _1: Effect<((val: Z) => A)> }
  | forall Z. { (): A, tag: "BIND",  _0: (v: Z) => Effect<A>,  _1: Effect<Z> }



Effect a
  = { Unit -> a }
  | { Unit -> a, tag: "PURE",   _0 :: a }
  | forall b. { Unit -> a, tag: "MAP",    _0 :: b -> a,        _1 :: Effect  b }
  | forall b. { Unit -> a, tag: "APPLY",  _0 :: Effect b,      _1 :: Effect (b -> a) }
  | forall b. { Unit -> a, tag: "BIND",   _0 :: b -> Effect a, _1 :: Effect  b }
```
Now hardest thing is to interpret this in stack safe way. but at first let's see
how `pureE` `mapE` `applyE` `bindE` `runPure` are defined:
*/


export interface EffectRaw<A> { (): A }
interface EffectPURE<A> extends EffectRaw<A> {
  tag: "PURE",
  _0: A
}
interface EffectMAP<Z, A> extends EffectRaw<A>, EffectMAP_OP<Z, A> {
  _1: Effect<Z>
}
interface EffectAPPLY<Z, A> extends EffectRaw<A>, EffectAPPLY_OP<Z> {
  _1: Effect<((val: Z) => A)>
}
interface EffectBIND<Z, A> extends EffectRaw<A>, EffectBIND_OP<Z, A> {
  _1: Effect<Z>
}

export type Effect<A> = EffectRaw<A> | EffectTagged<A>
type EffectTagged<A>
  = EffectPURE<A>
  | EffectMAP<unknown, A>
  | EffectAPPLY<unknown, A>
  | EffectBIND<unknown, A>


export const pure = function <A>(x: A): EffectPURE<A> {
  const res: EffectPURE<A> = function $effect(): A { return runEff($effect); };
  res.tag = "PURE";
  res._0 = x;
  return res;
};

export const map = function <Z, A>(f: ((val: Z) => A)) {
  return function (effect: Effect<Z>): EffectMAP<Z, A> {
    const res: EffectMAP<Z, A> = function $effect(): A { return runEff($effect); };
    res.tag = "MAP";
    res._0 = f;
    res._1 = effect;
    return res;
  };
};

export const apply = function <Z, A>(effF: Effect<((val: Z) => A)>) {
  return function (effect: Effect<Z>): EffectAPPLY<Z, A> {
    const res: EffectAPPLY<Z, A> = function $effect(): A { return runEff($effect); };
    res.tag = "APPLY";
    res._0 = effect;
    res._1 = effF;
    return res;
  };
};

export const bind = function <Z, A>(effect: Effect<Z>) {
  return function (f: (val: Z) => Effect<A>): EffectBIND<Z, A> {
    const res: EffectBIND<Z, A> = function $effect(): A { return runEff($effect); };
    res.tag = "BIND";
    res._0 = f;
    res._1 = effect;
    return res;
  };
};
/*
So when this function is called it will take effect which must have the `tag` property on it.
we would set up some variables which are needed for safe evaluation:
* operations - this will be a type aligned sequence of `Operations` which looks like this:
  ``` purs
  Operation a b
    = { tag: "MAP",        _0 :: a -> b }
    | { tag: "APPLY",      _0 :: Effect a }
    | { tag: "APPLY_FUNC", _0 :: a -> b }
    | { tag: "BIND",       _0 :: a -> Effect b }


type Effect<Z, A>
  = { tag: "MAP",        _0: (v: Z) => A }
  | { tag: "APPLY",      _0: Effect<Z> }
  | { tag: "APPLY_FUNC", _0: (v: Z) => A}
  | { tag: "BIND",       _0: (v: Z) => Effect<A> }

  ```
* effect - initially it's `inputEff` (argument of the `runEff`), it's basically tip of the tree,
  it will be then updated with other nodes while we are interpreting the structure.
* res - it will store results of invocations of effects which return results
* op - it will store current `Operation` which is popped from `operations`
if you look closely at Operation and Effect you would see that they have similar shape.
MAP, APPLY, BIND from `Effect` have same representation as `Operation`
```
*/

interface EffectAPPLY_FUNC_OP<Z, A> { tag: "APPLY_FUNC", _0: (v: Z) => A }
interface EffectMAP_OP<Z, A> { tag: "MAP", _0: (v: Z) => A }
interface EffectAPPLY_OP<Z> { tag: "APPLY", _0: Effect<Z> }
interface EffectBIND_OP<Z, A> { tag: "BIND", _0: (v: Z) => Effect<A> }

type Effect_OP<Z, A>
  = EffectAPPLY_FUNC_OP<Z, A>
  | EffectMAP_OP<Z, A>
  | EffectAPPLY_OP<Z>
  | EffectBIND_OP<Z, A>


function runEff<A>(inputEff: Effect<A>): A {
  const operations: Array<Effect_OP<unknown, unknown>> = [];
  let effect: Effect<unknown> = inputEff;
  let res: unknown | undefined;
  let op: Effect_OP<unknown, unknown> | undefined;
  effLoop: for (; ;) {
    if ("tag" in effect) {
      switch (effect.tag) {
        case "MAP":
          operations.push(effect);
          effect = effect._1;
          continue;
        case "BIND":
          operations.push(effect);
          effect = effect._1;
          continue;
        case "APPLY":
          operations.push(effect);
          effect = effect._1;
          continue;
        case "PURE":
          res = effect._0;
          break;
      }
    } else {
      res = effect();
    }

    while ((op = operations.pop())) {
      switch (op.tag) {
        case "MAP":
          res = op._0(res);
          break
        case "APPLY_FUNC":
          res = op._0(res);
          break
        case "APPLY":
          effect = op._0;
          operations.push({ tag: "APPLY_FUNC", _0: res as (v: unknown) => unknown });
          continue effLoop;
        case "BIND":
          effect = op._0(res);
          continue effLoop;
      }
    }
    return res as A;
  }
}