Live data from Hacker News

List is a monad

alexyorke.github.io

101–110 of 187 posts

Re: List is a monad

#101
Monad tutorials are on the rise again.

Let's start with function composition. We know that for any two types A and B we can consider functions from A to B, written A -> B. We can also compose them, the heart of sequentiality. If f: A -> B and g: B -> C then we might write (f;g) or (g . f) as two different, equivalent syntaxes for doing one thing and then the other, f and then g.

I'll posit this is an extremely fundamental idea of "sequence". Sure something like [a, b, c] is also a sequence, but (f;g) really shows us the idea of piping, of one operation following the first. This is because of how composition is only defined for things with compatible input and output types. It's a little implicit promise that we're feeding the output of f into g, not just putting them side-by-side on the shelf to admire.

Anyway, we characterize composition in two ways. First, we want to be clear that composition only cares about the order that the pipes are plugged together, not how you assemble them. Specifically, for three functions, f: A->B, g: B->C, h: C->D, (f;g);h = f;(g;h). The parentheses don't matter.

Second, we know that for any type A there's the "do nothing" identity function id_A: A->A. This doesn't have to exist, but it does and it's useful. It helps us characterize composition again by saying that f;id = id;f = f. If you're playing along by metaphor to lists, id is the empty list.

Together, composition and identity and the rules of associativity (parentheses don't matter) and how we can omit identity really serve to show what the idea of "sequences of pipes" mean. This is a super popular structure (technically, a category) and whenever you see it you can get a large intuition that some kind of sequencing might be happening.

Now, let's consider a slightly different sort of function. Given any type types, what about the functions A -> F B for some fixed other type F. F here exists to somehow "modulate" B, annotate it with additional meaning. Having a value of F B is kind of like having a value of type B, but maybe seen through some kind of lens.

Presumably, we care about that particular sort of lens and you can go look up dozens of useful choices of F later, but for now we can just focus on how functions A -> F B sort of still look like little machines that we might want to pipe together. Maybe we'd like there to be composition and identity here as well.

It should be obvious that we can't use identity or composition from normal function spaces. They don't type-check (id_A: A -> A, not A -> F A) and they don't semantically make sense (we don't offhand have a way to get Bs out of an F B, which would be the obvious way to "pipe" the result onward in composition).

But let's say that for some type constructors F, they did make sense. We'd have for any type A a function pure_A: A -> F A as well as a kind of composition such that f: A -> F B and g: B -> F C become f >=> g : A -> F C. These operations might only exist for some kinds of F, but whenever they do exist we'd again capture this very primal form of sequencing that we had with functions above.

We'd again capture the idea of little A -> F B machines which can be plugged into one another as long as their input and output types align and built into larger and larger sequences of piped machines. It's a very pleasant kind of structure, easy to work with.

And those F which support these operations (and follow the associativity and identity rules) are exactly the things we call monads. They're type constructors which allow for sequential piping very similar to how we can compose normal functions.

Re: List is a monad

#102
post #5

As far as monad tutorials go, this one seems quite good. I like the categorization of monads between "containers" and "recipes". However, I personally think that monad tutorials tend to give people the wrong impression and leave them more confused than they were before, because they focus on the wrong thing. A monad is not a complex concept, at all. IMO a more useful way to present the topic would be with one separat…

I mean at it's most basic "monads" are

-a data type with some hidden information

-a lot of functions that can ignore that hidden information

-some functions that can act (switch|add|mutate|signal|sequence) on that hidden information

people seem to think talking about flatMap somehow makes this intuitive despite the tautological issue of flatMap only making sense if you already know what's going on.

Re: List is a monad

#103
post #5

As far as monad tutorials go, this one seems quite good. I like the categorization of monads between "containers" and "recipes". However, I personally think that monad tutorials tend to give people the wrong impression and leave them more confused than they were before, because they focus on the wrong thing. A monad is not a complex concept, at all. IMO a more useful way to present the topic would be with one separat…

Yes, and I don't even see the value in generalizing to one Monad concept. It only makes things worse, as then one is tempted to share terminology between different kinds of monads. E.g. there's no reason Maybe's flatMap is called the same as List's flatMap, it might be more readable to call them differently, as some libraries do.

Re: List is a monad

#104
post #21
post #5

As far as monad tutorials go, this one seems quite good. I like the categorization of monads between "containers" and "recipes". However, I personally think that monad tutorials tend to give people the wrong impression and leave them more confused than they were before, because they focus on the wrong thing. A monad is not a complex concept, at all. IMO a more useful way to present the topic would be with one separat…

> one separate lesson for every common monad instance. Right on. This is the "What Are Monads" fallacy : https://entropicthoughts.com/the-what-are-monads-fallacy

Wow, this is a great post, thank you for sharing. It echoes my thoughts exactly.

Re: List is a monad

#105
post #5

As far as monad tutorials go, this one seems quite good. I like the categorization of monads between "containers" and "recipes". However, I personally think that monad tutorials tend to give people the wrong impression and leave them more confused than they were before, because they focus on the wrong thing. A monad is not a complex concept, at all. IMO a more useful way to present the topic would be with one separat…

> That's why the pattern is so useful in the first place How useful, really? Monads don't even universally compose, which is what most people sell the concept for.

Monads don't compose between different instances, but monad transformers do.

Re: List is a monad

#106
post #46

Earlier quoted context omitted.

> There's at least one other practical advantage as well, that of "chunking". > When we have a grasp of relevant, powerful structures underlying our world, we can "chunk" along them to reason more quickly. This is one thing I've observed about Haskell vs. other languages: it more readily gives names and abstractions to even the minutest and most trivial patterns in software, so that seemingly novel problems can be qu…

Note that this is general enough that you don't need a Monad for this. Applicative is enough (liftA2).

Not if you need to perform two /Monadic/ operations as the commenter stated explicitly.

Re: List is a monad

#107
post #50

I think the most intuitive description for a monad I've ever seen is 'flatMappable'. Context: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... Usually articles that describe them in a very Math-y way go above my head. But the definition above was immediately clear (I saw it on HN). I think this article is a bit more approachable than others I've read, but it still gets very confusing near the end.

Reminds me on an analogy for a monad I once heard. Not sure if it is correct because I lack the mathematical understanding to verify. Anyway, a nested To-Do list is (allegedly) a common form of a monad. Say I am trying to clean my whole house. Well, I could have an item for a task like cleaning the kitchen that has each task I need to do in the kitchen in order for the kitchen to be cleaned. I can do the same for the…

Not exactly. The flatMap() operation itself isn’t going to flatten an arbitrarily nested todo list. It just concatenates the lists that are returned after applying the callback to each item.

The monad part is about what happens if you call flatMap() repeatedly. That is, each call to flatMap() is one action, and these actions can be nested without affecting the result.

Re: List is a monad

#108
So I come at this from a math background but I’ve always found these explanations to be overly complex. In the parlance of C++, I think of a monad as a template class T with the following properties:

1. For any class X, there is a canonical method

  F: X -> T
2. For any class X, there is a canonical method

  G: T> -> T.
3. For classes X and Y, and any method

  f: X -> Y, 
there is a corresponding method

  “T”: T -> T.

—————-

Here “any type” means any type that is compatible with the template.

And then there’s some additional rules which make all these methods compatible, based on the different ways of stacking nested T’s and the “canonical” maps you get. Admittedly there is some confusing accounting here, but I also think most natural ways of constructing the above three requirements are going to satisfy them anyway. For List and Maybe it’s fairly obvious what the above methods are.

I dunno, maybe I have it wrong and someone can correct my understanding.

Re: List is a monad

#109

Earlier quoted context omitted.

Note that this is general enough that you don't need a Monad for this. Applicative is enough (liftA2).

Not if you need to perform two /Monadic/ operations as the commenter stated explicitly.

Every monad is also an applicative and liftA2 does/is the same thing as liftM2. The only reason they both exist was due to Monad being popularized in Haskell earlier than Applicative and thus not having it as a superclass until the Functor-Applicative-Monad Proposal in Haskell 2014. It was obviously correct, but a major breaking change that also got pork barreled a bit and so took a while to land.

Re: List is a monad

#110

Earlier quoted context omitted.

Could you elaborate on that? What does 'flatMappable' mean in this context?

This is a good explanation: https://users.scala-lang.org/t/what-is-a-monad-in-scala/4169 It's like... what would you call all types that have a .write() method? Writable right? What would you call all types that have a .dispose() method? Disposable. What would you call all types that have a .flatMap() method? Monad obviously.

That’s because flatMap() is a good name for a particular list operation, but it’s not generic enough to be a good name for the corresponding monad operation.

I’m not sure there is a good name for the monad operation. Sometimes it’s called ‘bind’ but what does it bind?

I suppose you could call it ‘then’ like when working with Promises.

Post reply on HN