// trampoline : (thunk -> thunk | value) -> value
// Runs a chain of thunks iteratively so recursion doesn't grow the JS call stack.
// - Start with a "thunk" (a function with no args)
// - While the result is still a function, keep calling it
// - When a non-function value is produced, return it
const trampoline = (thunk) => {
  let t = thunk;
  while (typeof t === "function") t = t(); // keep "bouncing"
  return t; // final value
};

// foldl : (f, acc, xs, k) -> ...
//
// Fold an array xs from left to right in a continuation-passing style (CPS) and
// use trampoline to stay stack-safe.
//
// Type-ish comments:
// - f : (x, acc, k2) => ...
//   where k2 : (newAcc) => ... is a continuation that tells foldl what to do next
//   IMPORTANT: f is expected to call k2(newAcc) rather than directly returning newAcc.
// - k : (finalAcc) => ... is the final continuation invoked at the end.
//
// Returns: a call that eventually triggers k(finalAcc).
const foldl = (f, acc, xs, k) => {
  // step(i, accNow) describes "the rest of the fold" starting at index i
  // and current accumulator accNow.
  //
  // It returns either:
  // - a thunk (function) that when called computes the next step, or
  // - in the base case, a thunk that calls k(accNow).
  const step = (i, accNow) => {
    // Base case: we've processed every element in xs.
    if (i >= xs.length) return () => k(accNow);

    // Process the next element.
    const x = xs[i];

    // We don't call f(x, accNow, ...) immediately on the call stack.
    // Instead, we return a thunk so trampoline can manage the iteration safely.
    return () =>
      // Call f in CPS form:
      // f decides how to compute/update the accumulator, and then calls k2(newAcc).
      f(x, accNow, (newAcc) => {
        // After f computes newAcc, continue folding from i+1.
        // step(i + 1, newAcc) returns a thunk, which trampoline will eventually run.
        return step(i + 1, newAcc);
      });
  };

  // Start the fold at index 0 with the initial accumulator acc.
  // step(0, acc) returns the initial thunk; trampoline runs it to completion.
  return trampoline(() => step(0, acc));
};