Monad Coproducts / Data types à la carte

[modulovalue]

Hello everybody,

I wanted to share a technique that technically shouldn't be possible in Dart, but that is possible in Dart. It is based on a technique that Rúnar Bjarnason introduces in his talk Composable application architecture with reasonably priced monads (in Scala) which he calls "Monad Coproducts", but says that it is based on Data Types à la Carte by Wouter Swiestra.

The interesting part is that, to implement this technique, higher kinded types are needed, which Scala officially supports, but Dart doesn't.

Erik Meijer and Gilad Bracha, both of whom were on the Dart team a long time ago, claim that "Dart can't have proper Monads because expressing the Monad interface would require higher kinded types", see: Erik Meijer and Gilad Bracha: Dart, Monads, Continuations, and More (2012), which, under a broad interpretation of their statement, is not correct, because we can simulate higher kinded types using type defunctionalization.

So, Dart "supports" higher kinded types, which means that Dart also supports expressing a proper Monad interface and so we can implement Monad Coproducts!

What follows is an example implementation of "Monad Coproducts"/"Data Types à la Carte" in Dart. I'd recommend pasting it into an IDE that supports // region markers and to collapse them all before exploring it. There's a lot of boilerplate code that obscures the actual intent, and exploring it by regions makes that much easier.

Note: it makes heavy use of phantom types. A simpler introduction in a different context can be found here: #2865

import 'dart:collection';
import 'dart:io';

/// Based on: https://www.youtube.com/watch?v=M258zVn4m2M
/// Please direct any feedback and questions to: https://github.com/modulovalue.
/// I'm very interested in finding out how to make this more digestible
/// without one having to learn anything about monads or coproducts.
// region main
void main() {
  Program<F> program<F>({
    required final IOAlgebra<F> IO,
    required final CloudFilesAlgebra<F> CLOUD,
    required final UserInteractionAlgebra<F> UI,
    required final LogAlgebra<F> LOG,
  }) => $<F>()
        .$((final void _) => LOG.log(LogLevel.debug, "Saying hello."))
        .$((final void _) => UI.tell("Hello!"))
        .$((final void _) => IO.delay(const Duration(milliseconds: 200)))
        .$((final void _) => UI.tell("Please wait..."))
        .$((final void _) => IO.delay(const Duration(milliseconds: 500)))
        .$((final void _) => UI.tell("What's your name?"))
        .$((final void _) => IO.read_ln())
        .$((final String? name) {
          final actual_name = name ?? "anonymous";
          return $<F>()
              .$((final void _) => UI.tell("Hello '" + actual_name + "'"))
              .$((final void _) => LOG.log(LogLevel.debug, "User '" + actual_name + "' has accessed the system."))
              .$((final void _) => IO.delay(const Duration(milliseconds: 500)))
              .$((final void _) => LOG.log(LogLevel.debug, "Listing all files."))
              .$((final void _) => CLOUD.list_files())
              .$((final List<String> paths) {
                late final Free<F, void> program;
                return program = $<F>()
                    .$((final void files) => UI.tell("What follows is a list of all files:"))
                    .$((final void files) => UI.tell(paths.asMap().entries.map((final k) => k.value + " (" + k.key.toString() + ")").join(", ") + "."))
                    .$((final void _) => LOG.log(LogLevel.debug, "Provided a list of all files to '" + actual_name + "'"))
                    .$((final void _) => UI.ask("Which file do you want to see? (Or enter 'exit' to exit)"))
                    .$((final String path) {
                      if (path == "exit") {
                        return UI.tell("Exiting");
                      } else {
                        return $<F>()
                            .$((final void _) {
                              final parsed = int.tryParse(path);
                              if (parsed == null) {
                                return UI.tell("Invalid path '" + path + "' given, an index was expected.");
                              } else {
                                if (paths.length > parsed) {
                                  final path = paths[parsed];
                                  return UI.tell(path);
                                } else {
                                  return UI.tell("There's no file for index " + parsed.toString());
                                }
                              }
                            })
                            .$((final void _) => program);
                      }
                    });
              });
        });

  final app = program<
      ForCoproduct2<
          ForCoproduct2<
              ForCloudFilesF,
              ForIOOp //
              >,
          ForCoproduct2<
              ForUserInteraction,
              ForLog //
              > //
          > //
      >(
    CLOUD: CloudFilesAlgebra(
      i: <A>(final a) => CoproductLeft(
        value: CoproductLeft(
          value: a,
        ),
      ),
    ),
    IO: IOAlgebra(
      i: <A>(final a) => CoproductLeft(
        value: CoproductRight(
          value: a,
        ),
      ),
    ),
    UI: UserInteractionAlgebra(
      i: <A>(final a) => CoproductRight(
        value: CoproductLeft(
          value: a,
        ),
      ),
    ),
    LOG: LogAlgebra(
      i: <A>(final a) => CoproductRight(
        value: CoproductRight(
          value: a,
        ),
      ),
    ),
  );
  // run_free_with_info(app)(
  // run_free_recovering(app)(
  run_free(app)(
    <A>(final a) {
      switch (a.DCoproduct) {
        case CoproductLeft(: final value):
          switch (value.DCoproduct) {
            case CoproductLeft(: final value):
              return interpret_cloud_files_algebra<A>(
                value: value.DCloudFiles,
              );
            case CoproductRight(: final value):
              return interpret_io_algebra<A>(
                val: value.DIo,
              );
          }
        case CoproductRight(: final value):
          switch (value.DCoproduct) {
            case CoproductLeft(: final value):
              return interpret_user_interaction_algebra<A>(
                user_interaction: value.DUserInteraction,
              );
            case CoproductRight(: final value):
              return () {
                /// Use this interpreter to disable logging.
                return interpret_log_algebra_noop;
                /// Use this interpreter to enable logging.
                // return interpret_log_algebra_print;
              }()<A>(
                log: value.DLog,
              );
          }
      }
    },
  );
}
// endregion

// region cloud algebra
// region boilerplate
interface class ForCloudFilesF {}

extension FixCloudFiles<A> on Kind<ForCloudFilesF, A> {
  CloudFilesF<A> get DCloudFiles => this as CloudFilesF<A>;
}
// endregion

// region dsl
sealed class CloudFilesF<A> implements Kind<ForCloudFilesF, A> {
  A match({
    required final List<String> Function(ListFiles value) listFiles,
  });
}

final class ListFiles implements CloudFilesF<List<String>> {
  const ListFiles();

  @override
  List<String> match({
    required final List<String> Function(ListFiles value) listFiles,
  }) =>
      listFiles(this);
}
// endregion

// region algebra
final class CloudFilesAlgebra<F> {
  final PartialOuterTransformation<ForCloudFilesF, F> i;

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

  Free<F, List<String>> list_files() => free_init(i(const ListFiles()));
}
// endregion

// region interpreter
A interpret_cloud_files_algebra<A>({
  required final Kind<ForCloudFilesF, A> value,
}) {
  return value.DCloudFiles.match(
    listFiles: (final a) => [
      "file_1",
      "file_2",
      "file_3",
    ],
  );
}
// endregion
// endregion

// region log algebra
// region boilerplate
interface class ForLog {}

extension FixLog<A> on Kind<ForLog, A> {
  Log<A> get DLog => this as Log<A>;
}
// endregion

// region dsl
sealed class Log<A> implements Kind<ForLog, A> {
  A match({
    required final void Function(JustLog v) log,
  });
}

final class JustLog implements Log<void> {
  final LogLevel level;
  final String message;

  const JustLog({
    required this.level,
    required this.message,
  });

  @override
  void match({
    required final void Function(JustLog v) log,
  }) {
    log(this);
  }
}
// endregion

// region supportive
enum LogLevel {
  all,
  debug,
  info,
  warn,
  error,
  fatal,
}
// endregion

// region algebra
final class LogAlgebra<F> {
  final PartialOuterTransformation<ForLog, F> i;

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

  Free<F, void> log(
    final LogLevel level,
    final String statement,
  ) =>
      free_init(i(JustLog(level: level, message: statement)));
}
// endregion

// region interpreter
A interpret_log_algebra_print<A>({
  required final Log<A> log,
}) =>
    log.match(
      log: (final v) => print("LOG|" + DateTime.now().toString() + "|" + v.level.name + ": " + v.message),
    );

A interpret_log_algebra_noop<A>({
  required final Log<A> log,
}) =>
    log.match(
      log: (final v) {
        // Logging is disabled.
      },
    );
// endregion
// endregion

// region io algebra
// region boilerplate
interface class ForIOOp {}

extension FixIoOp<A> on Kind<ForIOOp, A> {
  IOOp<A> get DIo => this as IOOp<A>;
}
// endregion

// region dsl
sealed class IOOp<A> implements Kind<ForIOOp, A> {
  const IOOp();

  A match({
    required final String? Function(Readln node) readln,
    required final void Function(Println node) println,
    required final FileRef Function(OpenFile node) openFile,
    required final UnmodifiableListView<int> Function(ReadBytes node) readBytes,
    required final void Function(WriteBytes node) writeBytes,
    required final void Function(CloseFile node) closeFile,
    required final ExecutionResult Function(Execute node) execute,
    required final void Function(Delay node) delay,
  });
}

final class Readln implements IOOp<String?> {
  const Readln();

  @override
  String? match({
    required final String? Function(Readln node) readln,
    required final void Function(Println node) println,
    required final FileRef Function(OpenFile node) openFile,
    required final UnmodifiableListView<int> Function(ReadBytes node) readBytes,
    required final void Function(WriteBytes node) writeBytes,
    required final void Function(CloseFile node) closeFile,
    required final ExecutionResult Function(Execute node) execute,
    required final void Function(Delay node) delay,
  }) =>
      readln(this);
}

final class Println implements IOOp<void> {
  final String s;

  const Println({
    required this.s,
  });

  @override
  void match({
    required final String? Function(Readln node) readln,
    required final void Function(Println node) println,
    required final FileRef Function(OpenFile node) openFile,
    required final UnmodifiableListView<int> Function(ReadBytes node) readBytes,
    required final void Function(WriteBytes node) writeBytes,
    required final void Function(CloseFile node) closeFile,
    required final ExecutionResult Function(Execute node) execute,
    required final void Function(Delay node) delay,
  }) =>
      println(this);
}

final class OpenFile implements IOOp<FileRef> {
  final String path;
  final bool openForRead;

  const OpenFile({
    required this.path,
    required this.openForRead,
  });

  @override
  FileRef match({
    required final String? Function(Readln node) readln,
    required final void Function(Println node) println,
    required final FileRef Function(OpenFile node) openFile,
    required final UnmodifiableListView<int> Function(ReadBytes node) readBytes,
    required final void Function(WriteBytes node) writeBytes,
    required final void Function(CloseFile node) closeFile,
    required final ExecutionResult Function(Execute node) execute,
    required final void Function(Delay node) delay,
  }) =>
      openFile(this);
}

final class ReadBytes implements IOOp<UnmodifiableListView<int>> {
  final FileRef file;
  final int byteCount;

  const ReadBytes({
    required this.file,
    required this.byteCount,
  });

  @override
  UnmodifiableListView<int> match({
    required final String? Function(Readln node) readln,
    required final void Function(Println node) println,
    required final FileRef Function(OpenFile node) openFile,
    required final UnmodifiableListView<int> Function(ReadBytes node) readBytes,
    required final void Function(WriteBytes node) writeBytes,
    required final void Function(CloseFile node) closeFile,
    required final ExecutionResult Function(Execute node) execute,
    required final void Function(Delay node) delay,
  }) =>
      readBytes(this);
}

final class WriteBytes implements IOOp<void> {
  final FileRef file;
  final Iterable<int> bytes;

  const WriteBytes({
    required this.file,
    required this.bytes,
  });

  @override
  void match({
    required final String? Function(Readln node) readln,
    required final void Function(Println node) println,
    required final FileRef Function(OpenFile node) openFile,
    required final UnmodifiableListView<int> Function(ReadBytes node) readBytes,
    required final void Function(WriteBytes node) writeBytes,
    required final void Function(CloseFile node) closeFile,
    required final ExecutionResult Function(Execute node) execute,
    required final void Function(Delay node) delay,
  }) =>
      writeBytes(this);
}

final class CloseFile implements IOOp<void> {
  final FileRef file;

  const CloseFile({
    required this.file,
  });

  @override
  void match({
    required final String? Function(Readln node) readln,
    required final void Function(Println node) println,
    required final FileRef Function(OpenFile node) openFile,
    required final UnmodifiableListView<int> Function(ReadBytes node) readBytes,
    required final void Function(WriteBytes node) writeBytes,
    required final void Function(CloseFile node) closeFile,
    required final ExecutionResult Function(Execute node) execute,
    required final void Function(Delay node) delay,
  }) =>
      closeFile(this);
}

final class Execute implements IOOp<ExecutionResult> {
  final String command;
  final Iterable<String> arguments;

  const Execute({
    required this.command,
    required this.arguments,
  });

  @override
  ExecutionResult match({
    required final String? Function(Readln node) readln,
    required final void Function(Println node) println,
    required final FileRef Function(OpenFile node) openFile,
    required final UnmodifiableListView<int> Function(ReadBytes node) readBytes,
    required final void Function(WriteBytes node) writeBytes,
    required final void Function(CloseFile node) closeFile,
    required final ExecutionResult Function(Execute node) execute,
    required final void Function(Delay node) delay,
  }) =>
      execute(this);
}

final class Delay implements IOOp<void> {
  final Duration duration;

  const Delay({
    required this.duration,
  });

  @override
  void match({
    required final String? Function(Readln node) readln,
    required final void Function(Println node) println,
    required final FileRef Function(OpenFile node) openFile,
    required final UnmodifiableListView<int> Function(ReadBytes node) readBytes,
    required final void Function(WriteBytes node) writeBytes,
    required final void Function(CloseFile node) closeFile,
    required final ExecutionResult Function(Execute node) execute,
    required final void Function(Delay node) delay,
  }) =>
      delay(this);
}
// endregion

// region supportive
final class FileRef {
  final RandomAccessFile f;

  const FileRef({
    required this.f,
  });
}

final class ExecutionResult {
  final int exitCode;
  final String stdout;
  final String stderr;

  const ExecutionResult({
    required this.exitCode,
    required this.stdout,
    required this.stderr,
  });
}
// endregion

// region algebra
final class IOAlgebra<F> {
  final PartialOuterTransformation<ForIOOp, F> i;

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

  Free<F, String?> read_ln() => free_init(i(const Readln()));

  Free<F, void> print_ln(
    final String s,
  ) =>
      free_init(i(Println(s: s)));

  Free<F, FileRef> open_file(
    final String path,
    final bool openForRead,
  ) =>
      free_init(i(OpenFile(path: path, openForRead: openForRead)));

  Free<F, UnmodifiableListView<int>> readBytes(
    final FileRef file,
    final int byteCount,
  ) =>
      free_init(i(ReadBytes(file: file, byteCount: byteCount)));

  Free<F, void> write_bytes(
    final FileRef file,
    final Iterable<int> bytes,
  ) =>
      free_init(i(WriteBytes(file: file, bytes: bytes)));

  Free<F, void> close_file(
    final FileRef ref,
  ) =>
      free_init(i(CloseFile(file: ref)));

  Free<F, ExecutionResult> execute(
    final String command,
    final Iterable<String> arguments,
  ) =>
      free_init(i(Execute(command: command, arguments: arguments)));

  Free<F, void> delay(
    final Duration duration,
  ) =>
      free_init(i(Delay(duration: duration)));
}
// endregion

// region interpreter
B interpret_io_algebra<B>({
  required final Kind<ForIOOp, B> val,
}) =>
    val.DIo.match(
      closeFile: (final v) => v.file.f.closeSync(),
      delay: (final v) => sleep(v.duration),
      execute: (final v) {
        final result = Process.runSync(
          v.command,
          v.arguments.toList(),
        );
        return ExecutionResult(
          exitCode: result.exitCode,
          stdout: result.stdout as String,
          stderr: result.stderr as String,
        );
      },
      openFile: (final v) => FileRef(
        f: File(
          v.path,
        ).openSync(
          mode: () {
            if (v.openForRead) {
              return FileMode.read;
            } else {
              return FileMode.write;
            }
          }(),
        ),
      ),
      println: (final p) => print(
        p.s,
      ),
      readBytes: (final v) => UnmodifiableListView(
        v.file.f.readSync(
          v.byteCount,
        ),
      ),
      readln: (final r) => stdin.readLineSync(),
      writeBytes: (final v) => v.file.f.writeFromSync(
        v.bytes.toList(),
      ),
    );
// endregion
// endregion

// region ui algebra
// region boilerplate
interface class ForUserInteraction {}

extension FixUserInteraction<A> on Kind<ForUserInteraction, A> {
  UserInteraction<A> get DUserInteraction => this as UserInteraction<A>;
}
// endregion

// region dsl
sealed class UserInteraction<A> implements Kind<ForUserInteraction, A> {
  const UserInteraction();

  A match({
    required final void Function(Tell) tell,
    required final String Function(Ask) ask,
  });
}

final class Tell extends UserInteraction<void> {
  final String statement;

  const Tell({
    required this.statement,
  });

  @override
  void match({
    required final void Function(Tell) tell,
    required final String Function(Ask) ask,
  }) {
    tell(this);
  }
}

final class Ask extends UserInteraction<String> {
  final String question;

  const Ask({
    required this.question,
  });

  @override
  String match({
    required final void Function(Tell) tell,
    required final String Function(Ask) ask,
  }) =>
      ask(this);
}
// endregion

// region algebra
final class UserInteractionAlgebra<F> {
  final PartialOuterTransformation<ForUserInteraction, F> i;

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

  Free<F, String> ask(
    final String question,
  ) =>
      free_init(i(Ask(question: question)));

  Free<F, void> tell(
    final String statement,
  ) =>
      free_init(i(Tell(statement: statement)));
}
// endregion

// region interpreter
A interpret_user_interaction_algebra<A>({
  required final UserInteraction<A> user_interaction,
}) =>
    user_interaction.match(
      tell: (final v) => print("> " + v.statement),
      ask: (final v) {
        print("> " + v.question);
        return stdin.readLineSync()!;
      },
    );
// endregion
// endregion

// region framework
// region coproduct
// region boilerplate
extension KindCoproductFix<F, G, A> on Kind<ForCoproduct2<F, G>, A> {
  Coproduct<F, G, A> get DCoproduct => this as Coproduct<F, G, A>;
}

interface class ForCoproduct0 {}

interface class ForCoproduct1<F> implements Kind<ForCoproduct0, F> {}

interface class ForCoproduct2<F, G> implements Kind<ForCoproduct1<F>, G> {}

interface class ForCoproduct3<F, G, A> implements Kind<ForCoproduct2<F, G>, A> {}
// endregion

// region dsl
/// A "Coproduct" here is very similar to the concept of an "Either".
/// An "Either" shares the same "Kind" with all variants, but makes
/// the type parameter variable, whereas a Coproduct shares the
/// same type parameter with all variants, but makes the "Kind"
/// variable.
sealed class Coproduct<F, G, A> implements ForCoproduct3<F, G, A> {}

final class CoproductLeft<F, G, A> implements Coproduct<F, G, A> {
  final Kind<F, A> value;

  const CoproductLeft({
    required this.value,
  });
}

final class CoproductRight<F, G, A> implements Coproduct<F, G, A> {
  final Kind<G, A> value;

  const CoproductRight({
    required this.value,
  });
}
// endregion
// endregion

// region free
// region boilerplate
extension KindFreeFix<F, A> on Kind<Kind<ForFree0, F>, A> {
  Free<F, A> get DFree => this as Free<F, A>;
}

interface class ForFree0 {}

interface class ForFree1<F> implements Kind<ForFree0, F> {}

interface class ForFree<F, A> implements Kind<ForFree1<F>, A> {}
// endregion

// region dsl
sealed class Free<F, A> implements ForFree<F, A> {
  R match<R>({
    required final R Function(FreePure<F, A>) pure,
    required final R Function<B>(Kind<F, B> p, Free<F, A> Function(B) f) bind,
  });
}

final class FreePure<F, A> implements Free<F, A> {
  final A a;

  const FreePure({
    required this.a,
  });

  @override
  R match<R>({
    required final R Function(FreePure<F, A>) pure,
    required final R Function<B2>(
      Kind<F, B2> p,
      Free<F, A> Function(B2 p1) f,
    ) bind,
  }) =>
      pure(this);
}

final class FreeBind<F, A, B> implements Free<F, A> {
  final Kind<F, B> p;
  final Free<F, A> Function(B) cont;

  const FreeBind({
    required this.p,
    required this.cont,
  });

  @override
  R match<R>({
    required final R Function(FreePure<F, A>) pure,
    required final R Function<B2>(
      Kind<F, B2> p,
      Free<F, A> Function(B2 p1) f,
    ) bind,
  }) =>
      bind(
        p,
        <FOO extends B>(final FOO a) => cont(a),
      );
}
// endregion

// region runners
A Function(B Function<B>(Kind<F, B>)) run_free<F, A>(
  final Free<F, A> free,
) =>
    (final eval) => free.match(
      pure: (final a) => a.a,
      bind: <B>(final sub, final cont) {
        final evaluated = eval(sub);
        final continuation = cont(evaluated);
        final next = run_free(continuation);
        return next(eval);
      },
    );

A Function(B Function<B>(Kind<F, B>)) run_free_recovering<F, A>(
  final Free<F, A> free,
) =>
    (final eval) => free.match(
      pure: (final a) => a.a,
      bind: <B>(final sub, final cont) {
        final evaluated = eval(sub);
        final continuation = cont(evaluated);
        final next = run_free(continuation);
        try {
          return next(eval);
        } on Object {
          print(
            "=" * 80,
          );
          print(
            "The program crashed. Something unexpected happened!",
          );
          print(
            "=" * 80,
          );
          rethrow;
        }
      },
    );

void Function(B Function<B>(Kind<F, B> val) eval) run_free_with_info<F, T>(
  final Free<F, T> free,
) =>
    (final B Function<B>(Kind<F, B> val) eval) {
      Free<F, dynamic>? current = free;
      for (;;) {
        final cur = current;
        if (cur == null) {
          break;
        } else {
          current = cur.match(
            pure: (final p) {
              print(
                "===> End: " + p.toString(),
              );
              return null;
            },
            bind: <B>(final p, final f) {
              print(
                "===> Evaluating: " + p.toString(),
              );
              final value = eval(p);
              print(
                "===> Evaluated to: " + value.toString()
              );
              return f(value);
            },
          );
        }
      }
    };
// endregion

// region helpers
extension FreeExtension<F, A> on Free<F, A> {
  Free<F, B> $<B>(
    final Free<F, B> Function(A) ff,
  ) =>
      match(
        pure: (final a) => ff(a.a),
        bind: <B2>(final pure, final cont) => FreeBind(
          p: pure,
          cont: (final B2 val) => cont(val).$(ff).DFree,
        ),
      );
}

typedef Program<F> = Free<F, void>;

FreeStart<F> $<F>() => FreeStart<F>();

final class FreeStart<F> {
  const FreeStart();

  Free<F, B> $<B>(
    final Free<F, B> Function(void) f,
  ) =>
      f(Null);
}

Free<F, A> free_init<F, A>(
  final Kind<F, A> pure,
) =>
    FreeBind<F, A, A>(
      p: pure,
      cont: (final A a) => FreePure(
        a: a,
      ),
    );
// endregion
// endregion

// region core
interface class Kind<F, A> {}

typedef PartialOuterTransformation<F, G> = Kind<G, A> Function<A>(
  Kind<F, A>,
);
// endregion
// endregion

It implements 4 algebras (that is, in this case, sets of operations) called: UI, LOG, CLOUD and IO. They represent distinct concerns. With "Monad Coproducts", we can compose them in one compilation unit while having them exist in separate compilation units without them having to depend on each other, and we don't have to provide an interpretation strategy during composition-time. That is, we can construct a program, and interpret it later, possibly with different interpretation strategies, all without having to sacrifice type safety.

We can observe that:

• We can construct programs from different algebras while being able to defer how they interact to after the program has been constructed.
• We can provide different interpretation strategies (for each algebra separately) to, for example, disable/enable logging without having to use "ad-hoc" toggles (e.g. if (enableLogging) log(...)) which would obscure the intent of the program.
• There's a lot of boilerplate needed to implement the higher-kinded-type-machinery which a language feature could eliminate.
• Dart has syntax sugar for chaining specific monads (e.g., Futures via asynchronous generators, Streams via synchronous generators, Lists via spreads, Statements via blocks and IIFEs), but no general mechanism for chaining free-monads (or arbitrary monads), which might be needed to make this technique ergonomic.
• To make this efficient in practice, it has to be possible to, given such a program and a specific interpretation strategy, compile them into a traditional program that does not contain the overhead that this representation has. There's a body of work known under the term of Futamura projections which offers a solution to this problem. The Free-Monad and Coproduct machinery could be optimized into a traditional program by inlining all the components until there's none of the additional machinery left. After the process, we should be left with a program that we would have written by hand.

Any comments would be greatly appreciated.

[Ing-Brayan-Martinez]

@modulovalue Greetings friend, I am using a translator, I know this context, I wanted to tell you that if you are right, higher order types are needed and today I was putting together a proposal for this, I am going to try to make it minimalist so that it is accessible to everyone. I like your initiative when you use it. I'm going to make reference to this post

[Ing-Brayan-Martinez]

@modulovalue Friend, here is my proposal of how I see the introduction of higher order functions. This feature is already supported in the language thanks to the reserved word typedef. To introduce monads into the syntax of the Dart language, we must identify the fundamental types that can be used as a monad

The fundamental types of language

The basic types are not candidates to be monads since they could not be Functors because they are incapable of wrapping a data. This is necessary to define a monad. The Dart language types that could not be used are:

• String
• num
• int
• double
• bool
• T?

Convertible types to monad

In the Dart language there are some complex types that are fundamental and if they are compatible with the idea of ​​monad, they can be the basis for supporting functional programming in the language. First we must explain why they are candidates for monad.

A type of language that is usable as a monad is one that allows values ​​to be stored inside, that is, it serves as a wrapper, this is known as a functor. It must also have a series of operators (map, filter, reduce, flatmap) that allow the management of the wrapped value. Among the language types that can meet this characteristic we have:

• DateTime
• List
• Map
• Set
• Future
• Stream
• Optional

For these objects to be used as monads, it is necessary to comply with the singlenton pattern to avoid having repeated instances and behave consistently.

About the DateTime type

For the DateTime type it is necessary to limit the instantiation of this object, for this we will use the of() operator which is necessary to construct the object serving as a functor as follows:

void main() {
  DateTime date = DateTime.of(2024, 06, 12);
  print(date.toString());
 
 DateTime date2 = DateTime.now();
 print(date2.toString());
}

This way the DateTime object is usable as a monad

About List Map and Set types

These are the collection base types in the Dart language and are candidates as monads that must be done in a very specific way. To convert a List, Map or a Set into a monad, it is necessary to use the of() operator that allows wrapping values. The difference would be that the resulting collection would be immutable.

It is necessary that the collection must be immutable so that it has consistency and is faithful to the functional programming paradigm. Let's look at some examples:

void main() {
 List<int> ex1 = List.of(1, 2, 3, 4, 5, 6);
 ex1.forEach((n) => print(n));
 
 Map<String, int> ex1 = Map.of('key1',  11, 'key2', 22, 'key3', 33);
 ex2.forEach((key, value) => print(value));

 Set<int> ex1 = Set.of(1, 2, 3, 4, 5, 6);
 ex1.forEach((n) => print(n));
}

All collections will be immutable and behave like monads

About Future and Stream types

These data types are designed to perform asynchronous operations and in a certain way they are already optimized to function as monads since they were designed this way from the beginning, the only change that could be made is in the Future object which has the constructor Future(() => 'hello'); which could be replaced by the of() operator as follows:

void main() {
 Future<String> ex1 = Future.of('hello');
 ex1.then((value) => print(value));
 
 Stream s = Stream.value('hello');
 s.forEach((value) => print(value));
}

About the Optional type

This Optional type is special because it does not currently exist in the Dart language, this type is useful for wrapping null values ​​that can generate an error and helps with null safety, I discuss this in this proposal. The optional type would look like this:

Using optional notation

void main() {
  Optional<String> name = null;

  // Error: Because you cannot directly access toUpperCase() because you are referring to the Optional wrapper, to access
  // toUpperCase() you must extract the String making sure that it is present without any risk

  print(name.toUpperCase()); //Access error, The IDE should not suggest this

  print(name?.toUpperCase()!); // Correct access, because operators are used that automatically ensure access

  print(name?.toUpperCase() ?? 'Not Value'); // Correct access, with default value
}

Using simplified optional notation

void main() {
  Optional<String> otherName = null;

  String? name = otherName; // Optional<String> equivalent String?

  // Error: Because you cannot directly access toUpperCase() because you are referring to the Optional wrapper, to access
  // toUpperCase() you must extract the String making sure that it is present without any risk

  print(name.toUpperCase()); // Access error, The IDE should not suggest this

  print(name?.toUpperCase()!); // Correct access, because operators are used that automatically ensure access

  print(name?.toUpperCase() ?? 'Not Value'); // Correct access, with default value
}

Using extended optional notation

void main() {
  Optional<String> otherName = null;

  String? name = otherName; // Optional<String> equivalent String?

  // Error: Because you cannot directly access toUpperCase() because you are referring to the Optional wrapper, to access
  // toUpperCase() you must extract the String making sure that it is present without any risk

  print(name.toUpperCase()); //Access error, The IDE should not suggest this

  print( name.map((str) => str.toUpperCase()).get() ); // Correct access

  print( name.map((str) => str.toUpperCase()).orElse('Not Value') ); // Correct access, with default value
}

These would be all my observations. If you have any questions or suggestions, you can comment.

[Ing-Brayan-Martinez]

I recommend you check out some libraries for functional programming in Dart, check this list:

• fpdart
• ribs