Early termination in functional folds a.k.a. reduce
Tags: javascript, functional, tutorial, types
Published: 2021-07-15 20:15:31

---
title: Early termination in functional folds a.k.a. reduce
published: true
description: 
tags: #javascript #functional #tutorial #types
//cover_image: https://direct_url_to_image.jpg
---

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:

```javascript
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:

```javascript
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:

```javascript
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:

```javascript
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](https://github.com/kongware/scriptum).