jnkrtech

Thank you!

Side note: I am relatively new here and am using the Mlem app. It seems like posting a link is done in the same way as a Reddit-style text post rather than a bare link. Did I do this right?

lemmy seems to have lost my response to this, so I'll type it again and hope that it doesn't show up twice

There's three separate issues here:

1. The ability to express multi-sorted algebras

2. The ability to extend algebras with new sorts

3. The ability to extend a single sort of an algebra with new variants

For point 1, object algebras do support this even though I didn't show it in the post:

interface ExprAlg<Num, Bool> {
    lit: (value: number) => Num;
    add: (left: Num, right: Num) => Num;
    eq: (left: Num, right: Num) => Bool;
    iff: (interrogee: Bool, then: Num, els: Num) => Num;
}

const evaluate: ExprAlg<number, boolean> = {
    lit: (value) => value,
    add: (left, right) => left + right,
    eq: (left, right) => left === right,
    iff: (interrogee, then, els) => interrogee ? then : els
}

function makeExample<Num, Bool>(alg: ExprAlg<Num, Bool>): Num {
    return alg.iff(
        alg.eq(
            alg.add(alg.lit(2), alg.lit(2)),
            alg.lit(4)),
        alg.lit(1),
        alg.lit(2))
}

console.log(makeExample(evaluate)); // prints 1

For point 2, you are correct that the original Java formulation of object algebras does not support data sort extensibility. I haven't tried to see if TS's more powerful generics change this or not.

For point 3, consider what happens if you want to add a new variant to the data type. In this case, add a Mult variant for multiplication. With GADTs this is not possible without modifying or duplicating the existing evaluation code, but I can do it with object algebras:

type ExtendedExprAlg<Num, Bool> = ExprAlg<Num, Bool> & {
    mult: (left: Num, right: Num) => Num;
}

const extendedEvaluate: ExtendedExprAlg<number, boolean> = Object.assign({}, evaluate, {
    mult: (left: number, right: number) => left * right
})

function makeExtendedExample<Num, Bool>( alg: ExtendedExprAlg<Num, Bool>): Num {
    const one = alg.mult(alg.lit(1), alg.lit(1));
    return alg.iff(
        alg.eq(one, makeExample(alg)),
        alg.lit(3),
        alg.mult(alg.lit(2), alg.lit(2))
    )
}

console.log(makeExtendedExample(extendedEvaluate)); // prints 3

This is the point of object algebras. ADTs and GADTs can't do this out of the box; this is the essence of the expression problem and is why more advanced techniques like final tagless encodings and datatypes a la carte exist.

Yes, this pattern is covered in my post on algebraic data types (linked at the start of the object algebras post.) The problem you mention about adding new data variants is exactly what object algebras solves. With object algebras data and functions are only co-located at the smallest possible granularity, so the desired functions and the desired data types can be composed as needed.

That’s an understandable criticism. I do plan on writing a more involved example in the future, but this would be a two-hour-read if I had tried to include it. I’m hoping that introducing the basics on a very simple example will be a good stepping stone towards more involved ones.

I get the concern. I haven't seen the pattern used in practice in an OO context, so I also can't say for certain where this breaks down. Something to note, though, is that object algebras in an OOP context are equivalent to the final tagless pattern in an FP context, and it's not uncommon for entire functional applications to be based around final tagless. This gives me some level of confidence that it would only take a reasonable amount of discipline to build a system based on object algebras.