> with a C/assembly background? Interesting! I normally explain monads (and functors, which they're based on) starting from generics/templates, which C doesn't

> with a C/assembly background? 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-generics https://rebelsky.cs.grinnell.edu/musings/cnix-macros-generic...