ADTs in JavaScript

adt-examples.js

// Copyright 2019 Simon Meskens
// Licensed under the MIT License
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided this license is
// preserved. This software is offered as-is, without any warranty.

import { adt } from "./adt.js";

const double = x => x * 2;

{
    // Create a value that's either Right or Left
    const either = adt(["left", "right"]);
    // `left` and `right` are the constructors
    const { left, right } = either;

    // Extend the Either with `map` and `extract`
    Object.assign(either.prototype, {
        map(transform) {
            return either.match(this, { left, right: x => right(transform(x)) });
        },
        extract() {
            return either.match(this, { left: x => x, right: x => x });
        }
    });

    const tests = [
        left("whoops")
            .map(double)
            .extract(), // Expected: "whoops"
        right(21)
            .map(double)
            .extract() // Expected: 42
    ];

    console.log(...tests);
}

{
    // Create a LISP style List, which can be constructed from a head and a tail
    const list = adt(["nil", "cons"]);
    const { nil, cons } = list;

    // Handy utility to go from array -> List
    list.from = arr => [...arr].reverse().reduce((tail, head) => cons(head, tail), nil());

    // Extend the List with `map` and `toArray`
    Object.assign(list.prototype, {
        map(transform) {
            return list.match(this, {
                nil,
                cons: (head, tail) => cons(transform(head), tail.map(transform))
            });
        },
        toArray() {
            return list.match(this, {
                nil: () => [],
                cons: (head, tail) => [head, ...tail.toArray()]
            });
        }
    });

    const tests = [
        list
            .from([1, 2, 3])
            .map(double)
            .toArray() // Expected: [2, 4, 6]
    ];

    console.log(...tests);
}

{
    // Generic extend function that adds `map` and `extract` to any Maybe
    const extend = ({ nothing, just, match }) => ({
        nothing,
        just,
        match,
        map: (option, transform) =>
            match(option, { nothing, just: x => just(transform(x)) }),
        extract: option => match(option, { nothing: () => undefined, just: x => x })
    });

    {
        // Very simple Maybe implementation
        const { map, extract, nothing, just } = extend({
            nothing: () => undefined,
            just: x => x,
            match: (option, { nothing, just }) =>
                option == undefined ? nothing() : just(option)
        });

        const tests = [
            extract(map(nothing(), double)), // Expected: undefined
            extract(map(just(21), double)) // Expected: 42
        ];

        console.log(...tests);
    }

    {
        // Maybe implementation using ADT
        const { map, extract, nothing, just } = extend(adt(["nothing", "just"]));

        const tests = [
            extract(map(nothing(), double)), // Expected: undefined
            extract(map(just(21), double)) // Expected: 42
        ];

        console.log(...tests);
    }
}

{
    // Generic extend function that adds `length`, `map` and `from` (array) to any list
    const extend = ({ nil, cons, match }) => {
        const length = list =>
            match(list, { nil: () => 0, cons: (head, tail) => 1 + length(tail) });

        const map = (list, transform) =>
            match(list, {
                nil,
                cons: (head, tail) => cons(transform(head), map(tail, transform))
            });

        // Constructing lists is easier inside out
        const from = arr =>
            [...arr].reverse().reduce((tail, head) => cons(head, tail), nil());

        return { nil, cons, match, length, map, from };
    };

    {
        // Very simple array backed list implementation
        const { length, map, from } = extend({
            nil: () => [],
            cons: (head, tail) => [head, ...tail],
            match: (list, { nil, cons }) =>
                list.length === 0 ? nil() : cons(list[0], list.slice(1))
        });

        const tests = [
            length(from([0, 1, 2])), // Expected: 3
            map(from([1, 2, 3]), double) // Expected: [2, 4, 6]
        ];

        console.log(...tests);
    }

    {
        // List implementation using ADT
        const { length, map, from } = extend(adt(["nil", "cons"]));

        const tests = [
            length(from([0, 1, 2])), // Expected: 3
            map(from([1, 2, 3]), double) // Expected: [2, 4, 6]
        ];

        console.log(...tests);
    }
}

adt.js

// Copyright 2019 Simon Meskens
// Licensed under the MIT License
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided this license is
// preserved. This software is offered as-is, without any warranty.

export const adt = labels => {
    const prototype = {};

    const constructors = labels
        .map(label => [
            label,
            (...values) =>
                Object.assign(Object.create(prototype), {
                    [label]: values
                })
        ])
        .reduce((dict, [label, constructor]) => ({ ...dict, [label]: constructor }), {});

    const match = (adt, cases) =>
        Object.entries(adt)
            .map(([label, values]) => cases[label](...values))
            .shift();

    return { ...constructors, match, prototype };
};