Recursion Schemes in Dart

I am trying to implement zero-cost recursion schemes in Dart.

I'm using a technique that, I believe, is formally known as [type defunctionalization](https://github.com/dart-lang/language/issues/844). The theory seems to be much more complex than what's necessary in practice, but I'll be referring to that technique within the context of Dart here as TD.

Using TD we can be more general than what the static type system currently supports and implement first class functors (_functors in the functional programming sense_).

Furthermore, using TD we can also implement a fixpoint type that allows us to generalize over recursive structures.

In addition to that, TD requires us to have a marker interface for the root of our recursive structures so that we can refer to them on the simulated kind level.

This is enough to implement recursion schemes. Recursion schemes are a way to generalize traversals over recursive structures. The benefits of expressing a problem in terms of recursion schemes are that the implementation becomes much more maintainable because any explicit recursion is removed and, among other things, it becomes clear which traversals can be merged to reduce N separate traversals to just one.

There are three categories of recursion schemes (folds, unfolds and refolds) and each can be expanded to support different problem domains. For simplicity, the code below implements a fold that is known as a catamorphism, but others such as anamorphisms, hylomorphisms and even more involved ones such as futumorphisms and histomorphisms are implementable in Dart as well.

The main issue with the implementation below is that we are forced to introduce a level of indirection via Fix when referring to an Expression that contains members of its own hierarchy. I was hoping that inline classes could help here, but it is not intended (https://github.com/dart-lang/sdk/issues/51564#issuecomment-1448256471) for them to support implements clauses and so they will not be able to implement Fix to make the Fix here zero-cost.

I have tried other things, such as making the members of the expression hierarchy implement Fix themselves, but I always ran into some limitations.

This example code evaluates a simple expression hierarchy by using a catamorphism. Notice how the argument to `invoke` needs to wrap all expressions in a Fix which I would like to avoid.

Catamorphism 1

```dart
void main() {
print(
Catamorphism(
fold: (final e) => e.DExpr.match(
value: (final v) => v.i,
add: (final a) => a.lhs + a.rhs,
mult: (final a) => a.lhs * a.rhs,
),
fmap: (final value, final fn) => value.DExpr.match(
value: (final self) => ExpressionValue(
i: self.i,
),
add: (final self) => ExpressionAdd(
lhs: fn(self.lhs),
rhs: fn(self.rhs),
),
mult: (final self) => ExpressionMult(
lhs: fn(self.lhs),
rhs: fn(self.rhs),
),
),
).invoke(
const Fix(
unfix: ExpressionMult(
lhs: Fix(
unfix: ExpressionAdd(
lhs: Fix(
unfix: ExpressionValue(
i: 1,
),
),
rhs: Fix(
unfix: ExpressionValue(
i: 3,
),
),
),
),
rhs: Fix(
unfix: ExpressionValue(
i: 5,
),
),
),
),
),
);
}

class Catamorphism {
final KindExpression Function(
KindExpression>,
B Function(KindFix),
) fmap;
final B Function(KindExpression) fold;

const Catamorphism({
required this.fmap,
required this.fold,
});

B invoke(
final KindFix a,
) {
final KindExpression> x = a.DFix.unfix;
final KindExpression y = fmap(x, invoke);
final B z = fold(y);
return z;
}
}

// Expression
abstract class KindExpression {}

extension ExpressionFix on KindExpression {
Expression get DExpr => this as Expression;
}

abstract class ForExpression {}

extension ExpressionMatcherExtension on Expression {
Z match({
required final Z Function(ExpressionValue a) value,
required final Z Function(ExpressionAdd a) add,
required final Z Function(ExpressionMult a) mult,
}) {
final _ = this;
if (_ is ExpressionValue) return value(_);
if (_ is ExpressionAdd) return add(_);
if (_ is ExpressionMult) return mult(_);
throw Exception(
"Invalid State",
);
}
}

abstract class Expression implements KindExpression {}

class ExpressionValue implements Expression {
final int i;

const ExpressionValue({
required this.i,
});
}

class ExpressionAdd implements Expression {
final F lhs;
final F rhs;

const ExpressionAdd({
required this.lhs,
required this.rhs,
});
}

class ExpressionMult implements Expression {
final F lhs;
final F rhs;

const ExpressionMult({
required this.lhs,
required this.rhs,
});
}

// Fix
abstract class KindFix {}

extension KindFixFix on KindFix {
Fix get DFix {
return this as Fix;
}
}

abstract class ForFix {}

class Fix implements KindFix {
final KindExpression> unfix;

const Fix({
required this.unfix,
});
}
```

My goal is to eventually add support for recursion schemes to custom code generators and to investigate how I can make using the theory behind recursion scheme fusion practical, but the overhead of the Fix wrapper makes it hard for me to commit to such a solution, because I would like for it to be at least as performant as code that doesn't make use of recursion schemes.

Edit: below is an updated version that uses new features to simplify and make things safer (_sealed classes, exhaustive matching, and class modifiers_):

Catamorphism 2

```dart
void main() {
print(
Catamorphism(
fold: (final e) => switch (e.DExpr) {
ExpressionValue(:final i) => i,
ExpressionAdd(:final lhs, :final rhs) => lhs + rhs,
ExpressionMult(:final lhs, :final rhs) => lhs * rhs,
},
fmap: (final value, final fn) => switch (value.DExpr) {
ExpressionValue(:final i) => ExpressionValue(
i: i,
),
ExpressionAdd(:final lhs, :final rhs) => ExpressionAdd(
lhs: fn(lhs),
rhs: fn(rhs),
),
ExpressionMult(:final lhs, :final rhs) => ExpressionMult(
lhs: fn(lhs),
rhs: fn(rhs),
),
},
).invoke(
const Fix(
unfix: ExpressionMult(
lhs: Fix(
unfix: ExpressionAdd(
lhs: Fix(
unfix: ExpressionValue(
i: 1,
),
),
rhs: Fix(
unfix: ExpressionValue(
i: 3,
),
),
),
),
rhs: Fix(
unfix: ExpressionValue(
i: 5,
),
),
),
),
),
);
}

final class Catamorphism {
final KindExpression Function(
KindExpression>,
B Function(KindFix),
) fmap;
final B Function(KindExpression) fold;

const Catamorphism({
required this.fmap,
required this.fold,
});

B invoke(
final KindFix a,
) {
final KindExpression> x = a.DFix.unfix;
final KindExpression y = fmap(x, invoke);
final B z = fold(y);
return z;
}
}

// Expression
final class KindExpression {}

extension ExpressionFix on KindExpression {
Expression get DExpr => this as Expression;
}

final class ForExpression {}

sealed class Expression implements KindExpression {}

final class ExpressionValue implements Expression {
final int i;

const ExpressionValue({
required this.i,
});
}

final class ExpressionAdd implements Expression {
final F lhs;
final F rhs;

const ExpressionAdd({
required this.lhs,
required this.rhs,
});
}

final class ExpressionMult implements Expression {
final F lhs;
final F rhs;

const ExpressionMult({
required this.lhs,
required this.rhs,
});
}

// Fix
sealed class KindFix {}

extension KindFixFix on KindFix {
Fix get DFix {
return this as Fix;
}
}

final class ForFix {}

final class Fix implements KindFix {
final KindExpression> unfix;

const Fix({
required this.unfix,
});
}
```

Start with the Catamorphism 2 example in the issue and read the linked language issue 844 and SDK discussion 51564. The issue does not identify a repository file, test, concrete language change, or acceptance criterion, so the desired Dart feature and definition of done need clarification.

Written by the indexing model from the issue text.