Early termination in functional folds a.k.a. reduce

Preface: This post is based on a dynamically typed version of Javascript called scriptum, i.e. vanilla Javascript with explicit type annotations.

In imperative programming special constructs like break are used to programmatically terminate a loop before the underlying data structure is exhausted.

The functional counterpart of loops is recursion, but since recursion is a functional primitive we try to avoid it using folds as a more appropriate abstraction.

In lazy evaluated languages the special fold scanl, which stores all intermediate results of a computation, suffices. But in eagerly evaluated Javascript we must use another approach that includes local continuations:

const foldk = fun(
  f => init => xs => {
    let acc = init;

    for (let i = 0; i < xs.length; i++)
      acc = f(acc) (xs[i]).run(id);

    return acc;
  },
  "(b => a => Cont<b, b>) => b => [a] => b");

foldk looks pretty convoluted, but the type annotation alleviates the cognitive load:

  "(b => a => Cont<b, b>) => b =>         [a] =>          b"
// ^^^^^^^^^^^^^^^^^^^^^^    ^            ^^^             ^
//           |               |             |              |
//  2-argument-function   b-value  array-of-a-values   b-value
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ => ^^^^^^^^^^
//                      |                             |
//                  arguments                       result

It takes three arguments, a binary function, a value, an array of values and returns a value. a and b are placeholders for values of optionally different types.

We haven't discussed the most complicated part of the type though. The binary function b => a => Cont<b, b> returns a continuation. Luckily this is the only place where continuations appear, that is to say we only need to wrap the result of our binary function into Cont. This doesn't sound too hard.

So what is a continuation? Nothing more than a (partially applied) function with a function argument as its last formal parameter. So inck is not a continuaion, but inck(2) is:

const inck = n => k => k(n + 1);
//                ^^^^^^^^^^^^^
//                      |
//                 continuation

const continuation = inck(2);
continuation(x => x); // 3

With scriptum we don't use the bare continuation but put it into a type wrapper Cont(k => k(n + 1)). In order to access the continuation inside the wrapper, scriptum supplies the .run method.

Now that we clarified this let's come back to the original task to terminate from a fold programatically in order to see how foldk is applied in practice:

foldk(fun(
  x => s => Cont(fun(
    k => x >= 5
      ? x // A
      : k(x + s.length), // B
    "(Number => Number) => Number")),
  "Number => String => Cont<Number, Number>"))
  (0) (["f","fo","foo","fooo","foooo"]); // 6

In line B we call the continuation k, i.e. the folding proceeds as usual. In line A, however, we just return the intermediate result without calling k. The folding is short circuited. The above computation calculates "f".length + "fo".length + "foo".length and then terminates the program due to the programatic reason that x >= 5 yields true.

So far we haven't leveraged scriptum's runtime type system. We will use the ANNO symbol to access the intermediate types of each function application:

foldk[ANNO]; // (b => a => Cont<b, b>) => b => [a] => b

result = foldk(fun(
  x => s => Cont(fun(
    k => x >= 5
      ? x // A
      : k(x + s.length), // B
    "(Number => Number) => Number")),
  "Number => String => Cont<Number, Number>"));

result[ANNO]; // Number => [String] => Number

result = result(0)
result[ANNO]; // [String] => Number

result(["f","fo","foo","fooo","foooo"]); // 6

Hopefully, this little sketch gives a first insight how thinking in FP looks like and how type annotation can assist us in finding reliable solutions.

scriptum is published on Github.