31

# 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.

31