Std: Execution, Sender/Receiver, and the Continuation Monad

TL;DR is its a design pattern. You wont really notice the value of them until you see how they solve the same thing over and over again, such as return value checking hell in c (check the second link)

But anyway my advice is to just ignore it; you'll really need to spend some time in e.g. haskell or something else in order to get familiar with them enough to fully grok them

[1] https://livebook.manning.com/book/functional-programming-in-...

[2] https://www.manning.com/books/functional-programming-in-c-pl...

If you are dead set on learning about monads without learning Haskell (or a related typed functional language), I would focus on understanding Haskell-style functors and then applicative functors because they are simpler than monads, but they are deeply-related algebraic building blocks that are useful abstractions in their own right. When you are comfortable programming with them, monads shouldn’t be much of a leap.

Interesting! I normally explain monads (and functors, which they're based on) starting from generics/templates, which C doesn't even have. I wonder if it's better or worse to start without those preconceptions?

I'm going to try to explain functors from this standpoint. From the other times I've done this, the fundamental problems people have with monads tend to actually be problems with functors. So hopefully this still helps. :)

In C, what do you do if you want to structure some data as a binary tree? It seems to me that you have three options:

1. You can write a binary tree from scratch, with a node type customized for the data you want it to carry. (You might even go the "intrusive" approach and simply add left/right pointers to your existing data structure.)

2. You can write macros for generating binary tree instances for any particular carrier type (as in [0]). You get a completely distinct tree type (and functions) for every type, but the definitions are consistent with each other in some sense, since they're generated by the same macros.

3. You can use a binary tree whose carrier type is `void*`. You get exactly one tree type (and one set of functions), but you have to make sure you cast elements to the right type whenever you interact with the data structure.

Notice that all of these solve the problem. You've got a binary tree that does what you want, no matter which approach you take. The tradeoffs here are almost entirely along the maintainability dimension: in (1) you have to rewrite the logic every time, and so you have to maintain all copies independently. In (2) you can maintain all logic in one place, but you get one whole tree type for every carrier, and no way to write functions that don't care what type of list they're getting. (You'd have to one for each type, e.g. also using macros.) In (3) you have just one tree type, but the knowledge about which element type you're using has been split across readers and writers, who have to be coordinated in some other way (usually programmer discipline).

Given these options -- and suspending disbelief about C's macro system, which is obviously terrifying to do these things with and we know better solutions of the same kind exist -- which would you choose? Obviously, it depends on the context (intrusive structures can be great for locality), but in terms of sustainability, which do you prefer?

As for myself, I prefer (2), even ignoring that I know where I'm leading you on this. (1) is an optimization; it's not where you want to start. You're literally duplicating all the logic, after all! (3) replaces local reasoning with global reasoning: you have to know (or be assured in some way) that the element you're getting from the list is of the type you want, and nothing prevents somebody who's particularly clever and enterprising from hanging some other type of data off of a part of the tree they're positive nobody's looking at. (This from experience.)

Option (2) lets you maintain the tree logic in one place, while also keeping the knowledge of what element type is held by the tree consistently in the tree rather than across its readers or writers. Its major downside is that, since all tree types are totally independent, we can't write a single function that works with trees over any element type. (Say, a binary-search function, which takes a tree and a function to compare two elements of the desired type.) This seems like a really reasonable thing to do, right? After all, any tree type is generated from the same macro. They're all similar; there's things you can say about any tree that isn't really dependent on its carrier type.

A functor, as a concept, is a way of organizing all of these distinct tree types together based on those similarities. We reason about "similarities" by looking at things we can do to any particular tree type, and asking how to do it to any other tree type. Anything that doesn't depend on the carrier can be "generalized" from one list to any other list.

In other words, suppose you've written a concrete function `Out foo(Tree_T1 list)`. If you had a function `T1 transform(T2 element)`, what would it take to produce a `foo` that operates on ` List_T2` instead? Well, you'd copy `foo`, rename it, change its list type, and... everywhere you get an element from your list, you wrap it in `transform` before continuing as before.

We don't really want to change `foo` itself, though. After all, we'd be duplicating the logic for every version of `foo`! It works, but ultimately we're just pretending that we have a Tree_T1, even though we received a Tree_T2. Instead, what if we define a helper, `Tree_T1 tree_map_transform(Tree_T2 tree)`, so that we can just use `foo`? That works, but we've kind of pushed the problem upstream... now we need a new `tree_map_` function for any particular `transform`!

Hang on, though -- before, we were worried about all of the generic functions we wanted to write against trees. Now we have exactly one generic function to maintain; all the others can be implemented using a `tree_map_`, and we can still use macros to derive these. Every other generic function can be written once! That's a significant reduction in duplication, if I may say! And we can still decide to use option (3) -- using void* -- along with a function pointer.

In C, we're kind of stuck. Even though C doesn't have higher-order functions, we can get a lot of mileage out of simple function pointers. The problem is that `tree_map` depends on two different types, and we just have no way to use one function definition that doesn't care about multiple types. But we've significantly reduced the amount of code that's actually subject to this restriction. (And we can always write these directly if we want, for efficiency.)

In this example, we never actually wrote down "a functor". We have no way to describe it in C; it's a concept, a way of organizing types in a coherent way, not something that the machine actually uses at runtime. But by thinking about how our types are related, we were able to define a single generic function, `tree_map` -- albeit, in C, mediated by macros or void* -- which we can use to access all the other generic functions, as long as we have one concrete instance.

Maybe at this point you're screaming at me, "what if foo() needed to write to the list? You'd need to turn a T1 into a T2 -- that's the wrong way around!" And... yes, that's correct! Functors are a way to organize these types in a coherent way. If you cared only about writing, there's a concept called a "contrafunctor" that relies on turning T1 into T2. And if you need both, there's a concept for that too. (They're all "functors", actually; it's just that what we traditionally call a plain-old functor is properly a "covariant functor".)

The point here is that we start with a bunch of unrelated types, that have some similarity we want to exploit for general functions, and we try to figure out how to exploit that similarity to write functions once that don't care about those differences.

Monads are functors where there's a particular kind of similarity that we want to exploit. This has already gotten long enough, and I don't want to overwhelm (any more than I have, anyway). In the end, you have a bunch of types, and some characteristics that all of them share. Functors let you organize those types according to their shared characteristics.

[0] https://rebelsky.cs.grinnell.edu/musings/cnix-macros-generic...

1. Implement a simple interpreter for the basic lambda calculus, no side-effects or I/O, something like [1]. You should have a discriminated union describing terms, lambdas and applications.

2. Now add two more node types to your union, one for a "print_line" command, and one for a "sequence" expression, that takes the left expression and passes it to a command on the right-hand side; the command is free to do something with the expression that was previously evaluated, or not.

This AST is the core of a monadic language. The basic operations of every monad are:

1. Wrap values in the monad: here you wrap values as an AST expression, let's call it Expr<T>.

2. Composition operator that accepts an Expr<T0> and a function T0->Expr<T1>: this is the sequence operator.

You can keep adding node types for more types of side-effects/commands (and handlers for those node types in your eval() function), but all you need is this "sequence" node type to handle an arbitrary number of side-effects in sequence, because a monad is basically a structured way to compose arbitrary computations.

Every sequence of operations won't necessarily make sense or compose well, because monads are actually too powerful to model effects, ie. they permit too much.

[1] https://github.com/io12/lambda/blob/master/lambda_calc.h

https://adit.io/posts/2013-04-17-functors,_applicatives,_and...

Not sure why, but treating everything as boxes makes all of the fancy FP abstractions on top make sense to me.

I think for C/assembly, the higher levels of abstractions aren't something you'll care about, because they're too costly. However, and apologies for the Rust code in a C++ thread, but I wrote this today and I think it demonstrates either the value or the horror of monads et al.

  let channel = app
      .channel
      .map(|c| Channel::from_str(&c))
      .transpose()?
      .unwrap_or(Channel::Stable);

The equivalent Rust code written in a more C-like style would be more verbose, something like this:

  let channel = if app.channel.is_some() {
      let parsed = Channel::from_str(&app.channel.unwrap());
      
      if parsed.is_ok() {
          parsed.unwrap()
      } else {
          return Err(parsed);
      }
  } else {
      Channel::Stable
  }

Ok, now consider a compound statement like { x; y; }. If there are more than two statements inside the braces, think of that as nested two-statement versions: {x; {y; z;} }. Please stretch your definition of C++ slightly so that statements are expressions, e.g. {x; y;} is an expression.

A "monadic" class in this scenario is a class that overloads the semicolon in compound statements. It expects the class members to have a method called "bind", so {x; y;} becomes "bind(x, [](a) { y })" (that is supposed to be a C++ lambda in the 2nd arg). The bind method receives the value from x and a lambda that it can choose to run this value through.

If the bind method simply takes the value of x and feeds it to the lambda, then it basically just runs x and y in sequence. The callback style should remind you of node.js if you are familiar with that. The obvious thing happens if you nest a bunch of these. This is how Haskell's I/O monad works: it just does the expressions in sequence. Rather than a compound statement with curly braces, Haskell uses a "do" block, but it's the same idea.

And, the idea also generalizes: instead of doing the expressions in sequence, it could spin off separate threads for each one and do them simultaneously (Haskell's Parallel monad), it could run some action over all the elements of a list (the List monad), etc.

Monads basically package the node.js control inversion and nested lambda cruft into a design pattern that lets you write what looks like straightforward sequential code, and also generalizes what it can do.

They are a traditional stumbling block in Haskell because several parts of Haskell interact to make them work: the semantics (described above), the type system (omitted here), and the implementations of specific monads (I gave a few examples like IO, Parallel, and List, but there are more). So you have to examine a few existing monads and understand how they are used, before the whole idea really makes sense. There is a good document called the "Typeclassopedia" that gives more examples.

I hope this helps!