8 ms·

List is a monad

157 points by polygot 1y ago

1-more 1y ago
IDK if it ads anything to the article, but `map` is a property of Functors, and every Monad is a Functor. Well, every Monad is an Applicative Functor, and every applicative functor is a functor. All a way of saying that, yep, you always have `map` when you have a Monad, but you don't need a Monad to have `map`. If you want an example we can compare a regular list and a Ziplist. A regular list's Applicative instance does a cross product, while a Ziplist's applicative instance does a dot product. (*) <$> [2,3] <*> [5,7, 11] --> [10,14,22,15,21,33] getZipList $ fmap show $ (*) <$> ZipList [2,3] <*> ZipList [5,7, 11] --> ["10","21"] There's no great way to write a Monad instance for ZipList. But it's an Applicative Functor and thus is also a Functor and thus you can map over it. https://www.mail-archive.com/haskell-cafe@haskell.org/msg57217.html https://www.mail-archive.com/haskell-cafe@haskell.org/msg572... For quirky reasons in Haskell, `fmap` the function implemented for every Functor instance. This is because `map` was already taken by lists. Weird, I know.
revskill 1y ago
U must prove it is a monoid in the category of endofuncors.
- rebeccaskinner 1y ago
  join has the type `m (m a) -> m a`. That's the thing that really shows off the monoidal structure. People normally implement monads in terms of bind, but you can easily define join in terms of bind for any Monad: `join ma = ma >>= id`. So really, as long as you have a lawful instance of Monad written with bind the existence of join is your proof.
- hirvi74 1y ago
  > monoid in the category of endofuncors. I do not even know what a monoid or an endofuncor is. While I enjoy math, despite not being the best at it, I am confident I never made it this far in my studies. I looked at the Wikipedia definitions, and I am even more confused now.
  - 1-more 1y ago
    https://bartoszmilewski.com/2016/12/27/monads-categorically/ https://bartoszmilewski.com/2016/12/27/monads-categorically/ This is a book chapter, and you need the preceding chapters to grasp it I think. I'm still in the middle of it.
robinhouston 1y ago
I expect the author has done this knowingly, but the title is rather painful for a mathematician to read. A list is not a monad. List is a monad. A list is an algebra for the List monad.
- leoh 1y ago
  I appreciate you mentioning this because I think it’s actually an important point
- Garlef 1y ago
  What you said is not correct! In detail: * "A list is not a monad" - True! * "List is a monad" - True. But I think "`List` is a monad" might be clearer. * "A list is an algebra for the `List` monad." - False! What's correct is the following: * "An algebra for the `List` Monad is precisely a monoid." Sketch of the construction: (an algebra for the list monad is a monoid): Recall that an algebra is a set/type `A` together with a function `mult: List A -> A` together with some axioms. Think of such a function `mult: List A -> A` as the function that assigns to each list with elements in `A` the product over all those elements. The aforementioned axioms boil down to: (1) `mult([])` is a neutral element and (2) `mult` is an associative binary operation when restricted to two-element lists. (a monoid is an algebra for the list monad): Same Idea - Given a monoid, we define a function `mult: List A -> A` by assigning to a list of elements of `A` the product of these elements. And the empty list we assign to the neutral element. Then we can use the associativity and properties of the neutral element to show that this function constitutes an algebra for the list monad.
  - robinhouston 1y ago
    You're quite right! Thanks for the correction. I should have said that a list is an element of a free algebra over the List monad, which is less pithy.
- polygot 1y ago
  Thanks for the feedback! I can definitely rename the post soon as a first step, although this may require rewriting a chunk of the article to more accurately reflect the fact that List is a monad, and not "a" list. I could make this distinction in part 3 (not written yet) although I want to balance not misleading readers, but not overcomplicating it too early on.
brooke2k 1y ago
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 separate lesson for every common monad instance. Start with Maybe, then IO, then maybe State and List, and so on... because ultimately, every instance of a Monad works very differently. That's why the pattern is so useful in the first place, because it applies to so many places. (Note: this is a criticism of monad tutorials in general, not this one in particular, which seems to do a decent job on this front). In my experience, people new to Haskell focus way too much on getting the "a-ha" moment for monads in general, when really you want a bunch of separate "a-ha" moments as you realize how each instance of a monad takes advantage of the pattern differently. I also tend to think that monads are best demonstrated in Haskell rather than in other languages, if only because the notation is so much less clunky. That may just be me though. (EDIT: well, also because almost no other languages have typeclasses, so you have to approximate it with interfaces/traits/etc) Also FYI: in part 2, the code examples have extra newlines in between every line, which makes it hard to read (I'm on firefox, if that matters).
- pdhborges 1y ago
  If all monad instances work differently what is the value of the Monad interface? What kind of usefull generic code can one write against the Monad interface. Related: https://buttondown.com/j2kun/archive/weak-and-strong-algebraic-structures/ https://buttondown.com/j2kun/archive/weak-and-strong-algebra...
  - ChadNauseam 1y ago
    Lots of useful generic code. MapM is a version of `map` that works with any Monad, `sequence` works with any monad, and so on. These are used very frequently. But the bigger benefit is when syntax sugar like `do` notation comes in. Because it works for any Monad, people can write their own Monads and take advantage of the syntax sugar. That leads to an explosion of creativity unavailable to languages who "lock down" their syntax sugar to just what the language designers intended. In other words, what requires a change to other languages can often be a library in Haskell.
daxfohl 1y ago
Nit, in Haskell it's a MonadPlus. Which IIRC is a monad that supports filtering.
- ChadNauseam 1y ago
  In Haskell List is a Monad as well as MonadPlus. Since List's Monad instance is used probably 100x more than its MonadPlus instance, I think it makes sense to focus on that,
nyeah 1y ago
Let's keep up the mathiness. Look how much economics has benefitted from that.
draw_down 1y ago
[dead]
hackandthink 1y ago
Just for fun, monads as modalities is missing: https://hackage.haskell.org/package/Agda-2.6.4.2/docs/Agda-Syntax-Common.html#t:Cohesion https://hackage.haskell.org/package/Agda-2.6.4.2/docs/Agda-S...
jrjrjrjrjfjj 1y ago
Hi
Smaug123 1y ago
The article sort of danced around what I think is the most natural way List is a "recipe": it's the bounded nondeterminism monad (a `List<T>` is a nondeterministic result; one could implement `List<T> -> T` by selecting an answer uniformly at random from the finite multiset).
- perlgeek 1y ago
  I really like my lists to be deterministic. Seriously, I've read things about lists and nondeterminism a few times in this thread, and I can't help but wonder if "you guys" (functional programming nerds, maybe?) use the word "nondeterministic" different than the rest of the world? If not, I'd love a good explanation about what makes lists non-deterministic, and why we would want that, and why they seem to be perfectly deterministic in imperative programming languages.
  - housecarpenter 1y ago
    It is a particular sense of "nondeterminism", but it's not specific to functional programming, I think it's the usual one theoretical CS as a whole. It's the same sense in which "nondeterminism" is used in P vs NP, for example. Think of a computation as a process of changing state. At a given point in time, the computer is in a certain state, the current state. The computation can be described in terms of a function that acts on the current state. In a deterministic computation, the function takes in the current state, and produces a single state as output which will be the state the computer enters on the next tick. In a non-deterministic computation, the function takes in the current state and produces a set of states as output. These states are all the possible states the computer might enter on the next tick. We don't know (or just don't care) which one of these states it will enter. You can model a non-deterministic computation as a deterministic one, by using a list `currentStates` to store the set of all possible current states of the computation. At each "tick", you do `currentStates = flatMap(nextStates, currentStates)` to "progress" the computation. In the end `currentStates` will be the set of all possible end states (and you could do some further processing to choose a specific end state, e.g. at random, if you wish, but you could also just work with the set of end states as a whole). It's in this sense that "a list is a non-deterministic result", although this is really just one thing a list can represent; a list is a generic data structure which can represent all sorts of things, one of which is a non-deterministic result.
mikelitoris 1y ago
A list is like a burrito
- zahlman 1y ago
  It's just a loust in the category of endosequences.
  - accoil 1y ago
    I think that was the article that made me actually try to understand "A monad is just a monoid in the category of endofunctors". Researching "endofunctor" helped significantly more than any of the analogies floating around at the time.
gr4vityWall 1y ago
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/Reference/Global_Objects/Array/flatMap 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.
- aadhavans 1y ago
  Could you elaborate on that? What does 'flatMappable' mean in this context?
  - IshKebab 1y ago
    This is a good explanation: https://users.scala-lang.org/t/what-is-a-monad-in-scala/4169 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.
    - skybrian 1y ago
      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.
      - still_grokking 1y ago
        Scala's new effect library Kyo just uses `map`. See: https://getkyo.io/#/?id=the-quotpendingquot-type-lt https://getkyo.io/#/?id=the-quotpendingquot-type-lt All pure values are automatically lifted into the Kyo monad, so `map` is effectively `flatMap`. From the linked docs: > This unique property removes the need to juggle between map and flatMap. All values are automatically promoted to a Kyo computation with zero pending effects, enabling you to focus on your application logic rather than the intricacies of effect handling. In the end it makes a lot of sense I think. What you do is manipulating values inside some wrapper. Whether this wrapper is a monad or not should not matter. Just do something with the value(s) inside, and that's mapping.
nemo1618 1y ago
I think this adds more confusion than it removes. A list is not a monad. A list is a data structure; a monad is more like a "trait" or "interface." So you can define a List type that "implements" the monad interface, but this is not an inherent property of lists themselves. That's the sense in which a list "is a" monad: the OOP sense. Haskell's List monad provides a model for nondeterminism. But that certainly isn't the only way List could satisfy the monad interface! It was a deliberate choice -- a good choice, possibly the best choice, but a choice nonetheless.
- blakehawkins 1y ago
  Can you explain the nondeterminism part of your comment more?
  - ryandv 1y ago
    Determinism, in that given some set of inputs you only ever receive one output. Non-determinism, in that given some set of inputs it's possible to receive a collection (a list) of possible outputs. With lists you can express things like all possible pairings of all possible outcomes, or the Cartesian product: ghci> liftM2 (,) ['a', 'b', 'c'] [1,2,3] [('a',1),('a',2),('a',3),('b',1),('b',2),('b',3),('c',1),('c',2),('c',3)] ... or in more explicit monadic do-notation: ghci> :{ ghci| do ghci| x <- ['a', 'b', 'c'] ghci| y <- [1,2,3] ghci| return (x, y) ghci| :} [('a',1),('a',2),('a',3),('b',1),('b',2),('b',3),('c',1),('c',2),('c',3)] and so on.
  - pkal 1y ago
    From automata theory, you might know that nondeterministic automata are represented by a set of states. Deterministic automata are always in a specific state, while nondeterministic ones are in multiple at once. Lists are used for non-determinism in Haskell the same way as a set, mainly because they are easier to implement. But the total order that a list induces over a set is not that relevant.
    - ryandv 1y ago
      That's right, and you see this directly reflected in the "types" of the transition functions for DFAs and NFAs, respectively [0] [1]: δ : Q × E ⟶ Q δ : Q × E ⟶ P(Q) ... where Q denotes the set of the automaton's states, E its alphabet of input symbols, and P the power set operation. Deterministic automata arrive at a definite, single state drawn from Q, while non-deterministic automata may arrive at a set (~list) of possible states, when given a current state from Q and next input symbol from E. [0] https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministic_finite_automaton [1] https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa...
FeelingsSparked 1y ago
[dead]
skybrian 1y ago
I like to think of a monad as a design pattern for constructing new objects where you pass in a sequence of callback functions, one at a time. A monad’s ‘bind’ operation adds another callback function to the end of a sequence. The monad interface only requires ways to construct object using callbacks. The ‘bind’ operation takes a callback as an argument, but says nothing about when it’s actually called; it could be immediately, deferred, multiple times, or even never. It’s up to the implementation of the monad, as well as the language, if it’s a lazy language. This is basically a framework. Like with other frameworks, the principle is “don’t call us; we’ll call you.” Arbitrary computation can happen between callbacks. The framework can do whatever control flow it wants, and this is what often makes frameworks opaque. Hiding control flow is what frameworks do, for better or worse. So far, none of this is specific to a Monad. The Monad part comes from the type signature of the callback function passed in to flatmap(), which allows ‘bind’ operations to be nested. Once you know what kind of thing you’re dealing with (frameworks) then you can go into why some frameworks qualify as a monad.
kelseyfrog 1y ago
While I can understand the desire to draw a metaphor, there are better approaches than saying, "A List Is a Monad". The statement as-is breaks pretty much immediately because, while there is a canonical list monad, there isn't a list monad, there are in fact several[1]. There are several more correct ways of phrasing the idea among: "List can be given a monad instance" "List forms a monad with pure and bind as defined" "List is the underlying functor of a monad" The point is that picking any old list implementation is likely not a monad without the supporting structure. Will any of these help you learn what a monad is? Likely not. Monadology is a Mary's Room[2] problem; there is a qualia, a subjective sensation, when one understands monads having experienced them first hand. Subsequently monad tutorials are the best case against physicalism[3] yet devised. 1. https://hackage.haskell.org/package/exotic-list-monads-1.1.0/docs/Control-Monad-List-Exotic.html https://hackage.haskell.org/package/exotic-list-monads-1.1.0... 2. https://en.wikipedia.org/wiki/Knowledge_argument https://en.wikipedia.org/wiki/Knowledge_argument 3. https://en.wikipedia.org/wiki/Physicalism https://en.wikipedia.org/wiki/Physicalism
- zzo38computer 1y ago
  Although there can be other monads (and stuff other than monads, such as ZipList) that can be made with lists, I think that such a monad would not necessarily be a "list monad". (Your link [1] has several examples of this.) You are right that it does not mean that "a list is a monad" and that your other phrasing is better, but it does not mean that "there isn't a list monad".
  - kelseyfrog 1y ago
    To me "a list monad" often subtly implies "one" list monad. I wasn't very clear, but the point I was trying to make was more along the line of singular vs plural. Thanks for pointing out the discrepancy.
drumnerd 1y ago
A monad is not a container! It’s a way of composing functions if they have an effect. You tell how to inject a value in that effect (unit) and how to compose two functions that have that effect and that’s it: programmable semicolons.
- mrkeen 1y ago
  And in the article's case, 'have an effect' means 'be a list'.
- polygot 1y ago
  Thanks for the feedback, I totally agree that monads are not containers. From an OOP perspective, they have some properties that make them, in some sense, sorta like containers, e.g., they contain a value like the Maybe monad. I still agree that they are not simply containers. I can clarify this in a revision to part 1 soon.
  - lmm 1y ago
    > From an OOP perspective, they have some properties that make them, in some sense, sorta like containers, e.g., they contain a value like the Maybe monad. Not always! I find this is a big source of confusion; not all monads contain values, sometimes beginners think they can or should "get the value out" of a monad and that tends to lead to writing the wrong kind of code.
ivanjermakov 1y ago
Misunderstanding of Monads is such an interesting phenomenon. Kind of similar to grasping 4D geometry or understanding the difference between a class and an object in OOP. List can be an instance of a monad, i.e. a monadic type. I think the trick to understanding monads is to see what benefits monad interface gives to the types that implement it.
kerblang 1y ago
The way I think of it, monads are a solution to Callback Hell, where you've fallen in love with lambdas, but now you have a nightmarish mess of lambdas in lambdas and lambdas calling lambdas. The monadic functions allow you to create "for comprehensions" aka "do comprehensions" but really, they look like a classic for-each loop. They secretly call the monadic map/flatMap/filter functions. for x in list doThings(x) These comprehensions have a strange bonus feature, that you can do nested "loops" all at once, and even add "guards" (little if statements) newlist= for x in list1 y in list2 if y > 3 z in list3 doThings(x, y, z) But again, the comprehension, when "de-sugared", is secretly calling the map/flatMap/filter functions of list1, list2, list3 to get our result. You as the author of a given monad can implement those functions however you want, and they're all 3 lambda based. But notice how the comprehension is flattening those lambdas out! Our callbacks in callbacks are much more readable like this. Without comprehensions, you can still implement monadic functions in any old language (probably in C...?), and they're handy in their own right, but you don't get the flattening-of-callback-hell magic.
- stronglikedan 1y ago
  After reading your comment, I've made it my mission to understand it. Although I have no idea what you're talking about, you make it sound intriguing.
  - teiferer 1y ago
    [dead]
  - kerblang 1y ago
    First off, I'm not sure it's even worth it to understand this stuff... Second, someone should be along to slam it soon enough and insist I've missed some gibberishy business that you'll never understand. With those caveats in mind, here's a more intensive scala-based monad tutorial I made: https://github.com/zaboople/techknow/blob/master/scala/monad/MonadTutorial.scala https://github.com/zaboople/techknow/blob/master/scala/monad... But really, don't burn up too much of your short life trying to come to terms with this stuff. There's a reason most languages don't get around to supporting Monads...
mvdtnz 1y ago
The amount of people who tie themselves into knots to understand this pointless concept is very funny to me. I am 16 years into a successful software engineering career without learning what a monad is an it never held me back. Turns out I can use lists and optional types and all that jazz without it. I mean really. Look at posts like this[0]. What does this give you? Nothing, in practical reality. Nothing. [0] https://news.ycombinator.com/item?id=44446472 https://news.ycombinator.com/item?id=44446472
- battle-racket 1y ago
  funny that you call it pointless then admit you never learned what it is
- lmm 1y ago
  > I am 16 years into a successful software engineering career without learning what a monad is an it never held me back. How would you know? That's the classic Blub Paradox. Being able to write a custom monad and then leverage the vast array of libraries that already exist has helped me deliver functionality to end users quicker, more maintainably, and with lower defect rates. They don't let you do anything that you couldn't do by writing it out longhand. But just like using generic container libraries instead of writing a specific container for every type you want to handle collections of, they're extremely helpful.
t43562 1y ago
Another tutorial which makes monads about 100x more impossible to understand for me by relating them to something else and describing all the weird ways that they are NOT that thing. IMO if you already have it, this will be a lovely comparison full of insight, but if you haven't then it's full of confusing statements. IMO what they are is utterly unimportant, except to mathematicians, and what you can do with them is more to the point. The fact that explanations are so often in Haskell just makes them more unintelligible because you really need to know what problem they solve.
- polygot 1y ago
  Thanks for the feedback! I'll likely be editing part 1 to include the feedback so far from the commenters as well. If there's a specific statement or analogy that felt especially confusing, please point it out and I'll clarify it in the post.
  - t43562 1y ago
    Sorry for moaning - it's just the usual despair that I feel every time I read a new explanation and fail to understand it. This isn't your fault.
- empath75 1y ago
  The reason that the explanations are all in Haskell is that Haskell is the only language that is reasonably popular that implements monad and calls it a monad, and 90% of the people looking up "What is a monad" are trying to learn Haskell.
  - t43562 1y ago
    Yes, you're doing 2 difficult things at the same time - a new language and a new concept. IMO it would be great to just have the concept to deal with.
benreesman 1y ago
In most programming languages the compiler authors go to great lengths to gives intuitive semantics to having one statement follow another, followed by another. This is an organizing principle for thinking about code and for having a program exist with well-defined semantics. But its not a very robust one: its never true of fast programs on realistic hardware for example (not for a long time now). And all the rule bending (-fstrict-alias, bunch of stuff) exists in this tension between the grade school natural language paradigm and the reality of computers. I say grade school not to be pejorative, but rather because it is roughly the boundary where written natural languages begin to have interesting tensions around past and future and simultaneous, changing and not changing. Functors and applicatives and monads and other type classes like these are the source of endless analogies because there isn't an accepted, broadly-understood terminology for this "well its roughly what would happen if you had a piece of paper and wrote things on it at every statement boundary and scratched off the old ones" (though Turing and von Neumann did formalize this in useful ways, they just don't generalize well to realistic computers anymore). Monads are the mathematical object that is forced on you if you want a rigorous way to describe the semantics of program execution in the vicinity of this "common sense" notion. That's really what everyone is dancing around: your program is only well defined with either: - a big rulebook full of exceptions and edge cases - a compositional rule strict enough to give some useful predictability but lax enough to admit most useful programs. It is this rigor/laxity tension as concerns text on a page and gates on a semiconductor that gives monads a privileged place in the towers of categories. When I worked on Sigma we were among the earlier adoptors of ApplicativeDo, for example, because we wanted a slightly different rigor/laxity tradeoff for performance reasons. Monads are what happens when you do shift the giant pile of "back of the book" compiler details that describe program execution semantics into a much simpler set of rules, but at the cost of increasing the barrier to entry because you need to know the rules before you can print "hello world".
acjohnson55 1y ago
I used to struggle with understanding the "receipe" metaphor for monads when it comes to lists. But a list (or, really any collection) as a monad can be thought of as the "discrete nondeterminism monad". Meaning that every collection is a set of possible inputs to the computation that is provided as the argument to a `flatMap` operation. Each `flatMap`, by definition, returns a new collection of possible outputs for each of the inputs, and each of those collections gets concatenated. Every item in the final output collection represents the result of following some path through the computations, selecting a single item at each step. Importantly, the type of the output of each `flatMap` operation can differ from the input. You can imagine extending this by assigning probabilities, or making the domain continuous (I think...). These extensions would still be monads, just without being simple collections. It's kind of like how multiplication over whole numbers is repeated addition, but that metaphor becomes less useful for other domains of numbers.
tombert 1y ago
Realizing that lists are monads is what made monads "click" for me. When I was first learning Haskell a million years ago, I was completely confused by the concept of a monad; I could, after enough fighting with the compiler, usually get something working, but it was a stochastic guess-and-check process trying to figure out what `IO` actually means. Even the `Maybe` was confusing to me, because I couldn't really figure out how the hell you relate something like "checking for null" with "writing to the disk". I can't remember where I saw it, probably on the Haskell wiki somewhere, but when they pointed out the List is a monad, and after seeing an example of how it worked, I suddenly got it: in a hand-wavey way, a monad is basically just a value with a wrapper context [1], and from a practical perspective that's all it is. In the case of a List its wrapper context is that there might be 0 or many of those things in there, in the case of a Maybe its wrapper context is that it might exist or it might not, in the case of IO its wrapper context is that it's interfacing with the outside world, and once you abstract away the entire idea of context, you can suddenly open up an entire world of reusability. This is a good tutorial, I will probably be linking it to people if they ever make the mistake of asking about monads. [1] I don't need a lecture on the minutia of this, I know that there's a lot more to it in the theory world, I went to graduate school specifically to study functional language verification. I'm keeping it simple.
tel 1y ago
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.
kevinventullo 1y ago
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<X> 2. For any class X, there is a canonical method G: T<T<X>> -> T<X>. 3. For classes X and Y, and any method f: X -> Y, there is a corresponding method “T<f>”: T<X> -> T<Y>. —————- 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.
- 4ad 1y ago
  So you think that a monad which is an object with a simple definition in category theory is better explained in terms of C++? I would agree that most of these articles about monads are bad. Just study the definition, then study what you can do with monads, it's not that hard.
  - kevinventullo 1y ago
    For people who are more familiar with C++ than category theory, yes.
  - recursive 1y ago
    Yes. If you don't already know category theory, learning it is hard. The terms on wikipedia seem to form a dense graph of links. It's hard to get a foothold of comprehension. For people that already know C++, or are at least familiar with this syntax, this is more useful than describing it in haskell syntax or category theory. There seems to be a chicken and egg problem regarding haskell and monads. Learning c++ may be harder or easier than category theory. I'm no sure, as I don't understand either one of them. But this syntax makes more sense to me than something expressed in terms of category theory vocabulary.
kazinator 1y ago
https://www.kylheku.com/cgit/lisp-snippets/tree/monads.lisp https://www.kylheku.com/cgit/lisp-snippets/tree/monads.lisp [Content Warning: Lisp] We define a small OOP framework for monads, plus macros which then can succinctly define different kinds of monads, including generating a comprehension macro for each one.
danieltanfh95 1y ago
The obsession with trying to explain a monad ultimately stems from conflicting explanations and the inability to differentiate between a mathematical monad and monads implemented in software. Monads in software are just a standard API for any given type. That’s it. Theres no magic here. Just implement the standard and you have a monad. It grinds my gears seeing monad tutorial after tutorial using the wrong metaphors or misleading explanations
- lmm 1y ago
  Associativity is important, and not something that can be expressed in the API in most languages.
  - danieltanfh95 1y ago
    Associativity is part of the contract/specifications of said "standard API"
- petesergeant 1y ago
  > Monads in software are just a standard API for any given type. That’s it. Theres no magic here. I don’t think that’s helpful for people to understand _why_ monads though, and that’s generally what people are looking for.
  - danieltanfh95 1y ago
    a standard api is the magic. when you can talk to anything via a standard api it creates uniformity and standard blocks you can build from
agnishom 1y ago
Somebody is keeping a giant list of Monad tutorials, right?
- lordgilman 1y ago
  Yes, and we are approaching peak monad tutorial https://wiki.haskell.org/Monad_tutorials_timeline https://wiki.haskell.org/Monad_tutorials_timeline
  - throwaway290 1y ago
    So in the golden age of the internet we had the highest rate of monad tutorial growth. Churn them out, bring back the good times
theanonymousone 1y ago
I will die with the crushing embarrassment of not being able describe what a monad is, despite being a so-called (and apparently fake) programmer since the age of 10.
- perlgeek 1y ago
  There's nothing embarrassing about not knowing the details of a sub-field you're not deeply involved in. Like, why would you embarrassed about not understanding the details of MPLS networking if you're not a network engineer who works with MPLS?
fud101 1y ago
Ive never understood what a Monad is or why I should care. I still don't care to learn category theory or whatever but I was wondering, if there is a single image/diagram which will convey the idea behind monad? I recently stumbled on such an image which made the concept of simultaneity of SR click and I'm intrigued in other things I could never understand suddenly becoming crystal clear with a single image.
psyleft 1y ago
I still think the best way to conceptualize a monad is a "wrapper" around some data that contains additional state. The critical part of this definition is the second half, which sometimes gets skipped over for simplicity but is really what ties together all the disparate uses of monads. The most convincing description of this idea imo is this video by Tsoding: https://www.youtube.com/watch?v=fCoQb-zqYDI https://www.youtube.com/watch?v=fCoQb-zqYDI

157 points by polygot 1y ago

IDK if it ads anything to the article, but `map` is a property of Functors, and every Monad is a Functor. Well, every Monad is an Applicative Functor, and every applicative functor is a functor. All a way of saying that, yep, you always have `map` when you have a Monad, but you don't need a Monad to have `map`. If you want an example we can compare a regular list and a Ziplist. A regular list's Applicative instance does a cross product, while a Ziplist's applicative instance does a dot product. (*) <$> [2,3] <*> [5,7, 11] --> [10,14,22,15,21,33] getZipList $ fmap show $ (*) <$> ZipList [2,3] <*> ZipList [5,7, 11] --> ["10","21"] There's no great way to write a Monad instance for ZipList. But it's an Applicative Functor and thus is also a Functor and thus you can map over it. https://www.mail-archive.com/haskell-cafe@haskell.org/msg57217.html https://www.mail-archive.com/haskell-cafe@haskell.org/msg572... For quirky reasons in Haskell, `fmap` the function implemented for every Functor instance. This is because `map` was already taken by lists. Weird, I know.

revskill 1y ago

U must prove it is a monoid in the category of endofuncors.

rebeccaskinner 1y ago
join has the type `m (m a) -> m a`. That's the thing that really shows off the monoidal structure. People normally implement monads in terms of bind, but you can easily define join in terms of bind for any Monad: `join ma = ma >>= id`. So really, as long as you have a lawful instance of Monad written with bind the existence of join is your proof.
hirvi74 1y ago
> monoid in the category of endofuncors. I do not even know what a monoid or an endofuncor is. While I enjoy math, despite not being the best at it, I am confident I never made it this far in my studies. I looked at the Wikipedia definitions, and I am even more confused now.
- 1-more 1y ago
  https://bartoszmilewski.com/2016/12/27/monads-categorically/ https://bartoszmilewski.com/2016/12/27/monads-categorically/ This is a book chapter, and you need the preceding chapters to grasp it I think. I'm still in the middle of it.

robinhouston 1y ago

I expect the author has done this knowingly, but the title is rather painful for a mathematician to read. A list is not a monad. List is a monad. A list is an algebra for the List monad.

leoh 1y ago
I appreciate you mentioning this because I think it’s actually an important point
Garlef 1y ago
What you said is not correct! In detail: * "A list is not a monad" - True! * "List is a monad" - True. But I think "`List` is a monad" might be clearer. * "A list is an algebra for the `List` monad." - False! What's correct is the following: * "An algebra for the `List` Monad is precisely a monoid." Sketch of the construction: (an algebra for the list monad is a monoid): Recall that an algebra is a set/type `A` together with a function `mult: List A -> A` together with some axioms. Think of such a function `mult: List A -> A` as the function that assigns to each list with elements in `A` the product over all those elements. The aforementioned axioms boil down to: (1) `mult([])` is a neutral element and (2) `mult` is an associative binary operation when restricted to two-element lists. (a monoid is an algebra for the list monad): Same Idea - Given a monoid, we define a function `mult: List A -> A` by assigning to a list of elements of `A` the product of these elements. And the empty list we assign to the neutral element. Then we can use the associativity and properties of the neutral element to show that this function constitutes an algebra for the list monad.
- robinhouston 1y ago
  You're quite right! Thanks for the correction. I should have said that a list is an element of a free algebra over the List monad, which is less pithy.
polygot 1y ago
Thanks for the feedback! I can definitely rename the post soon as a first step, although this may require rewriting a chunk of the article to more accurately reflect the fact that List is a monad, and not "a" list. I could make this distinction in part 3 (not written yet) although I want to balance not misleading readers, but not overcomplicating it too early on.

brooke2k 1y ago

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 separate lesson for every common monad instance. Start with Maybe, then IO, then maybe State and List, and so on... because ultimately, every instance of a Monad works very differently. That's why the pattern is so useful in the first place, because it applies to so many places. (Note: this is a criticism of monad tutorials in general, not this one in particular, which seems to do a decent job on this front). In my experience, people new to Haskell focus way too much on getting the "a-ha" moment for monads in general, when really you want a bunch of separate "a-ha" moments as you realize how each instance of a monad takes advantage of the pattern differently. I also tend to think that monads are best demonstrated in Haskell rather than in other languages, if only because the notation is so much less clunky. That may just be me though. (EDIT: well, also because almost no other languages have typeclasses, so you have to approximate it with interfaces/traits/etc) Also FYI: in part 2, the code examples have extra newlines in between every line, which makes it hard to read (I'm on firefox, if that matters).

pdhborges 1y ago
If all monad instances work differently what is the value of the Monad interface? What kind of usefull generic code can one write against the Monad interface. Related: https://buttondown.com/j2kun/archive/weak-and-strong-algebraic-structures/ https://buttondown.com/j2kun/archive/weak-and-strong-algebra...
- ChadNauseam 1y ago
  Lots of useful generic code. MapM is a version of `map` that works with any Monad, `sequence` works with any monad, and so on. These are used very frequently. But the bigger benefit is when syntax sugar like `do` notation comes in. Because it works for any Monad, people can write their own Monads and take advantage of the syntax sugar. That leads to an explosion of creativity unavailable to languages who "lock down" their syntax sugar to just what the language designers intended. In other words, what requires a change to other languages can often be a library in Haskell.

daxfohl 1y ago

Nit, in Haskell it's a MonadPlus. Which IIRC is a monad that supports filtering.

ChadNauseam 1y ago
In Haskell List is a Monad as well as MonadPlus. Since List's Monad instance is used probably 100x more than its MonadPlus instance, I think it makes sense to focus on that,

nyeah 1y ago

Let's keep up the mathiness. Look how much economics has benefitted from that.

draw_down 1y ago

[dead]

hackandthink 1y ago

Just for fun, monads as modalities is missing: https://hackage.haskell.org/package/Agda-2.6.4.2/docs/Agda-Syntax-Common.html#t:Cohesion https://hackage.haskell.org/package/Agda-2.6.4.2/docs/Agda-S...

jrjrjrjrjfjj 1y ago

Smaug123 1y ago

The article sort of danced around what I think is the most natural way List is a "recipe": it's the bounded nondeterminism monad (a `List<T>` is a nondeterministic result; one could implement `List<T> -> T` by selecting an answer uniformly at random from the finite multiset).

perlgeek 1y ago
I really like my lists to be deterministic. Seriously, I've read things about lists and nondeterminism a few times in this thread, and I can't help but wonder if "you guys" (functional programming nerds, maybe?) use the word "nondeterministic" different than the rest of the world? If not, I'd love a good explanation about what makes lists non-deterministic, and why we would want that, and why they seem to be perfectly deterministic in imperative programming languages.
- housecarpenter 1y ago
  It is a particular sense of "nondeterminism", but it's not specific to functional programming, I think it's the usual one theoretical CS as a whole. It's the same sense in which "nondeterminism" is used in P vs NP, for example. Think of a computation as a process of changing state. At a given point in time, the computer is in a certain state, the current state. The computation can be described in terms of a function that acts on the current state. In a deterministic computation, the function takes in the current state, and produces a single state as output which will be the state the computer enters on the next tick. In a non-deterministic computation, the function takes in the current state and produces a set of states as output. These states are all the possible states the computer might enter on the next tick. We don't know (or just don't care) which one of these states it will enter. You can model a non-deterministic computation as a deterministic one, by using a list `currentStates` to store the set of all possible current states of the computation. At each "tick", you do `currentStates = flatMap(nextStates, currentStates)` to "progress" the computation. In the end `currentStates` will be the set of all possible end states (and you could do some further processing to choose a specific end state, e.g. at random, if you wish, but you could also just work with the set of end states as a whole). It's in this sense that "a list is a non-deterministic result", although this is really just one thing a list can represent; a list is a generic data structure which can represent all sorts of things, one of which is a non-deterministic result.

mikelitoris 1y ago

A list is like a burrito

zahlman 1y ago
It's just a loust in the category of endosequences.
- accoil 1y ago
  I think that was the article that made me actually try to understand "A monad is just a monoid in the category of endofunctors". Researching "endofunctor" helped significantly more than any of the analogies floating around at the time.

gr4vityWall 1y ago

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/Reference/Global_Objects/Array/flatMap 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.

aadhavans 1y ago
Could you elaborate on that? What does 'flatMappable' mean in this context?
- IshKebab 1y ago
  This is a good explanation: https://users.scala-lang.org/t/what-is-a-monad-in-scala/4169 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.
  - skybrian 1y ago
    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.
    - still_grokking 1y ago
      Scala's new effect library Kyo just uses `map`. See: https://getkyo.io/#/?id=the-quotpendingquot-type-lt https://getkyo.io/#/?id=the-quotpendingquot-type-lt All pure values are automatically lifted into the Kyo monad, so `map` is effectively `flatMap`. From the linked docs: > This unique property removes the need to juggle between map and flatMap. All values are automatically promoted to a Kyo computation with zero pending effects, enabling you to focus on your application logic rather than the intricacies of effect handling. In the end it makes a lot of sense I think. What you do is manipulating values inside some wrapper. Whether this wrapper is a monad or not should not matter. Just do something with the value(s) inside, and that's mapping.

nemo1618 1y ago

I think this adds more confusion than it removes. A list is not a monad. A list is a data structure; a monad is more like a "trait" or "interface." So you can define a List type that "implements" the monad interface, but this is not an inherent property of lists themselves. That's the sense in which a list "is a" monad: the OOP sense. Haskell's List monad provides a model for nondeterminism. But that certainly isn't the only way List could satisfy the monad interface! It was a deliberate choice -- a good choice, possibly the best choice, but a choice nonetheless.

blakehawkins 1y ago
Can you explain the nondeterminism part of your comment more?
- ryandv 1y ago
  Determinism, in that given some set of inputs you only ever receive one output. Non-determinism, in that given some set of inputs it's possible to receive a collection (a list) of possible outputs. With lists you can express things like all possible pairings of all possible outcomes, or the Cartesian product: ghci> liftM2 (,) ['a', 'b', 'c'] [1,2,3] [('a',1),('a',2),('a',3),('b',1),('b',2),('b',3),('c',1),('c',2),('c',3)] ... or in more explicit monadic do-notation: ghci> :{ ghci| do ghci| x <- ['a', 'b', 'c'] ghci| y <- [1,2,3] ghci| return (x, y) ghci| :} [('a',1),('a',2),('a',3),('b',1),('b',2),('b',3),('c',1),('c',2),('c',3)] and so on.
- pkal 1y ago
  From automata theory, you might know that nondeterministic automata are represented by a set of states. Deterministic automata are always in a specific state, while nondeterministic ones are in multiple at once. Lists are used for non-determinism in Haskell the same way as a set, mainly because they are easier to implement. But the total order that a list induces over a set is not that relevant.
  - ryandv 1y ago
    That's right, and you see this directly reflected in the "types" of the transition functions for DFAs and NFAs, respectively [0] [1]: δ : Q × E ⟶ Q δ : Q × E ⟶ P(Q) ... where Q denotes the set of the automaton's states, E its alphabet of input symbols, and P the power set operation. Deterministic automata arrive at a definite, single state drawn from Q, while non-deterministic automata may arrive at a set (~list) of possible states, when given a current state from Q and next input symbol from E. [0] https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministic_finite_automaton [1] https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa...

FeelingsSparked 1y ago

[dead]

skybrian 1y ago

I like to think of a monad as a design pattern for constructing new objects where you pass in a sequence of callback functions, one at a time. A monad’s ‘bind’ operation adds another callback function to the end of a sequence. The monad interface only requires ways to construct object using callbacks. The ‘bind’ operation takes a callback as an argument, but says nothing about when it’s actually called; it could be immediately, deferred, multiple times, or even never. It’s up to the implementation of the monad, as well as the language, if it’s a lazy language. This is basically a framework. Like with other frameworks, the principle is “don’t call us; we’ll call you.” Arbitrary computation can happen between callbacks. The framework can do whatever control flow it wants, and this is what often makes frameworks opaque. Hiding control flow is what frameworks do, for better or worse. So far, none of this is specific to a Monad. The Monad part comes from the type signature of the callback function passed in to flatmap(), which allows ‘bind’ operations to be nested. Once you know what kind of thing you’re dealing with (frameworks) then you can go into why some frameworks qualify as a monad.

kelseyfrog 1y ago

While I can understand the desire to draw a metaphor, there are better approaches than saying, "A List Is a Monad". The statement as-is breaks pretty much immediately because, while there is a canonical list monad, there isn't a list monad, there are in fact several[1]. There are several more correct ways of phrasing the idea among: "List can be given a monad instance" "List forms a monad with pure and bind as defined" "List is the underlying functor of a monad" The point is that picking any old list implementation is likely not a monad without the supporting structure. Will any of these help you learn what a monad is? Likely not. Monadology is a Mary's Room[2] problem; there is a qualia, a subjective sensation, when one understands monads having experienced them first hand. Subsequently monad tutorials are the best case against physicalism[3] yet devised. 1. https://hackage.haskell.org/package/exotic-list-monads-1.1.0/docs/Control-Monad-List-Exotic.html https://hackage.haskell.org/package/exotic-list-monads-1.1.0... 2. https://en.wikipedia.org/wiki/Knowledge_argument https://en.wikipedia.org/wiki/Knowledge_argument 3. https://en.wikipedia.org/wiki/Physicalism https://en.wikipedia.org/wiki/Physicalism

zzo38computer 1y ago
Although there can be other monads (and stuff other than monads, such as ZipList) that can be made with lists, I think that such a monad would not necessarily be a "list monad". (Your link [1] has several examples of this.) You are right that it does not mean that "a list is a monad" and that your other phrasing is better, but it does not mean that "there isn't a list monad".
- kelseyfrog 1y ago
  To me "a list monad" often subtly implies "one" list monad. I wasn't very clear, but the point I was trying to make was more along the line of singular vs plural. Thanks for pointing out the discrepancy.

drumnerd 1y ago

A monad is not a container! It’s a way of composing functions if they have an effect. You tell how to inject a value in that effect (unit) and how to compose two functions that have that effect and that’s it: programmable semicolons.

mrkeen 1y ago
And in the article's case, 'have an effect' means 'be a list'.
polygot 1y ago
Thanks for the feedback, I totally agree that monads are not containers. From an OOP perspective, they have some properties that make them, in some sense, sorta like containers, e.g., they contain a value like the Maybe monad. I still agree that they are not simply containers. I can clarify this in a revision to part 1 soon.
- lmm 1y ago
  > From an OOP perspective, they have some properties that make them, in some sense, sorta like containers, e.g., they contain a value like the Maybe monad. Not always! I find this is a big source of confusion; not all monads contain values, sometimes beginners think they can or should "get the value out" of a monad and that tends to lead to writing the wrong kind of code.

ivanjermakov 1y ago

Misunderstanding of Monads is such an interesting phenomenon. Kind of similar to grasping 4D geometry or understanding the difference between a class and an object in OOP. List can be an instance of a monad, i.e. a monadic type. I think the trick to understanding monads is to see what benefits monad interface gives to the types that implement it.

kerblang 1y ago

The way I think of it, monads are a solution to Callback Hell, where you've fallen in love with lambdas, but now you have a nightmarish mess of lambdas in lambdas and lambdas calling lambdas. The monadic functions allow you to create "for comprehensions" aka "do comprehensions" but really, they look like a classic for-each loop. They secretly call the monadic map/flatMap/filter functions. for x in list doThings(x) These comprehensions have a strange bonus feature, that you can do nested "loops" all at once, and even add "guards" (little if statements) newlist= for x in list1 y in list2 if y > 3 z in list3 doThings(x, y, z) But again, the comprehension, when "de-sugared", is secretly calling the map/flatMap/filter functions of list1, list2, list3 to get our result. You as the author of a given monad can implement those functions however you want, and they're all 3 lambda based. But notice how the comprehension is flattening those lambdas out! Our callbacks in callbacks are much more readable like this. Without comprehensions, you can still implement monadic functions in any old language (probably in C...?), and they're handy in their own right, but you don't get the flattening-of-callback-hell magic.

stronglikedan 1y ago
After reading your comment, I've made it my mission to understand it. Although I have no idea what you're talking about, you make it sound intriguing.
- teiferer 1y ago
  [dead]
- kerblang 1y ago
  First off, I'm not sure it's even worth it to understand this stuff... Second, someone should be along to slam it soon enough and insist I've missed some gibberishy business that you'll never understand. With those caveats in mind, here's a more intensive scala-based monad tutorial I made: https://github.com/zaboople/techknow/blob/master/scala/monad/MonadTutorial.scala https://github.com/zaboople/techknow/blob/master/scala/monad... But really, don't burn up too much of your short life trying to come to terms with this stuff. There's a reason most languages don't get around to supporting Monads...

mvdtnz 1y ago

The amount of people who tie themselves into knots to understand this pointless concept is very funny to me. I am 16 years into a successful software engineering career without learning what a monad is an it never held me back. Turns out I can use lists and optional types and all that jazz without it. I mean really. Look at posts like this[0]. What does this give you? Nothing, in practical reality. Nothing. [0] https://news.ycombinator.com/item?id=44446472 https://news.ycombinator.com/item?id=44446472

battle-racket 1y ago
funny that you call it pointless then admit you never learned what it is
lmm 1y ago
> I am 16 years into a successful software engineering career without learning what a monad is an it never held me back. How would you know? That's the classic Blub Paradox. Being able to write a custom monad and then leverage the vast array of libraries that already exist has helped me deliver functionality to end users quicker, more maintainably, and with lower defect rates. They don't let you do anything that you couldn't do by writing it out longhand. But just like using generic container libraries instead of writing a specific container for every type you want to handle collections of, they're extremely helpful.

t43562 1y ago

Another tutorial which makes monads about 100x more impossible to understand for me by relating them to something else and describing all the weird ways that they are NOT that thing. IMO if you already have it, this will be a lovely comparison full of insight, but if you haven't then it's full of confusing statements. IMO what they are is utterly unimportant, except to mathematicians, and what you can do with them is more to the point. The fact that explanations are so often in Haskell just makes them more unintelligible because you really need to know what problem they solve.

polygot 1y ago
Thanks for the feedback! I'll likely be editing part 1 to include the feedback so far from the commenters as well. If there's a specific statement or analogy that felt especially confusing, please point it out and I'll clarify it in the post.
- t43562 1y ago
  Sorry for moaning - it's just the usual despair that I feel every time I read a new explanation and fail to understand it. This isn't your fault.
empath75 1y ago
The reason that the explanations are all in Haskell is that Haskell is the only language that is reasonably popular that implements monad and calls it a monad, and 90% of the people looking up "What is a monad" are trying to learn Haskell.
- t43562 1y ago
  Yes, you're doing 2 difficult things at the same time - a new language and a new concept. IMO it would be great to just have the concept to deal with.

benreesman 1y ago

In most programming languages the compiler authors go to great lengths to gives intuitive semantics to having one statement follow another, followed by another. This is an organizing principle for thinking about code and for having a program exist with well-defined semantics. But its not a very robust one: its never true of fast programs on realistic hardware for example (not for a long time now). And all the rule bending (-fstrict-alias, bunch of stuff) exists in this tension between the grade school natural language paradigm and the reality of computers. I say grade school not to be pejorative, but rather because it is roughly the boundary where written natural languages begin to have interesting tensions around past and future and simultaneous, changing and not changing. Functors and applicatives and monads and other type classes like these are the source of endless analogies because there isn't an accepted, broadly-understood terminology for this "well its roughly what would happen if you had a piece of paper and wrote things on it at every statement boundary and scratched off the old ones" (though Turing and von Neumann did formalize this in useful ways, they just don't generalize well to realistic computers anymore). Monads are the mathematical object that is forced on you if you want a rigorous way to describe the semantics of program execution in the vicinity of this "common sense" notion. That's really what everyone is dancing around: your program is only well defined with either: - a big rulebook full of exceptions and edge cases - a compositional rule strict enough to give some useful predictability but lax enough to admit most useful programs. It is this rigor/laxity tension as concerns text on a page and gates on a semiconductor that gives monads a privileged place in the towers of categories. When I worked on Sigma we were among the earlier adoptors of ApplicativeDo, for example, because we wanted a slightly different rigor/laxity tradeoff for performance reasons. Monads are what happens when you do shift the giant pile of "back of the book" compiler details that describe program execution semantics into a much simpler set of rules, but at the cost of increasing the barrier to entry because you need to know the rules before you can print "hello world".

acjohnson55 1y ago

I used to struggle with understanding the "receipe" metaphor for monads when it comes to lists. But a list (or, really any collection) as a monad can be thought of as the "discrete nondeterminism monad". Meaning that every collection is a set of possible inputs to the computation that is provided as the argument to a `flatMap` operation. Each `flatMap`, by definition, returns a new collection of possible outputs for each of the inputs, and each of those collections gets concatenated. Every item in the final output collection represents the result of following some path through the computations, selecting a single item at each step. Importantly, the type of the output of each `flatMap` operation can differ from the input. You can imagine extending this by assigning probabilities, or making the domain continuous (I think...). These extensions would still be monads, just without being simple collections. It's kind of like how multiplication over whole numbers is repeated addition, but that metaphor becomes less useful for other domains of numbers.

tombert 1y ago

Realizing that lists are monads is what made monads "click" for me. When I was first learning Haskell a million years ago, I was completely confused by the concept of a monad; I could, after enough fighting with the compiler, usually get something working, but it was a stochastic guess-and-check process trying to figure out what `IO` actually means. Even the `Maybe` was confusing to me, because I couldn't really figure out how the hell you relate something like "checking for null" with "writing to the disk". I can't remember where I saw it, probably on the Haskell wiki somewhere, but when they pointed out the List is a monad, and after seeing an example of how it worked, I suddenly got it: in a hand-wavey way, a monad is basically just a value with a wrapper context [1], and from a practical perspective that's all it is. In the case of a List its wrapper context is that there might be 0 or many of those things in there, in the case of a Maybe its wrapper context is that it might exist or it might not, in the case of IO its wrapper context is that it's interfacing with the outside world, and once you abstract away the entire idea of context, you can suddenly open up an entire world of reusability. This is a good tutorial, I will probably be linking it to people if they ever make the mistake of asking about monads. [1] I don't need a lecture on the minutia of this, I know that there's a lot more to it in the theory world, I went to graduate school specifically to study functional language verification. I'm keeping it simple.

tel 1y ago

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.

kevinventullo 1y ago

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<X> 2. For any class X, there is a canonical method G: T<T<X>> -> T<X>. 3. For classes X and Y, and any method f: X -> Y, there is a corresponding method “T<f>”: T<X> -> T<Y>. —————- 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.

4ad 1y ago
So you think that a monad which is an object with a simple definition in category theory is better explained in terms of C++? I would agree that most of these articles about monads are bad. Just study the definition, then study what you can do with monads, it's not that hard.
- kevinventullo 1y ago
  For people who are more familiar with C++ than category theory, yes.
- recursive 1y ago
  Yes. If you don't already know category theory, learning it is hard. The terms on wikipedia seem to form a dense graph of links. It's hard to get a foothold of comprehension. For people that already know C++, or are at least familiar with this syntax, this is more useful than describing it in haskell syntax or category theory. There seems to be a chicken and egg problem regarding haskell and monads. Learning c++ may be harder or easier than category theory. I'm no sure, as I don't understand either one of them. But this syntax makes more sense to me than something expressed in terms of category theory vocabulary.

kazinator 1y ago

https://www.kylheku.com/cgit/lisp-snippets/tree/monads.lisp https://www.kylheku.com/cgit/lisp-snippets/tree/monads.lisp [Content Warning: Lisp] We define a small OOP framework for monads, plus macros which then can succinctly define different kinds of monads, including generating a comprehension macro for each one.

danieltanfh95 1y ago

The obsession with trying to explain a monad ultimately stems from conflicting explanations and the inability to differentiate between a mathematical monad and monads implemented in software. Monads in software are just a standard API for any given type. That’s it. Theres no magic here. Just implement the standard and you have a monad. It grinds my gears seeing monad tutorial after tutorial using the wrong metaphors or misleading explanations

lmm 1y ago
Associativity is important, and not something that can be expressed in the API in most languages.
- danieltanfh95 1y ago
  Associativity is part of the contract/specifications of said "standard API"
petesergeant 1y ago
> Monads in software are just a standard API for any given type. That’s it. Theres no magic here. I don’t think that’s helpful for people to understand _why_ monads though, and that’s generally what people are looking for.
- danieltanfh95 1y ago
  a standard api is the magic. when you can talk to anything via a standard api it creates uniformity and standard blocks you can build from

agnishom 1y ago

Somebody is keeping a giant list of Monad tutorials, right?

lordgilman 1y ago
Yes, and we are approaching peak monad tutorial https://wiki.haskell.org/Monad_tutorials_timeline https://wiki.haskell.org/Monad_tutorials_timeline
- throwaway290 1y ago
  So in the golden age of the internet we had the highest rate of monad tutorial growth. Churn them out, bring back the good times

theanonymousone 1y ago

I will die with the crushing embarrassment of not being able describe what a monad is, despite being a so-called (and apparently fake) programmer since the age of 10.

perlgeek 1y ago
There's nothing embarrassing about not knowing the details of a sub-field you're not deeply involved in. Like, why would you embarrassed about not understanding the details of MPLS networking if you're not a network engineer who works with MPLS?

fud101 1y ago

Ive never understood what a Monad is or why I should care. I still don't care to learn category theory or whatever but I was wondering, if there is a single image/diagram which will convey the idea behind monad? I recently stumbled on such an image which made the concept of simultaneity of SR click and I'm intrigued in other things I could never understand suddenly becoming crystal clear with a single image.

psyleft 1y ago

I still think the best way to conceptualize a monad is a "wrapper" around some data that contains additional state. The critical part of this definition is the second half, which sometimes gets skipped over for simplicity but is really what ties together all the disparate uses of monads. The most convincing description of this idea imo is this video by Tsoding: https://www.youtube.com/watch?v=fCoQb-zqYDI https://www.youtube.com/watch?v=fCoQb-zqYDI