Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Monad Called Free (2014)

blog.sigfpe.com

Post reply on HN
Print view View original

11–20 of 44 posts

Re: The Monad Called Free (2014)

#11

Post by hutao »

skybrian wrote: post #9

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?

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, 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.

Re: The Monad Called Free (2014)

#12

Post by kmeisthax »

KPGv2 wrote: post #7
ivanjermakov wrote: post #5

Earlier quoted context omitted.

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.

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) -…

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.

Re: The Monad Called Free (2014)

#13

Post by KPGv2 »

michaelsbradley wrote: post #8
KPGv2 wrote: post #7

Earlier quoted context omitted.

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) -…

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 (wh…

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.

Re: The Monad Called Free (2014)

#14

Post by lisper »

kmeisthax wrote: post #12
KPGv2 wrote: post #7

Earlier quoted context omitted.

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) -…

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.…

> 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.

Re: The Monad Called Free (2014)

#15

Post by jerf »

skybrian wrote: post #9

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?

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/ .

Re: The Monad Called Free (2014)

#16

Post by wat10000 »

KPGv2 wrote: post #7
ivanjermakov wrote: post #5

Earlier quoted context omitted.

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.

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) -…

> 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?

Re: The Monad Called Free (2014)

#17

Post by nine_k »

wat10000 wrote: post #16
KPGv2 wrote: post #7

Earlier quoted context omitted.

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) -…

> 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 othe…

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 :-\

Re: The Monad Called Free (2014)

#18

Post by platinumrad »

hutao wrote: post #10

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…

> 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.

Re: The Monad Called Free (2014)

#19

Post by anon291 »

KPGv2 wrote: post #7
ivanjermakov wrote: post #5

Earlier quoted context omitted.

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.

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) -…

Forget programming, everyday business and physics is monadic in function.

And if-then statements are functorial.

These are very general thought patterns.

Re: The Monad Called Free (2014)

#20

Post by anon291 »

kmeisthax wrote: post #12
KPGv2 wrote: post #7

Earlier quoted context omitted.

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) -…

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.…

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).

Post reply on HN