[HN Gopher] The Monad Called Free
___________________________________________________________________
The Monad Called Free
Author : romes
Score : 53 points
Date : 2026-02-02 20:02 UTC (4 days ago)
(HTM) web link (blog.sigfpe.com)
(TXT) w3m dump (blog.sigfpe.com)
| gylterud wrote:
| I owe so much to this blog! It was such an inspiring read when I
| started out programming in Haskell back in 2007.
|
| Today I am a professor in computer science and still draw on it
| for examples in my advanced functional programming course. Just
| last week we did the loeb function, as an example of interesting
| use of Functor.
|
| Loeb function: http://blog.sigfpe.com/2006/11/from-l-theorem-to-
| spreadsheet...
| ddellacosta wrote:
| Yeah this is such an important blog for Haskell.
|
| A classic that everyone should read:
| http://blog.sigfpe.com/2006/08/you-could-have-invented-monad...
|
| I attended a talk of his at Papers We Love at Strange Loop in
| 2018, I didn't really read the description and I was vaguely
| expecting something Haskell related, and instead got this:
| https://www.youtube.com/watch?v=766obijdpuU
|
| I could barely understand it, but was impressed by what I could
| grasp. Dan Piponi's range is amazing, dude is brilliant
| mcbuilder wrote:
| Free Monads are everywhere. Learning Haskell at this time was
| such an amazing experience. Haskell has incredible library
| stability, the kmettoverse feels the same, my is still good
| enough for most situations, there are new streaming libraries but
| accomplish the same things as conduit and pipes. LLMs are as
| decent as you would expect on Haskell, and have helped me debug
| some situations where I would be fighting GHC usually with some
| flags turned out. AI has actually has been helpful in learning
| since in Haskell once you figure something out you solve it for a
| whole class of problems, the issues is sometimes figuring that
| one thing out it's so abstract you feel like you are hitting a
| cliff. Excited to be writing Haskell still in 2026, I hope it
| continues to avoid success at all cost.
| anon291 wrote:
| Monads, arrows, applicatives, and functors make the world go
| round.
| ivanjermakov wrote:
| People think category theory is weird and confusing, but
| really it just managed to name things (classes) that before
| were just "things". One might not know what monad or functor
| is, but they surely used it and have intuition on how it
| works.
| KPGv2 wrote:
| Right. I don't know how many times I've been exasperated by
| how monads are perceived as difficult.
|
| Do you understand "flatmap"? Good, that's literally all a
| monad is: a flatmappable.
|
| Technically it's also an applicative functor, but at the
| end of the day, that gives us a few trivial things:
|
| - a constructor (i.e., a way to put something inside your
| monad, exactly how `[1]` constructs a list out of a natural
| number)
|
| - map (everyone understands this bc we use them with lists
| constantly)
|
| - ap, which is basically just "map for things with more
| than one parameter"
|
| Monads are _easy_. But when you tell someone "well it's a
| box and you can unwrap it and modify things with a function
| that also returns a box, and you unwrap that box take the
| thing out and put it inside the original box--
|
| No. It is a flatmappable. That's it. Can you flatmap a
| list? Good. Then you already can use the entirety of monad-
| specific properties.
|
| When you start talking about Maybe, Either, etc. then
| you've moved from explaining monads to explaining something
| else.
|
| It's like saying "classes are easy" and then someone says
| "yeah well what about InterfaceOrienterMethodContainerArran
| geableFilterableClass::filter" that's not a class! That's
| one method in a specific class. Not knowing it doesn't mean
| you don't understand classes. It just means you don't have
| the standard library memorized!
| michaelsbradley wrote:
| People have different "aha" moments with monads. For me,
| it was realizing that something being a monad has to do
| with the _type /class_ fitting the monad laws. If the
| monad laws hold for the type/class then you've got a
| monad, otherwise not.
|
| So then when you look at List, Maybe, Either, et al. it's
| interesting to see how their conforming to the laws
| "unpacks" differently with respect to what they each _do_
| differently (what 's happening to the data in your
| program), but the laws are just the same.
|
| The reason this was an aha moment for me is that I
| struggled with wanting to understand a monad as another
| kind of _thing_ -- _" I understand what a function is, I
| understand what objects and primitive values are, but I
| don't get that List and Maybe and Either are the same
| kind of thing, they seem like totally different things!"_
| KPGv2 wrote:
| Yes, I 100% agree. But I want to mention something that
| isn't a disagreement, just a further nuance:
|
| 1. my explanation of monad is sufficient for people who
| need to _use_ them
|
| 2. your explanation of monad is necessary for people who
| might want to invent new ones
|
| What I mean by this is that if you want to invent a new
| monad, you need to make sure your idea conforms to the
| monad laws. But if you're just going to consume existing
| monads, you don't need to know this. You only need to
| know the functions to work with a monad: flatmap (or map
| + flatten), ap(ply), bind/of/just. Everything else is
| specific to a given monad. Like an either's toOptional is
| not monadic. It's just turning Left _ into None and Right
| an into Some a.
|
| And needing to know these properties "work" is
| unnecessary, as their very existence in the library is
| pretty solid evidence that you can use them, haha.
| kmeisthax wrote:
| It's also important to note that in Haskell and other
| functional programming languages, there is no implied
| order of operations. You need a Monad type in order to
| express that certain things are supposed to happen after
| other things. Monads can also express that certain things
| happen "in between" two operations, which is why we have
| different kinds of Monads and mathematical axioms of what
| they're all supposed to do.
|
| Outside of FP however, this seems really stupid. We're
| used to operations that happen in the order you wrote
| them in and function applications that just so happen to
| also print things to the screen or send bits across the
| network. If you live in this world, like most people do,
| then "flatmap" is a good metaphor for Monads because
| that's basically all they do in an imperative
| language[1].
|
| Well, that, and async code. JavaScript decided to
| standardize on a Monad-shaped "thenable" specification
| for representing asynchronous processes, where most other
| programming languages would have gone with green threads
| or some other software-transparent async mechanism. To be
| clear, it's better than the callback soup you'd normally
| have[0], but working with bare Thenables is still
| painful. Just like working with bare Monads - which is
| why Haskell and JavaScript both have syntax to work
| around them (await/async, do, etc).
|
| Maybe/Either get talked about because they're the
| simplest Monads you can make, but it makes Monads sound
| like a spicy container type.
|
| [0] The FP people call this "continuation-passing style"
|
| [1] To be clear, Monads don't have to be list-shaped and
| most Monads aren't.
| lisper wrote:
| > You need a Monad type in order to express that certain
| things are supposed to happen after other things
|
| This is the kind of explanation that drives me absolutely
| batshit crazy because it is fundamentally at odds with:
|
| > Do you understand "flatmap"? Good, that's literally all
| a monad is: a flatmappable.
|
| So, I _think_ I understand flatmap, assuming that this is
| what you mean:
|
| https://www.w3schools.com/Jsref/jsref_array_flatmap.asp
|
| But this has absolutely nothing to do with "certain
| things are supposed to happen after other things", and
| CANNOT POSSIBLY have anything to do with that. Flatmap is
| a purely functional concept, and in the context of things
| that are purely functional, nothing ever actually
| _happens_. That 's the _whole point_ of "functional" as
| a concept. It cleanly separates the _result_ of a
| computation from the _process_ used to produce that
| result.
|
| So one of your "simple" explanations must be wrong.
| anon291 wrote:
| Because you're not used to abstract algebra. JavaScript
| arrays form a monad with flatmap as the join operator.
| There are multiple ways to make a monad with list like
| structures.
|
| And you are correct. Monads have nothing to do with
| sequencing (I mean any more than any other non
| commutative operator -- remember x^2 is not the same as
| 2^x)
|
| Haskell handles sequencing by reducing to weak head
| normal form which is controlled by case matching. There
| is no connection to monads in general. The IO monad uses
| case matching in its implementation of flatmap to achieve
| a sensible ordering.
|
| As for JavaScript flat map, a.flatMap(b).flatMap(c) is
| the same as a.flatMap(function (x) { return
| b(x).flatMap(c);}).
|
| This is the same as promises: a.then(b).then(c) is the
| same as a.then(function (x) { return b(x).then(c)}).
|
| Literally everything for which this is true forms a monad
| and the monad laws apply.
| anon291 wrote:
| There is an implied order of operations in Haskell.
| Haskell always reduces to weak head normal form. This
| implies an ordering.
|
| Monads have nothing to do with order (they follow the
| same ordering as Haskell's normalization guarantees).
|
| > JavaScript decided to standardize on a Monad-shaped
| "thenable" specification for representing asynchronous
| processes,
|
| Its impossible for something to be monad shaped. All
| asynchronous interfaces form a monad whether you decide
| to follow the Haskell monad type class or decide to do
| something else. They're all isomorphic and form a monad.
| Any model of computation forms a monad.
|
| Assembly language quite literally forms a category over
| the monoid of endo functors.
|
| Jacquard loom programming also forms a category over the
| monoid of endo functors because all processes that
| sequence things with state form such a thing, whether you
| know that or not.
|
| It's like claiming the Indians invented numbers to fit
| the addition algorithm. Putting the cart before the
| horse, because all formations of the natural numbers form
| a natural group/ring with addition and multiplication
| formed the standard way (they also all form separate
| groups and rings, that we barely ever use).
| WorldMaker wrote:
| > Maybe/Either get talked about because they're the
| simplest Monads you can make, but it makes Monads sound
| like a spicy container type.
|
| Actually "spicy container type" is maybe a better
| definition of Monad than you may think. There's a weird
| sort of learning curve for Monads where the initial
| reaction is "it's just a spicy container type", you learn
| a bit and get to "it is not just a spicy container type",
| then eventually you learn a lot more and get to "sure
| fine, it's just a spicy container type, but I was wrong
| about what 'container' even means" and then settle back
| down to "it's a spicy container type, lol".
|
| "It's a spicy container type" and "it's anything that is
| flatmappable" are two very related simplifications, if
| "container" is a good word for "a thing that is
| flatmappable". It's a terrible tautological definition,
| but it's actually not as bad of a definition as it
| sounds. (Naming things is hard, especially when you get
| way out into mathematical abstractions land.)
|
| There are flatmappable things that don't have anything to
| do with ordering or sequencing. Maybe is a decent
| example: you only have a current state, you have no idea
| what the past states were or what order they were in.
|
| Flatmappable things are generally (but not always) non-
| commutative: if you flatmap A into B you get a different
| thing than if you flatmap B into A. That _can_ represent
| sequencing. With a Promise `A.then(() = > B)` is
| different sequence than `B.then(() => A)`. But that's as
| much "domain specific" to the Promise Monad and what its
| flatmap operation _is_ (which we commonly call `then` to
| make it a bit more obvious what its flatmap operation
| _does_ , it sequences; A then B) than anything
| fundamental to a Monad. The fundamental part is that it
| has a flatmap operator (or bind or then or SelectMany or
| many other language or domain-specific names), not
| anything to do with what that flatmap operator _does_
| (how it is implemented).
| wat10000 wrote:
| > Do you understand "flatmap"? Good, that's literally all
| a monad is: a flatmappable.
|
| Awesome! Now I understand.
|
| > Technically it's also an applicative functor
|
| Aaaand you've lost me. This is probably why people think
| monads are difficult. The explanations keep involving
| these unfamiliar terms and act like we need to already
| know them to understand monads. You say it's just a
| flatmappable, but then it's also this other thing that
| gives you more?
| nine_k wrote:
| But words like "incapsulation" or "polymorphism" or even
| "autoincrement" also sound unfamiliar and scary to a
| young kid who encounters them the first time. But the kid
| learns their meaning along the way, in a desire to build
| their own a game, or something. The feeling that one
| already knows a lot, sort of enough, and it'd be painful
| and boring to learn another abstract thing is a grown-up
| problem :-\
| Nevermark wrote:
| Those words need definitions, but they can both be
| defined using words most people know.
|
| Casual attempts at defining Monads often just sweep a
| pile of confusion around a room for a while, until
| everything gets hidden behind whatever odd piece of
| furniture that is familiar to the person generating the
| definition. They then imagine they have cleared up the
| confusion, but it is still there.
| nine_k wrote:
| Most engineers don't have too much trouble understanding
| things like List<T>, or Promise<T>, or even Optional<T>,
| which all demonstrate vividly what a monad does (except
| Promise in JS that auto-flattens).
|
| A monad is a generalization of all them. It's a structure
| that covers values of type T, some "payload" (maybe one,
| like Promise, maybe many, like List, maybe even none,
| like List or Optional sometimes). You can ask it to do
| some operations on these values "inside", it's the map()
| operation. You can ask it to do similar thing when
| operation on each value produces a nested structure of
| the same kind, and flatten them into one level again:
| this is flatMap(). This is how Promises are chained. The
| result is again a structure of the same kind, maybe with
| "payload" of a different type.
|
| This is a really simple abstraction, simpler than most
| GoF patterns, to my mind, and more fundamental and
| useful.
| anon291 wrote:
| I mean people need to be familiar with mathematics. In
| mathematics things form things without having to
| understand them.
|
| For example, The natural numbers form a ring and field
| over normal addition and multiplication , but you don't
| need to know ring theory to add numbers..
|
| People need to stop worrying about not understanding
| things. No one understands everything.
| wat10000 wrote:
| Now imagine if every single explanation of natural
| numbers talked about rings and fields. Nobody ever just
| says "they're the counting numbers starting from one." A
| few of them might say, "they're the counting numbers
| starting from one, and they form a ring and field over
| addition and multiplication." And I might think, I
| understand the first part, but I'm not sure what the
| second part is and it sounds important, so maybe I still
| don't know what natural numbers are.
|
| I'm not worried, but it's amusing to see this person say
| it's so simple, and then immediately trample on it.
| a57721 wrote:
| I get your point, but the natural numbers do not form a
| ring or field.
| anon291 wrote:
| Forget programming, everyday business and physics is
| monadic in function.
|
| And if-then statements are functorial.
|
| These are very general thought patterns.
| platinumrad wrote:
| These are vacuous statements.
| secretballot wrote:
| > everyday business and physics is monadic in function.
|
| So?
|
| > And if-then statements are functorial.
|
| So?
|
| All the "this is hard" stuff around these ideas seems to
| focus on managing to explain _what these things are_ but
| I found that to progress at the speed of reading (so,
| about as easy as anything can be) once it occurred to me
| to find explanations that used examples in languages I
| was familiar with, instead of Haskell or Haskell-inspired
| pseudocode.
|
| What I came out the other side of this with was: OK, I
| see what these are (that's incredibly simple, it turns
| out) and I even see how these ideas would be useful _in
| Haskell_ and some similar languages, because they solve
| problems with and help one communicate about problems
| particular to those languages. I do not see why it
| matters for... anything else, unless I were to go out of
| my way to find reasons to apply these ideas (and _why_
| would I do that? And no, I don 't find "to make your code
| more purely-functional" a compelling reason, I'm entirely
| fine with code I touch only selectively, _sometimes_
| engaging with or in any of that sort of thing).
|
| The "so?" is the part I found (and find) hard.
| skybrian wrote:
| I keep bouncing off this stuff due to the lack of concrete
| examples where it would be useful. Maybe some documentation
| organized like the Design Patterns book would be helpful?
| hutao wrote:
| A great way to understand monads is as a "design pattern,"
| because they pop up extremely often in practical programming.
| Consider functions with a type signature that looks like `A ->
| T<B>`, such as `A -> Promise<B>` or `A -> Optional<B>`.
|
| If you have some function fetchResponse that returns a
| Promise<Response>, and a function processJSON that takes a
| Response as an argument, you cannot compose them the usual way,
| as `processJSON(fetchResponse(x))`. Instead, you need to do
| `fetchReponse(x).then(processJSON)`, and the entire expression
| has to return another Promise. Ditto for functions that return
| an Optional.
|
| All data types that implement this design pattern have the
| structure of a monad. A monad consists of a generic type that
| is "covariant" in its type parameter (such as Promise or
| Optional), a way to embed a singular value into the data type,
| and a "then" method to compose the data type with a callback.
| Lists also implement the monad design pattern, and the "then"
| method for lists is flatmap. A monad basically lets you compose
| functions with a type signature that looks like `A -> T<B>`.
|
| Furthermore, each of these data types (Promises, Optionals,
| Lists) can be viewed as the output of some computation.
| Promises are produced whenever a function performs asynchronous
| IO, Optionals are produced when computations may return some
| "null" value, and Lists are returned if an algorithm may
| produce multiple solutions.
|
| Just like Promises have async/await syntactic sugar, similar
| syntactic sugar can be devised for other "monadic" types. For
| Optionals, the equivalent of async/await is null propagation
| (some languages have a `?` operator for this). For Lists, the
| equivalent of async/await is list comprehension, which "picks"
| each element from the list to build up a new list. Async/await,
| null propagation, and list comprehensions all have the same
| underlying structure, called a "monad."
|
| A "free monad" is a monad that does not implement any specific
| computation, but instead builds up an abstract syntax tree that
| needs to be interpreted. Free monads are useful because other
| monad instances can be implemented in terms of the free monad.
| skybrian wrote:
| This explanation doesn't contain any practical examples
| either. I mean, I do know that Promises are a monad, but
| that's not obviously helpful. You can write plenty of async
| code using Promises without knowing that, and it will
| probably be clearer to the reader. Similarly, options are a
| monad, but that's unhelpful for writing code that deals with
| optional values.
|
| Why is most writing about functional programming like this?
| jerf wrote:
| https://jerf.org/iri/post/2025/fp_lessons_purity/ may help,
| perhaps even especially if you are not a functional programmer.
|
| See also https://jerf.org/iri/post/2958/ .
| hutao wrote:
| It's serendipitous that I'm seeing this blog post on the front
| page today, because I'm currently writing an article discussing
| the free monad.
|
| In addition to the free monad presented in this post, there is a
| variant, called the "freer" monad, based on the "bind" operation
| instead of the "join" operation: data Freer f a
| where Pure :: a -> Freer f a Bind :: f a ->
| (a -> Freer f b) -> Freer f b
|
| I believe this definition originates from the following paper by
| Oleg Kiselyov and Hiromi Ishii:
| https://okmij.org/ftp/Haskell/extensible/more.pdf
|
| When thinking of monads as giving the semantics of some
| computational strategy, it's easier to define them in terms of
| "bind" instead of "join." This way of defining monads is
| sometimes called a "Kleisli triple" because it is better
| suggestive of "Kleisli arrows," or functions of the signature `a
| -> m b`. The "bind" operation defines how to compose a monadic
| computation with its continuation, and from this perspective, the
| "freer" monad resembles an abstract syntax tree.
|
| Originally, Eugenio Moggi proposed monads as a technique for
| specifying the denotational semantics of programming languages.
| All Java programs "really" happen in the IO + Either monads,
| because all Java programs may perform IO and throw exceptions. To
| my understanding, free monads are the monad that OCaml 5 runs in,
| because they give the semantics for effect handlers (or resumable
| exceptions).
| platinumrad wrote:
| > All Java programs "really" happen in the IO + Either monads
|
| People say things like this all the time, and I think it's a
| vacuous assertion. While there is probably some very narrow
| view where returning early with an error, throwing an
| exception, and binding in Either are the same thing, such a
| view ignores a lot of important context (e.g. all of imperative
| programming). This is why you have to qualify it as "IO +
| Either", but that doesn't say anything at all because
| everything is possible in IO.
___________________________________________________________________
(page generated 2026-02-06 23:01 UTC)