Forem: Iven Marquardt

The three kinds of effects in programming

Iven Marquardt — Wed, 20 Dec 2023 14:43:18 +0000

Effects can be distinguished in three categories:

control flow effects
mutations
input/output

Control Flow

Control flow effects have their manifestations in data types:

indeterministic control flow: Array/List
computation without a result value: null
unavoidable exception: Error
short circuit: break/continue

The problem with imperative programming is that these data types are partly insufficient to encode their corresponding control flow:

Array provides an indeterministic choice but if this choice changes, you need to mutate the array or endure a performance penalty
null merely indicates the lack of a result value but offers no means to avoid further processing
Error entails the same problems as null and only works with try/catch statements, the next generation goto
break/continue are no expressions but special nullary operators tied to their special constructs

From a functional perspective, these types are more or less harmful. FP uses algebraic data types, continuations and monads to solve shortcomings in the imperative world.

Mutations

Mutations alter existing program state observably and destructively during the runtime of a program.

They are a side effect that puts a constraint on evaluation order, i.e. order matters even when it doesn't have to. It also hampers idempotent functions. This may lead to non-intuitive program behavior and renders optimization/refactoring harder.

Functional programming uses tree structures to realize persistent data types with structural sharing.

I/O

You cannot ignore the real world, even with functional programming. If you rely on input and output and you do if your program should to achieve something useful, side effects are inevitable.

The trick is to separate the pure description of effects from their execution:

const Cont = k => {
  const o = {run: k};
  return o;
};

Cont.map = f => tx =>
  Cont(k => tx.run(x => k(f(x))));

Cont.and = tx => ty =>
  Cont(k =>
    tx.run(x =>
      ty.run(y =>
        k([x, y]))));

const sqr = x => x * x;

// database mocks

const tw = Cont(k => new Promise((res, rej) => res(k(3)))),
  tx = Cont(k => new Promise((res, rej) => res(k(5))));

const ty = Cont.map(sqr) (tw),
  tz = Cont.map(sqr) (tx);

const data = Cont.and(ty, tz);

// ^^^ pure ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

data.run(data => { // data yields [9, 25]
  // impure scope
});

Only in the impure scope you can observe the result value of running the effect. Everything else is pure.

Pure and impure scopes are separated and effect execution is deferred by conducting it inside the last continuation of the program, namely data => { // impure scope }.

Cont builds up a nested deferred function call tree. Functional programming thus only utilizes tree data structures and continuations to handle all three effect classes.

Monads naturally arise from continuations

Iven Marquardt — Tue, 19 Dec 2023 16:28:01 +0000

A function const id = x => x becomes a continuation passing style function in Javascript as soon as you add a function argument and call it with the result value in tail position: const id_ = x => k => k(x). The actual continuation emerges when you apply the CPS function: id_(2) yields const id2 = k => k(2), the continuation.

You can compose normal functions with const comp = f => g => x => f(g(x)) and then comp(id) (id). But can you compose continuations like id2 as well?

// doesn't work, cont2 returns a value but cont expects a fun
const comp_ = cont => cont2 => k => cont(cont2(k));

// works but x is awkwardly discarded
const comp_ = cont => cont2 => k => cont2(x => cont(y => k(y));

Unfortunately, no. There is no specialized comp_ operator for id2 to compose two continuations in a general way. But there is a way to compose the CPS version id_ with its continuation id2:

const comp_ = cont => cps => k => cont(x => cps(x) (k));
const f = comp_(id2) (id_);
f(id); // yields 2 since we are only composing identity

comp_ a.k.a. chain/bind is one part of the monad interface. The second one is const of = x => k => k(x), which simply puts a normal value into the monad context:

const chain = cont => cps => k => cont(x => cps(x) (k));
const of = x => k => k(x);
const f = chain(of(3)) (id_);
f(id); // yields 3

So not just the continuation monad but monads of all types are just the most general way to compose/chain expressions of those types using continuations under the hood. Please note that monads are a very generalized and thus subtle concept. Stare at it long enough, play with it once in a while and you'll eventually get it.

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

Iven Marquardt — Thu, 15 Jul 2021 20:15:31 +0000

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.

Enjoying an Haskell like Type System in Javascript

Iven Marquardt — Tue, 25 May 2021 18:30:10 +0000

scriptum is a type validator and a functional library build upon it. A type validator is distinguished by a static type checker like Typescript by operating at runtime. Besides it doesn't infere types from terms but only checks applications.

Doing without type inference sounds like a silly idea but fortunately the validator can resort to Javascript's introspection means, so the developer only has to annotate function types.

Technically speaking scriptum is based on the Hindler-Milner type system extended by higher-kinded/rank types and row polymorphism.

A runtime type system can never attain the soundness of a static one. You can think of it more as a tool for gradual typing. Here is a complex, real world example that should give an intuition how expressive this approach is.

Javascript is modeled around the idea of mutations. Mutations are not bad per se but sharing this side effect causes harm. Mutable represents a data type that helps to tame mutations by keeping them local by design. I am going to introduce the untyped version first, so that you can comprehend its functionality without distraction.

In order to understand the Mutable constructor we first need to understand the _let combinator for local bindings, which is used in the implementation. It is like a let declaration but as a fist class expression and with its own scope. You can consider _let as a more readable IFFE:

const _let = (...args) => ({in: f => f(...args)});
_let(2, 3).in((x, y) => x + y); // 5

Mutable provides an interface to construct values which can be safely updated in-place. The underlying idea is to hide the mutations inside the Mutable wrapper until the wrapped value is actually consumed. Once consumed no more in-place updates are possible.

const Mutable = clone => ref => {
  return _let({}, ref).in((o, ref) => {
    let mutated = false;

    o.consume = () => {
      if (mutated) {
        delete o.consume;
        delete o.update;

        o.consume = fun(() => ref, "_ => t<a>");

        o.update = _ => {
          throw new TypeError(
            "illegal in-place update of consumed data structure");
        };
      }
      return ref;
    };
    o.update = k => {
      if (!mutated) {
        ref = clone(ref); // copy once on first write
        mutated = true;
      }
      k(ref); // use the effect but discard the result
      return o;
    };
    return (o[Symbol.toStringTag] = "Mutable", o);
  });
};

const arrClone = xs => xs.concat(),
  arrPush = x => xs => (xs.push(x), xs);

const mutableArr = Mutable(arrClone),
  foo = mutableArr([1, 2, 3]);

foo.update(arrPush(4))
  .update(arrPush(5))
  .consume(); // [1, 2, 3, 4, 5]

foo.update(arrPush(6)); // type error

Mutable essentially prevents us from sharing mutated values at different places in the code and thus alleviates the peril of unexpected side effects.

One issue remains though. arrMutable doesn't give us any guarantee that the updated value is still of type [Number] after a mutation. It could just as well be [String] or even Set<Boolean>. This is the moment when the type validator comes into play. But how do we make the composite type with its pretty complex interface type safe?

Here is the necessary main annotation,

`{}, t<a> => Mutable {
  consume: (_ => t<a>),
  ·update: ((t<a> => t<a>) => this*)
}`

(· denotes a safe space so that you can actually indent type annotations as demonstrated above)

which reads: Mutable is a function that takes two arguments, an empty object {} and the actual mutable type t<a>. It returns a Mutable object with two properties consume and update.

consume expects a thunk (a function without arguments) that returns the mutable type.

update is a bit more involved. It expects a function that takes another function t<a> => t<a> and returns the object to be constructed. this* indicates a self-reference at the type level. The function argument t<a> => t<a> takes the mutable value and gives back the updated value of the same type.

t<a> is a higher kinded type, better known as generics in Typescript, which takes another generics as an argument. The type ensures that only mutable composite values are passed to the constructor.

As Mutable is a composite type we need to annotate the methods consume and update as well. Moreover, we need to connect the inner types with the outer one. Please note that Mutable is a quite advanced type which requires some additional plumbing. Usually you don't need the extra step.

Here is the complete implementation from the scriptum library:

const Mutable = clone => ref => {
  return _let({}, ref).in(fun((o, ref) => {
    const anno = CHECK ? introspectDeep(ref) : "";
    let mutated = false;

    o.consume = fun(() => {
      if (mutated) {
        delete o.consume;
        delete o.update;
        o.consume = fun(() => ref, `_ => ${anno}`);

        o.update = _ => {
          throw new TypeError(
            "illegal in-place update of consumed data structure");
        };
      }

      return ref;
    }, `_ => ${anno}`);

    o.update = fun(k => {
      if (!mutated) {
        ref = clone(ref); // copy once on first write
        mutated = true;
      }

      k(ref); // use the effect but discard the result
      return o;
    }, `(${anno} => ${anno}) => Mutable {
      consume: (_ => ${anno}),
      ·update: ((${anno} => t<a>) => this*)
    }`);

    return (o[TAG] = "Mutable", o);
  }, `{}, t<a> => Mutable {
    consume: (_ => t<a>),
    ·update: ((t<a> => t<a>) => this*)
  }`));
};

const arrClone = fun(
  xs => xs.concat(),
  "[a] => [a]");

const arrPush = fun(
  x => xs => (xs.push(x), xs),
  "a => [a] => [a]");

As you can see types and functions are associated with the fun combinator.

Now we can safely assume for our example that t<a> is always an array of numbers:

const arrForEach = fun(
  f => xs => (xs.forEach((x, i) => xs[i] = f(x)), xs),
  "(a => b) => [a] => [b]");

const numToStr = fun(
  n => n.toString(),
  "Number => String");

foo.update(arrPush(4))
  .update(arrPush(5))
  .update(arrForEach(numToStr)); // type error

Hopefully, this brief introduction gave you a rough idea how the type validator can assist your coding. We've just scratched the surface!

scriptum on GitHub

You Might not Need Immutability - Safe In-Place Updates

Iven Marquardt — Fri, 25 Dec 2020 19:59:10 +0000

[Editor's note: see edit at the bottom]

What makes destructive/in-place updates of mutable values like Array or Map harmful? First of all, they represent a side effect, that is an implicit process not directly evident from the code. We should always strive for expressing our intentions explicitly.

Moreover reference values can be shared by copying the reference with the consequence that side effects may pop up throughout the application, causing race conditions and other unexpected behavior.

So why bother using in-place updates at all? Well, they can lead to quite performant and intuitive algorithms in certain scenarios. The question is rather whether there is a way to benefit from these attributes without jeopardizing the application's predictability and maintainability.

As it turns out we can. All it takes is a special data type which decouples mutable values from the global scope and rules out reference sharing. Here is a first implementation of such a generic type:

const record = (type, o) =>
  (o[Symbol.toStringTag] = type.name || type, o);

const app = f => x => f(x);

const Mutable = clone => refType =>
//     clonable ^^^^^ constraint
  record(Mutable, app(([o, refType]) => {
    o.mutable = {
      run: k => {
//         ^ continuation (A)

        // rule subsequent calls out
        o.mutable.run = _ => {
          throw new TypeError("illegal subsequent inspection");
        };

        // rule subsequent calls out
        o.mutable.set = _ => {
          throw new TypeError("illegal subsequent mutation");
        };

        return k(refType);
//             ^^^^^^^^^^ call-at-most-once semantics (B)
      },

      set: k => {
//         ^ continuation (A)
        k(refType);
//      ^^^^^^^^^^ call-any-number-of-times semantics (B)
// but discard the result (C)
        return o;
      }
    }

    return o;
  }) ([{}, clone(refType)]));

Mutable takes two arguments, the mutable value refType we want to perform in-place operations on and a function clone that knows how to create a shallow copy of this value. A shallow copy is necessary to decouple refType from the parent scope, which narrows the scope where the mutations are actually observable.

Next we create two closures run and set wrapped in an object, which each hold the mutable value as a free variable and expect a continuation (B), which is the only means to interact with this value. The first closure allows us to inspect refType, whereas the second one merely performs mutations on it while discarding the result, because it is only interested in the side effects.

By the way, a continuation is just a partially applied function with a function argument as its last formal paramter:

const inck = x => k => k(x + 1);
//                ^^^^^^^^^^^^^ this is the continuation

By using continuations we turn the usual call mechanism upsite down: Instead of passing a value to a function we pass it the other way around. By relying on this mechanism the run/set closures are able to completely control how k is applied to the mutable value and what happens with the result. It is the prerequisite for modelling functions with call-at-most-once (run) and call-any-number-of-times (set) semantics respectively in Javascript.

Now we can perform as many in-place updates as we want (via set), but only until a function in our application inspects the mutable value (via run). Once inspected the value is owned by this function and can neither be inspected again nor be further updated. I borrowed the ownership concept from the extraordinary Rust language, where it is implemented on the language level in a way more sophisticated manner.

Enough with the theory though. Let's take a look at two examples to see how Mutable works in practice:

const reduce = f => init => xs =>
  xs.reduce((acc, x) => f(acc) (x), init);

const concat = xs => ys => // performs in-place updates
  (xs.push.apply(xs, ys), xs);

const flatten = reduce(
  acc => xs => concat(acc) (xs)) ([]);

const xss = [[1], [2, 3], [4], [5]];

flatten(xss); // [1, 2, 3, 4, 5]
flatten(xss); // [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]

run code

This is a contrived, simple example and yet it is not easy for the untrained eye to pick up the side effect leak. Let's see what happens if we encode this computation with our new Mutable type:

// Mutable combinators
const mutRun = k => o =>
  o.mutable.run(k);

const mutSet = k => o =>
  o.mutable.set(k);

const arrClone = xs =>
  xs.concat();

const MutableArr = Mutable(arrClone);

// adapted computation from the first example

const reduce = f => init => xs =>
  mutRun(id)
//^^^^^^ inspect the mutable value once (C)
    (xs.reduce((acc, x) =>
      f(acc) (x), MutableArr(init)));
//  make in-place ^^^^^^^^^^ updates explicit (A)

const concat = xs => ys =>
  mutSet(xs_ =>
//^^^^^^ perform any number of in-place updates on the mutable value (B)
    (xs_.push.apply(xs_, ys), xs_)) (xs);

const flatten = reduce(concat) ([]);

// MAIN

const xss = [[1], [2, 3], [4], [5]];

flatten(xss); // [1, 2, 3, 4, 5]
flatten(xss); // [1, 2, 3, 4, 5]

run code

As you can see the problem just vanished and this holds not only for this specific case but for the entire error class. Let's go through the necessary transformation. It is a pretty mechanical process:

identify the mutable value and wrap it with Mutable (A)
use the mutSet combinator to perform as many in-place updates on this mutable value as you need (B)
use the mutRun combinator to inspect the mutable value once at the boundary of your impure computation (C)

Inspecting the mutable value with mutRun(id) just means that we are only interested in the reference itself, instead of looking up an element or retrieving the length.

The seasoned functional programmer might be concerned why the in-place updates rely on strict evaluation? They are right, it should be non-strict but for the sake of simplicity I leave it as is at this point.

With the next exmaple we are going to trigger a couple of error messages which may give an insight of Mutable's proper use:

// Map instance

const mapClone = m =>
  new Map(m);

const MutableMap = Mutable(mapClone);

const mapSet = k => v => m =>
  mutSet(m_ => m_.set(k, v)) (m);

const mapUpd = k => f => m =>
  mutSet(m_ =>
    m_.has(k)
      ? m_.set(k, f(m_.get(k)))
      : m_) (m);

const mapGet = k => m => m.get(k);

// MAIN

const m = MutableMap(new Map());

mapSet("foo") (1) (m); // in-place update
mapSet("bar") (5) (m); // in-place update
mapUpd("bar") (x => x * x) (m); // in-place update

const m_ = mutRun(id) (m); // inspection

console.log(m_); // Map(foo: 1, bar: 25)

// you must not perform further mutations from now on

try {mapSet("foo") (1) (m)}
catch (e) {console.log(e.message)}

// you must not perform further inspections from now on

try {mutRun(m => m.size) (m)}
catch (e) {console.log(e.message)}

run code

The principles should be clear now.

We haven't covered race conditions yet. Let's see how Mutable can help alleviating the problem:

// auxiliary functions

const delayf = f => ms => x =>
  new Promise((res, rej) => setTimeout(x => {
    try {return comp(res) (f) (x)}
    catch (e) {return rej(e.message)}
  }, ms, x));

const comp = f => g => x => f(g(x));

const id = x => x;

const arrClear = xs =>
  xs.length = 0;

const arrHead = ([x]) => x;

const sqr = x => x * x;

// MAIN

const xs = [3, 4, 5],
  ms = Math.round(Math.random() * 100);

const foo = delayf(comp(sqr) (arrHead)) (25);

const bar = delayf(arrClear) (ms); // unsafe in-place update

foo(xs).then(x =>
  console.log(
    `foo retrieved head from [${xs}] and evaluated to ${x} after 25ms`));
//    will eventually log [] ^^^^^^^          and NaN ^^^^
bar(xs).then(x =>
  console.log(`bar cleared array after ${ms}ms`));

run code

If you run the program often enough you will eventually reproduce the race condition. Imagine what a nightmare race conditions may evolve into in larger codebases.

Here is the same application encoded with Mutable:

// auxiliary functions

const delayf = f => ms => x =>
  new Promise((res, rej) => setTimeout(y => {
    try{comp(res) (f) (y)}
    catch (e) {rej(e.message)}
  }, ms, x));

const sqr = x => x * x;

// MAIN

const xs = MutableArr([3, 4, 5]),
  ms = Math.round(Math.random() * 100);

const foo = delayf(comp(sqr) (mutRun(arrHead))) (25);

const bar = delayf(arrClear) (ms); // safe in-place update

foo(xs).then(x =>
  console.log(`foo retrieved head from MutableArr
  and evaluated to ${x} after 25ms`));
//                 ^^^^ will either log NaN...

bar(xs)
  .then(x => console.log(`bar cleared array after ${ms}ms`))
  .catch(e => console.log(`bar triggered exception "${e}"`));
//   ...or trigger an "illegal subsequent mutation" ^^^^ error

run code

How is this any different from the previous example? Unfortunately Mutable doesn't provide a strong enough guarantee to avoid race conditions from occurring in the first place. This isn't Rust after all. But at least the type produces immediate errors, either NaN or TypeErro("illegal subsequent mutation") in the example above. While Mutable doesn't save us from race conditions altogether, it helps us detecting them.

You can think of Mutable as kind of interpreter that assists you in creating exclusively safe in-place updates. It is a bit of a pain in the neck to be honest. But if you think it over you might come to the conclusion that a type yelling at you on unsafe mutations is way better than pinpointing subtle bugs caused by unleashed side effects.

[EDIT]
Mutable's implementation is too strict. It has a copy-exactly-once-then-write semantics but should have copy-at-most-once-on-first-write. Additionally a variant is needed that only copies if the mutable value is actually needed, i.e. consumed.

You can see the current implementation as part of the scriptum library on Github.

Handling Folds that require non-empty data structures

Iven Marquardt — Sun, 29 Nov 2020 13:06:58 +0000

Some folds (aka reduce) don't include an accumulator or initial value and thus require a non-empty foldable data structure, a variadic maxn fold for instance. Such folds come along with two issues though.

The first issue concerns the type. With reduce we can express asymetric types, because the accumulator can have a different type than the elements of the Foldable, e.g. we can reduce [Number,Number,Number] to String. Without an accumulator we can only express symetric types.

The second issue concerns the case when we pass an empty data structure. Without an accumulator there is nothing to return. We can through an error what would render the function partial.

Here is a fold for non-empty Foldable types that solves both issues in a clean functional way:

const arrFold1 = f => g => xs => {
//                    ^ A
  let acc;

  if (xs.length === 0)
    return None;
//         ^^^^ B

  acc = g(xs[0]);

  for (let i = 1; i < xs.length; i++)
    acc = f(acc) (xs[i], i);

  return Some(acc);
//       ^^^^^^^^^ B
};

const maxn = ({fold1, max}) => tx =>
  fold1(x => y =>
    max(x) (y)) (x => x) (tx);

const numMax = m => n =>
  n > m ? n : m;

maxn({fold1: arrFold1, max: numMax})
  ([1,2,30,4,5,6]); // Some(30)

maxn({fold1: arrFold1, max: numMax})
  ([]); // None

run code

Instead of an accumulator arrFold1 expects an unary function (A) that may or may not transform the first element's type. If an empty structure is provided, it returns None and Some(a) (B) otherwise.

This mimplementation is part of the scriptum FP lib

Turn non-algebraic, imperative arrays into a monad transformer

Iven Marquardt — Tue, 17 Nov 2020 11:59:24 +0000

Turns out that although JS arrays are not algebraic, you can implement a transformer-like type ArrayT m a = m (Array (m a)). It behaves like a transformer & adheres to the monad laws for many m but there are no guarantees that this holds for all m:

// ARRAYT

const arrFoldT = chain => f => init => mmx =>
  chain(mmx) (mx => {
    const go = (acc, i) =>
      i === mx.length
        ? acc
        : chain(mx[i]) (x =>
            go(f(acc) (x), i + 1))

    return go(init, 0);
  });

const arrAppendT = ({chain, of}) => mmx => mmy =>
  arrFoldT(chain)
    (acc => x =>
      chain(acc) (acc_ =>
        of(arrSnoc(of(x)) (acc_)))) (mmx) (mmy);

const arrChainT = ({chain, of}) => mmx => fmm =>
  arrFoldT(chain)
    (acc => x =>
      arrAppendT({chain, of}) (acc) (fmm(x)))
        (of([]))
          (mmx);

const arrOfT = of => x => of([of(x)]);

// OPTION

const Option = union("Option");

const None = Option("None", {});

const Some = some => Option(Some, {some});

const optChain = mx => fm =>
  match(mx, {
    None: _ => None,
    Some: ({some: x}) => fm(x)
  });

const optOf = x => Some(x);

// OPTARR

const optArrChain = arrChainT({chain: optChain, of: optOf});

const optArrOf = arrOfT(optOf);

// MAIN

const mmw = Some([Some(1), Some(2), Some(3)]),
  mmx = Some([Some(1), None, Some(3)]),
  mmy = Some([Some(1), Some(0), Some(3)]),
  mmz = None;

const main = optArrChain(mmw) (x => optArrOf(x * x)),
  main2 = optArrChain(mmx) (x => optArrOf(x * x)),
  main3 = optArrChain(mmx) (x => x === 0 ? None : optArrOf(x * x)),
  main4 = optArrChain(mmz) (x => optArrOf(x * x));

main;  // Some([Some(1), Some(4), Some(9)])
main2; // None
main3; // None
main4; // None

You can find a running example on repl.

Abstracting From Nested Monadic Computations w/o Do-Notation

Iven Marquardt — Mon, 02 Nov 2020 20:21:04 +0000

As soon as we work with monads in Javascript we wind up with nested monadic computations, because there is no do-notation as in Haskell or multi-prompt coroutines as in Kotlin. We cannot use generators either, because they are insufficient for the job.

So are we stuck with nested monadic computations in an ad-hoc fashion like the following?

// Monad

const arrChain = mx => fm =>
  arrFold(acc => x =>
    arrAppend(acc) (fm(x))) ([]) (mx);

// auxiliary function

const arrFold = f => init => xs => {
  let acc = init;

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

  return acc;
};

const arrAppend = xs => ys =>
  xs.concat(ys);

// MAIN

const main = arrChain([1,2]) (x => // nested monadic computation
  arrChain([3,4]) (y =>
    arrChain([5,6]) (z =>
      x === 1
        ? []
        : [x, y, z])));

main; // [2,3,5,2,3,6,2,4,5,2,4,6]

Actually, there is a small improvement. We can treat monadic actions like applicative functors by wrapping them in the context of their corresponding monad:

// Monad

const chain3 = chain => tx => ty => tz => fm =>
  chain(chain(chain(tx) (x => fm(x)))
    (gm => chain(ty) (y => gm(y))))
      (hm => chain(tz) (z => hm(z)));

// MAIN

const main = chain3(arrChain) // much more readable
  ([1,2])
  ([3,4])
  ([5,6])
    (x => x === 1
      ? []
      : [y => [z => [x, y, z]]]);

main; // [2,3,5,2,3,6,2,4,5,2,4,6]

run code

Given chain3 we can implement other arity aware combinators and overload them inside a variadic chainn to gain more flexibility.

More on this and other FP topics in my course for FP in JS:
A fool's scriptum on functional programming.

When you think your functional code is stack safe

Iven Marquardt — Sun, 04 Oct 2020 14:29:24 +0000

Recursion is a functional primitive and thus we try to avoid it, because ultimately it is only a nasty imperative loop in disguise. In FP we usually use folds and only resort to recursion if folding is not expressive enough.

In Javascript we additionally need to take care of stack-safety. It is therefore a smart strategy to implement folds with specific trampolines suitable for each type:

// Foldable

const arrFold = f => init => xs => {
  let acc = init;

  for (let i = 0; i < xs.length; i++) // trampoline
    acc = f(acc) (xs[i], i);

  return acc;
};

// identity

const id = x => x;

// function composition

const comp = f => g => x => f(g(x));

const compn = arrFold(comp) (id); // variadic

// MAIN

const inc = x => x + 1;

compn([inc, inc, inc, inc, inc]) (0); // 5

run code

You may think yourself safe with arrFold being implemented as a stack-safe trampoline. However, you are not:

// MAIN

const inc = x => x + 1;

const xs = Array(1e5).fill(inc);

const foo = compn(xs); // still okay

foo(0); // stack overflow

run code

Composing means to combine two functions to a description of a new function, which is only evaluated if the required argument is provided. So iteratively composing builds up a huge description of descriptions waiting to be run.

What can we do about it? We need a way to break the composition apart. We've already used trampolines. It seems to be the proper tool:

// trampoline for deferred function call trees

const postRec = f => (...args) => {
  let step = f(...args);

  while (step.tag !== "Base")
    step = f(...step.args);

  return init => {
    let {f, x} = step.x(init);

    while (step = f(x)) {
      if (step && step.tag === "Call") {
        step = step.f(step.x);

        if (step && step.tag === "Call") {
          ({f, x} = step);
          continue;
        }

        else break;
      }

      else break;
    }

    return step;
  }
};

const Base = x =>
  ({tag: "Base", x});

const Call = f => x =>
  ({tag: "Call", f, x});

const Step = (...args) =>
  ({tag: "Step", args});

// function composition

const comp = f => g => x => f(g(x));

const compn = xs => // variadic
  postRec((i, acc) =>
    i === xs.length
      ? Base(acc)
      : Step(i + 1, Call(comp(acc) (xs[i]))))
        (0, Call(id));

// MAIN

const inc = x => x + 1;

const xs = Array(1e5).fill(inc);

compn(xs) (0); // 100000

run code

postRec isn't a beauty. It reveals all its ugly operational semantics. Javascript was never about beauty but to get things done, I guess.

Anayway, in FP we often have to deal with descriptions of computations that create huge deferred function call trees. Having a specialized trampoline at our disposal allows us to get serious about FP in JS.

If you want to learn more about FP in JS take a look at my course on Github.

How to fold a string in Javascript?

Iven Marquardt — Tue, 15 Sep 2020 12:59:14 +0000

A naive functional implementation would look like this:

const strFold = f => acc => ([head, ...tail]) =>
  head === undefined
    ? acc
    : strFold(f) (f(acc) (head)) (tail);

const countVowels = n => x =>
  "aoiue".search(x) === -1
    ? n
    : n + 1;

strFold(countVowels) (0) ("hello"); // 2

run code

However, this is neither stack-safe nor does it utilize the special trait of Javascript strings: They are different from arrays.

We don't want to consume each character one by one but chunks with any number of characters. Hence our string fold should rely on regular expressions. Let's do this:

const strFoldChunk = rx => f => acc => s => {
  const ry = new RegExp( // clone
    rx.source,
    rx.flags[0] !== "g"
      ? "g" + rx.flags
      : rx.flags);

  let r, acc_ = acc;

  while (r = ry.exec(s)) { // implicit local mutation by exec
    acc_ = f(acc_) (r[0]);
  }

  return acc_;
};

const strMatchAll = rx =>
  strFoldChunk(rx)
    (x => y => x + y)
      ("");

const strMatchLast = rx => s =>
  strFoldChunk(rx)
    (_ => x => x)
      ("")
        (s);

strMatchAll(/a\d/) ("aaa1a2a3a4a5"); // "a1a2a3a4a5"
strMatchLast(/a\d/) ("aaa1a2a3a4a5"); // "a5"

run code

We managed to consume chunks of characters and additionally abstracted from recursion with stack-safe folds. This is promising.

However, on second thoughts we cannot derive strMatch or strMatchNth from strFoldChunk efficiently, because this would need the folding to stop at the 1st or nth element. A fold has run to completion semantics, though. It traverses the entire structure.

Let's take another step and introduce lazy evaluated right folds. Please note that the thunk function creates a value that is not evaluated until it is needed by a computation. If thunk is evaluated once, the result is stored and reused for further accesses. Here is the implementation:

const strict1 = thunk =>
  thunk && thunk[THUNK]
    ? thunk.valueOf()
    : thunk;

const thunk = f =>
  new Proxy(f, new ThunkProxy());

// simplyfied version

class ThunkProxy {
  constructor() {
    this.memo = undefined;
  }

  get(g, k) {
    if (this.memo === undefined) {
      this.memo = g();

      while (this.memo && this.memo[THUNK])
        this.memo = this.memo.valueOf();
    }

    if (k === THUNK)
      return true;

    else if (k === Symbol.toPrimitive)
      return this.memo[Symbol.toPrimitive];

    else if (k === "valueOf")
      return () => this.memo;

    else return this.memo[k];
  }
}

const THUNK = "thunk";

const union = type => (tag, o) =>
  (o[type] = type, o.tag = tag.name || tag, o);

const match = (tx, o) =>
  o[tx.tag] (tx);List = union("List");

const Nil = List("Nil", {});

const Cons = head => tail =>
  List(Cons, {head, tail});

const strFoldChunkr = rx => f => acc => s => {
  const ry = new RegExp( // clone
    rx.source,
    rx.flags[0] !== "g"
      ? "g" + rx.flags
      : rx.flags);

  const go = r =>
    r === null
      ? Cons(acc) (NIL)
      : f(r[0]) (thunk(() => go(ry.exec(s))));

  return go(ry.exec(s));
};

const listFoldr = f => acc => xs => {
  const go = (xs, i) =>
    match(xs, {
      Nil: _ => acc,
      Cons: ({head, tail}) => f(head, i) (thunk(() => go(tail, i + 1)))
    });

  return go(xs, 0);
};

const strMatch = rx => s =>
  strFoldChunkr(rx)
    (Cons)
      ("")
        (s).head;

const strMatchNth = rx => n => s =>
  listFoldr((head, i) => tail =>
    i === n
      ? head
      : strict1(tail)) // explicitly encforce evaluation
        ("")
          (strFoldChunkr(rx)
            (Cons)
              ([])
                (s));

strMatch(/a\d/) ("aaa1a2a3a4a5"); // "a1"
strMatchNth(/a\d/) (2) ("aaa1a2a3a4a5"); // "a3"

run code

I know, this implementation is a bit more involved. Lazy evaluation is hard to understand, if you are unfamiliar with the concept. Basically the algorithm stops as soon as the criterion (evaluated the 1st and nth element respectively) is reached. The lazy behavior resembles short circuiting in a eagerly evaluated languages.

We successfully managed to push the limits of Javascript and this is only the beginning. Much more is possible.

Lil' functional auxiliary helpers: `thisify`

Iven Marquardt — Thu, 09 Jul 2020 12:02:29 +0000

If you want a self-referencing object in an ad-hoc manner you should meet thisify:

const thisify = f => f({});

const comp = f => g => x => f(g(x));
const log = prefix => x => (console.log(prefix, x), x);
const sqr = x => x * x;

const foo = thisify(o => {
  o.bar = 5;

  o.once = op => {
    const memo = op(o.bar);
    o.once = _ => memo;
    return memo;
  }

  return o;
});

foo.once(comp(log("logs")) (sqr)); // logs 25 + yields 25
foo.once(comp(log("logs")) (sqr)); // yields 25

run code

f => f({}) is all it takes to mimic Javascript's this.

FP serves the most delicious abstractions

Iven Marquardt — Fri, 29 May 2020 10:59:55 +0000

For instance, if we try to combine two composed applicatives of type Task<Option<number[]>, E> - an async computation that may fail or yields any number of numbers - it gets pretty soon pretty ugly:

// tAp/tMap     = Task functor/applicative
// optAp/optMap = Option functor/applicative
// arrAp/arrMap = Array functor/applicative
// tttx         = Task(Some([1,2,3]));
// ttty         = Task(Some([10,20,30]));

tAp(
  tMap(x_ => y_ =>
    optAp(
      optMap(x => y =>
        arrAp(
          arrMap(add) (x)) (y)) (x_)) (y_))
            (tttx))
              (ttty); // Task(Some([11,21,31,12,22,32,13,23,33]))

We can get rid of the anonymous functions by using point-free style, but the computation still remains hideous and confusing:

const comp = f => g => x => f(g(x));

tAp(
  tMap(
    comp(optAp)
      (optMap(
        comp(arrAp) (arrMap(add)))))
          (tttx))
            (ttty); // Task(Some([11,21,31,12,22,32,13,23,33]))

The problem seems to be the common applicative pattern ap(map(f) (x)) (y). Let's abstract it:

const liftA2 = ({map, ap}) => f => tx => ty =>
  ap(map(f) (tx)) (ty);

const tLiftA2 = liftA2({map: tMap, ap: tAp});
const optLiftA2 = liftA2({map: optMap, ap: optAp});
const arrLiftA2 = liftA2({map: arrMap, ap: arrAp});

comp3(
  tLiftA2)
    (optLiftA2)
      (arrLiftA2)
        (add)
          (tttx)
            (ttty); // Task(Some([11,21,31,12,22,32,13,23,33]))

This is much better. comp3 takes three functions and the resulting composed function takes add and two composed values tttx/ttty and applies add to the inner values. Since applicative computation of the Array type means to calculate the cartesian product this is what we get. Nice.

See an running example and how everything falls into place.

If you want to learn more about FP join my course on Github.