For loops and accumulating arguments (Solving Problems in Computer Science, ATypcial CompSci)

for_loops.re

/* Imperative for-loop for factorial:
      ---------------------------------
      int factorial(int n)
      int result = 1
      for (int i = 2; i <= n; i = i + 1)
        result = result * i
      return result
   */
/* Transformation of for-loop into recursive function:
   --------------------------------------------------
   for (int i = 2; i <= n; i = i + 1)
     result = result * i

   int i = 2
   while (i <= n)
     result = result * i
     i = i + 1

   int i = 2
   loop:
     if (not(i <= n))
       break
     else
       result = result * i
       i = i + 1
   */
/* Alternatively:
   --------------
   int factorial(int n)
     int result = n
     for (n = n - 1; n > 1; n = n - 1)
       result = result * n
     return result

   */
/* First try */
let rec for_loop = (state_in: 'state): 'state =>
  if (failwith("?base_case")) {
    failwith("?state");
  } else {
    failwith("?some_recursion");
  };

/* Add in keep_going. Remember to negate, for the base case. */
let rec for_loop = (state_in: 'state, keep_going: 'state => bool): 'state =>
  if (!keep_going(state_in)) {
    state_in;
  } else {
    failwith("?some_recursion");
  };

/* This will loop forever: nothing is getting smaller. */
let rec for_loop = (state_in: 'state, keep_going: 'state => bool): 'state =>
  if (!keep_going(state_in)) {
    state_in;
  } else {
    for_loop(state_in, keep_going);
  };

/* Add a loop_body. */
let rec for_loop =
        (
          state_in: 'state,
          keep_going: 'state => bool,
          loop_body: 'state => 'state,
        )
        : 'state =>
  if (!keep_going(state_in)) {
    state_in;
  } else {
    let next_state = loop_body(state_in);
    for_loop(next_state, keep_going, loop_body);
  };

/* Simplify: remove type annotations, only state_in changes */
let for_loop = (state_in /* 1 */, keep_going, loop_body) => {
  let rec do_loop = state_in /* 2 */ =>
    !keep_going(state_in /* 2 */) ?
      state_in /* 2 */ : do_loop(loop_body(state_in /* 2 */));
  do_loop(state_in /* 1 */);
};

/* Now the factorial function */
type state = {
  i: int,
  n: int,
  result: int,
};

let factorial = n => {
  let state = {i: 2, n, result: 1};
  let keep_going = state => state.i < state.n;
  let next_state = ({i, n, result} as state) => {
    ...state,
    i: i + 1,
    result: result * i,
  };
  for_loop(state, keep_going, next_state).result;
};

/* More concisely, using the 'backwards' version */
let factorial = n =>
  snd(
    for_loop((n - 1, n), ((n, _)) => n > 1, ((n, r)) => (n - 1, n * r)),
  );

/* Substitute in for_loop */
let factorial = n =>
  snd(
    {
      let rec do_loop = state_in =>
        if (!(((n, _)) => n > 1)(state_in)) {
          state_in;
        } else {
          do_loop((((n, r)) => (n - 1, n * r))(state_in));
        };
      do_loop((n - 1, n));
    },
  );

/* Move snd to result of do_loop.
   Replace 'state_in' with (n,r). */
let factorial = n => {
  let rec do_loop = ((n, r)) =>
    if (!(((n, _)) => n > 1)((n, r))) {
      (n, r);
    } else {
      do_loop((((n, r)) => (n - 1, n * r))((n, r)));
    };
  snd(do_loop((n - 1, n)));
};

/* Apply functions in if-condition and else-branch. */
let factorial = n => {
  let rec do_loop = ((n, r)) =>
    if (!(n > 1)) {
      (n, r);
    } else {
      do_loop((n - 1, n * r));
    };
  snd(do_loop((n - 1, n)));
};

/* Simplify if-condition and push 'snd' if true-branch. */
let factorial = n => {
  let rec do_loop = ((n, r)) =>
    if (n <= 0) {
      snd((n, r));
    } else {
      do_loop((n - 1, n * r));
    };
  do_loop((n - 1, n));
};

/* Finally, rewrite in a short-form. */
let factorial = n => {
  let rec do_loop = ((n, r)) => n <= 0 ? r : do_loop((n - 1, n * r));
  do_loop((n - 1, n));
};

/* So we see how an accumulating argument can change something like this,
      which evaluates like this
          factorial(3) => 3 * factorial (2)
                       => 3 * (2 * factorial (1))
                       => 3 * (2 * (1 * factorial (0)))
                       => 3 * (2 * (1 * 0))
                       => 3 * (2 * 1)
                       => 3 * 2
                       => 6
   */
let rec factorial = n => n <= 0 ? 1 : n * factorial(n - 1);

/* into something like this
   factorial (3) => do_loop (2, 3)
                 => do_loop(1, 6)
                 => do_loop(0, 6)
                 => 6
   */
let factorial = n => {
  let rec do_loop = ((n, r)) => n <= 0 ? r : do_loop((n - 1, n * r));
  do_loop((n - 1, n));
};

/* Try using for_loop to compute sum or fibonacci numbers.
   Then expand that definition to get a specialised function like shown above.
   */
let sum_1_to = n => {
  let extract = failwith("?extract");
  extract(
    for_loop(
      failwith("?initial_state"),
      failwith("?keep_going"),
      failwith("?loop_body"),
    ),
  );
};

let fibonacci = n => {
  let extract = failwith("?extract");
  extract(
    for_loop(
      failwith("?initial_state"),
      failwith("?keep_going"),
      failwith("?loop_body"),
    ),
  );
};

/* Try making a new for_loop function that builds in the extract function:
      for_loop_with_extract(state_in, keep_going, extract, loop_body)
   What is the type of extract?
   */
let for_loop_with_extract = failwith("?for_loop_with_extract");