fib

class Tuple {
  constructor(state, value) {
   this.state = state;
    this.value = value;
  }
}

class Nothing {
  map = mapper => this;
  get = () => 'nothing';
  or = (value) => new Just(value);
}

class Just {
  constructor(value) {
    this.value = value;
  }

  map = mapper => new Just(mapper(this.value));
  get = () => this.value;
  or = (value) => this;
}

class Memo {
  data = {};
  get = (key) => this.data[key] == null ? new Nothing() : new Just(this.data[key]);
  add = (key, value) => {
      this.data[key] = value;
      return this;
    };
}

class State {
  constructor(runState) {
   this.runState = runState;
  }

  static unit = value => new State(state => new Tuple(state, value));
  static getState = getFromState => new State(state => new Tuple(state, getFromState(state)));
  static transition = (mapper, value) => new State(state => new Tuple(mapper(state), value));
  flatMap = mapper => new State(state => {
    const temp = this.runState(state);
    return mapper(temp.value).runState(temp.state);
  })
  map = mapper => this.flatMap(value => State.unit(mapper(value)));
  eval = state => this.runState(state).value;
}

const fib = n => State.getState(memo => memo.get(n))
  .flatMap(maybe => maybe.map(value => State.unit(value)).or(
    fib(n - 1).flatMap(prev => fib(n - 2)
                                  .map(v => v + prev)
                                  .flatMap(value => State.transition(memo => memo.add(n, value), value))
              )
  ).get())

const memo = new Memo();
memo.add(0, 1);
memo.add(1, 1);

console.log([...Array(9).keys()].map(n => fib(n).eval(memo)))