5 ms·

The Monad Called Free (2014)

66 points by romes 8mo ago

gylterud 8mo ago
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.html?m=1 http://blog.sigfpe.com/2006/11/from-l-theorem-to-spreadsheet...
- ddellacosta 8mo ago
  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-monads-and.html 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 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 8mo ago
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 8mo ago
  Monads, arrows, applicatives, and functors make the world go round.
  - ivanjermakov 8mo ago
    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 8mo ago
      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 InterfaceOrienterMethodContainerArrangeableFilterableClass::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 8mo ago
        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!"
skybrian 8mo ago
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 8mo ago
 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`, such as `A -> Promise` or `A -> Optional`. 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`. 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 8mo ago
hutao 8mo ago
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 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 8mo ago
  > 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.

66 points by romes 8mo ago

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.html?m=1 http://blog.sigfpe.com/2006/11/from-l-theorem-to-spreadsheet...

ddellacosta 8mo ago
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-monads-and.html 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 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 8mo ago

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 8mo ago
Monads, arrows, applicatives, and functors make the world go round.
- ivanjermakov 8mo ago
  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 8mo ago
    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 InterfaceOrienterMethodContainerArrangeableFilterableClass::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 8mo ago
      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!"

skybrian 8mo ago

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 8mo ago
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`, such as `A -> Promise` or `A -> Optional`. 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`. 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 8mo ago

hutao 8mo ago

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 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 8mo ago
> 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.