Refactoring to discover Arr.traverse and the State applicative

traversing_state.js

// This gist shows how to factor a concrete stateful fold in vanilla JS
// into a number of general purpose utilities that can be combined to recover
// the original behavior

// We're going to start from a particular code snippet and iteratively make
// small changes to it to get a finished product

// While reading this post, it is useful to have a diff tool at hand that allows
// you to compare snippets side by side and see what changed in each iteration

// The goal is not to show a process of refactoring that you should be applying
// to your code on a day to day basis, but rather to show how refactoring from a
// concrete use case to an abstraction can help explain the meaning  of that
// abstraction, and teach us how to use it

// 1
{
  const f = xxs =>
    xxs.reduce(
      ([i, p], xs) => [i + xs.length, [...p, xs.map((_, j) => i + j)]],
      [0, []]
    );

  const input = [[0, 0], [0, 0, 0], [0]];
  const [i, result] = f(input);
  console.log(result);
}

// Now we start refactoring. As is usually the case with these sorts of things,
// things are going to get much worse before they get better

// 2
// Factor the reduction expression and seed into separate variables
{
  const redex = ([i, p], xs) => [
    i + xs.length,
    [...p, xs.map((_, j) => i + j)]
  ];
  const z = [0, []];
  const f = xxs => xxs.reduce(redex, z);

  const input = [[0, 0], [0, 0, 0], [0]];
  const [i, result] = f(input);
  console.log(result);
}

// 3
// Create a curried foldl function
{
  const foldl = f => z => xs => xs.reduce((p, c) => f(p)(c), z);

  const redex = ([i, p]) => xs => [
    i + xs.length,
    [...p, xs.map((_, j) => i + j)]
  ];
  const z = [0, []];
  const f = foldl(redex)(z);

  const input = [[0, 0], [0, 0, 0], [0]];
  const [i, result] = f(input);
  console.log(result);
}

// 4
// Use properties instead of a tuple
{
  const foldl = f => z => xs => xs.reduce((p, c) => f(p)(c), z);

  const redex = ({ i, p }) => xs => ({
    i: i + xs.length,
    p: [...p, xs.map((_, j) => i + j)]
  });
  const z = { i: 0, p: [] };
  const f = foldl(redex)(z);

  const input = [[0, 0], [0, 0, 0], [0]];
  const { i, p } = f(input);
  console.log(p);
}

// TODO: Add some exposition here about deferring selection of initial state

// 5
// Push the initial state out into a parameter
{
  const foldl = f => z => xs => xs.reduce((p, c) => f(p)(c), z);

  const redex = st => xs => i_ => {
    const { i, p } = st(i_);
    return {
      i: i + xs.length,
      p: [...p, xs.map((_, j) => i + j)]
    };
  };
  const z = i => ({ i, p: [] });
  const f = foldl(redex)(z);

  const input = [[0, 0], [0, 0, 0], [0]];
  const { i, p } = f(input)(0);
  console.log(p);
}

// Now let's recognize a particular type of thing called a "state transition"
// :: type StateTransition i p = s -> { i: i, p: p }

// (less verbose alias)
// :: type St = StateTransition

// Notice that the `i => { i, p: [] }` we're passing as the seed for the fold
// above is a state transition; specifically a `StateTransition Int [a]`. It takes
// some integer and produces an array of arbitrary things and another integer

// In this round of refactoring we're not going to change anything, we're just
// going to go around adding type annotations, so we can clearly see where we've
// unwittingly introduced state transitions

// 6
// Annotate everything
{
  // :: (b -> a -> b) -> b -> [a] -> b
  const foldl = f => z => xs => xs.reduce((p, c) => f(p)(c), z);

  // Try validating the type signatures below for yourself and make sure everything
  // lines up
  // :: St Int [Int] -> [Int] -> St Int [Int]
  const redex = st => xs => i_ => {
    const { i, p } = st(i_);
    return {
      i: i + xs.length,
      p: [...p, xs.map((_, j) => i + j)]
    };
  };
  // :: St Int [a]
  const z = i => ({ i, p: [] });
  // :: [[Int]] -> St Int [[Int]]
  const f = foldl(redex)(z);

  // :: [[Int]]
  const input = [[0, 0], [0, 0, 0], [0]];
  // :: { i: Int, p: [[Int]] }
  const { i, p } = f(input)(0);
  console.log(p);
}

// 7
// Factor out some of the array logic
{
  // :: (b -> a -> b) -> b -> [a] -> b
  const foldl = f => z => xs => xs.reduce((p, c) => f(p)(c), z);
  // :: [a]
  const empty = [];
  // :: [a] -> a -> [a]
  const snoc = xs => y => [...xs, y];
  // :: Int -> [Int]
  const range = n => [...Array(n).keys()];

  // :: St Int [Int] -> [Int] -> St Int [Int]
  const redex = st => xs => i_ => {
    const { i, p } = st(i_);
    return {
      i: i + xs.length,
      p: snoc(p)(range(xs.length).map(j => i + j))
    };
  };
  // :: St Int [a]
  const z = i => ({ i, p: empty });
  // :: [[Int]] -> St Int [[Int]]
  const f = foldl(redex)(z);

  // :: [[Int]]
  const input = [[0, 0], [0, 0, 0], [0]];
  // :: { i: Int, p: [[Int]] }
  const { i, p } = f(input)(0);
  console.log(p);
}

// At this point you might be starting to grumble: "some refactoring this is; the snippet
// is now several times as long as when we started!". This is a fair criticism, and I will
// deal with this criticism by simply cheating and claiming that most of this snippet is now
// actually part of a library or module, and no longer part of my snippet

const Arr = {};
// :: (b -> a -> b) -> b -> [a] -> b
Arr.foldl = f => z => xs => xs.reduce((p, c) => f(p)(c), z);
// :: [a]
Arr.empty = [];
// :: [a] -> a -> [a]
Arr.snoc = xs => y => [...xs, y];
// :: Int -> [Int]
Arr.range = n => [...Array(n).keys()];

// I will play this  dirty trick several more times in the course of this gist

// 8
// Let's just update our snippet to leverage our little sleight of hand
{
  // :: St Int [Int] -> [Int] -> St Int [Int]
  const redex = st => xs => i_ => {
    const { i, p } = st(i_);
    return {
      i: i + xs.length,
      p: Arr.snoc(p)(Arr.range(xs.length).map(j => i + j))
    };
  };
  // :: St Int [a]
  const z = i => ({ i, p: Arr.empty });
  // :: [[Int]] -> St Int [[Int]]
  const f = Arr.foldl(redex)(z);

  // :: [[Int]]
  const input = [[0, 0], [0, 0, 0], [0]];
  // :: { i: Int, p: [[Int]] }
  const { i, p } = f(input)(0);
  console.log(p);
}

// 9
// Factor out some combinators for manipulating state transitions
{
  // :: p -> St i p
  const noop = p => i => ({ i, p });

  // :: St i p -> (p -> St i q) -> St i q
  const after = st => f => i_ => {
    // Perform the first transition on the initial state
    const { i, p } = st(i_);
    // Use the resulting value to produce a new state transition
    const st2 = f(p);
    // Run the second state transition on the new state
    return st2(i);
  };

  // :: St Int [Int] -> [Int] -> St Int [Int]
  const redex = st => xs =>
    after(st)(p => i => ({
      i: i + xs.length,
      p: Arr.snoc(p)(Arr.range(xs.length).map(j => i + j))
    }));
  // :: St Int [a]
  const z = noop(Arr.empty);
  // :: [[Int]] -> St Int [[Int]]
  const f = Arr.foldl(redex)(z);

  // :: [[Int]]
  const input = [[0, 0], [0, 0, 0], [0]];
  // :: { i: Int, p: [[Int]] }
  const { i, p } = f(input)(0);
  console.log(p);
}

// Cheat again
const State = {};
// :: p -> St i p
State.noop = p => i => ({ i, p });
// :: St i p -> (p -> St i q) -> St i q
State.after = st => f => i_ => {
  // Perform the first transition on the initial state
  const { i, p } = st(i_);
  // Use the resulting value to produce a new state transition
  const st2 = f(p);
  // Run the second state transition on the new state
  return st2(i);
};

// 10
// Use externalized State things
{
  // :: St Int [Int] -> [Int] -> St Int [Int]
  const redex = st => xs =>
    State.after(st)(p => i => ({
      i: i + xs.length,
      p: Arr.snoc(p)(Arr.range(xs.length).map(j => i + j))
    }));
  // :: St Int [a]
  const z = State.noop(Arr.empty);
  // :: [[Int]] -> St Int [[Int]]
  const f = Arr.foldl(redex)(z);

  // :: [[Int]]
  const input = [[0, 0], [0, 0, 0], [0]];
  // :: { i: Int, p: [[Int]] }
  const { i, p } = f(input)(0);
  console.log(p);
}

// :: (a -> b -> c) -> St i a -> St i b -> St i c
State.combineResults = f => st1 => st2 =>
  State.after(st1)(p1 => State.after(st2)(p2 => State.noop(f(p1)(p2))));

// 11
// Decouple the array result collection from the per item action
{
  // :: [Int] -> St Int [Int]
  const perItemSt = xs => i => ({
    i: i + xs.length,
    p: Arr.range(xs.length).map(j => i + j)
  });

  // :: St Int [Int] -> [Int] -> St Int [Int]
  const redex = prevSt => xs =>
    State.combineResults(Arr.snoc)(prevSt)(perItemSt(xs));
  // :: St Int [a]
  const z = State.noop(Arr.empty);
  // :: [[Int]] -> St Int [[Int]]
  const f = Arr.foldl(redex)(z);

  // :: [[Int]]
  const input = [[0, 0], [0, 0, 0], [0]];
  // :: { i: Int, p: [[Int]] }
  const { i, p } = f(input)(0);
  console.log(p);
}

// TODO: Introduce the concept of applicatives, reveal noop and combineResults are pure and lift2
State.pure = State.noop;
State.lift2 = State.combineResults;

// 12
// Use pure and lift2
{
  // :: [Int] -> St Int [Int]
  const perItemSt = xs => i => ({
    i: i + xs.length,
    p: Arr.range(xs.length).map(j => i + j)
  });

  // :: St Int [Int] -> [Int] -> St Int [Int]
  const redex = prevSt => xs => State.lift2(Arr.snoc)(prevSt)(perItemSt(xs));
  // :: St Int [a]
  const z = State.pure(Arr.empty);
  // :: [[Int]] -> St Int [[Int]]
  const f = Arr.foldl(redex)(z);

  // :: [[Int]]
  const input = [[0, 0], [0, 0, 0], [0]];
  // :: { i: Int, p: [[Int]] }
  const { i, p } = f(input)(0);
  console.log(p);
}

// 13
// Inline redex and z
{
  // :: [Int] -> St Int [Int]
  const perItemSt = xs => i => ({
    i: i + xs.length,
    p: Arr.range(xs.length).map(j => i + j)
  });

  // :: [[Int]] -> St Int [[Int]]
  // prettier-ignore
  const f = Arr.foldl
    (prevSt => xs => State.lift2(Arr.snoc)(prevSt)(perItemSt(xs)))
    (State.pure(Arr.empty));

  // :: [[Int]]
  const input = [[0, 0], [0, 0, 0], [0]];
  // :: { i: Int, p: [[Int]] }
  const { i, p } = f(input)(0);
  console.log(p);
}

// TODO: Exposition, then factor out traverse

Arr.traverse = A => f =>
  Arr.foldl(p => c => A.lift2(Arr.snoc)(p)(f(c)))(A.pure(Arr.empty));

// 14
// Use traverse
{
  // :: [[Int]] -> St Int [[Int]]
  const f = Arr.traverse(State)(xs => i => ({
    i: i + xs.length,
    p: Arr.range(xs.length).map(j => i + j)
  }));

  // :: [[Int]]
  const input = [[0, 0], [0, 0, 0], [0]];
  // :: { i: Int, p: [[Int]] }
  const { i, p } = f(input)(0);
  console.log(p);
}