Talk:Monad (functional programming)

The meaning of the pseudo-code needs to be clarified:

(f >=> g) x = (f(x) → mb) >>= g(y = b)

1: My personal reading is that this is an equation. The left hand side is (f >=> g) x

2: The right hand side is

Let functor (f(x) → mb) be the functor resulting from substituting mb for y in g;

3: The (y=b) on the right hand side is not an equation; but g(y=b) is an application of g to the type y where b

4: The f → mb is a functor from type x to monadic value mb where b

The Kleisli compose operator >=> means if some m >>= f then f is the continuation of m.^[1] -- Ancheta Wis   (talk | contribs) 18:59, 27 October 2022 (UTC), 01:42, 28 October 2022 (UTC)

Alexis King^[2] notes that if m >>= f >>= g >>= h then the continuation of m is f >=> g >=> h ^[3] --Ancheta Wis   (talk | contribs) 19:18, 27 October 2022 (UTC)

The notation doesn't make much sense and seems to have been introduced quite randomly and without references in https://en.wikipedia.org/w/index.php?title=Monad_(functional_programming)&diff=next&oldid=867467071 , along with a few other strange changes by user:Zar2gar1 in the vicinity. To me, user:Nbrader's edit is a correction. --Daniel5Ko (talk) 23:27, 28 October 2022 (UTC)

So which is it,

(f >=> g) x = (f x) >>= g

or some other parenthesization needed?

(f >=> g) x = f x >>= g

ping user:Zar2gar1 --Ancheta Wis   (talk | contribs) 00:14, 29 October 2022 (UTC)

@user:Zar2gar1, Thank you for your pseudocode in the article, which attempts to accomodate the requests of the readership to avoid Haskell. Because of the objections above, I propose the use of Bartosz Milewski's 2019 book Category Theory for Programmers pages 202 through 205, which uses Haskell notation to explain Kleisli composition >=> . Dr. Milewski uses Kleisli composition >=> and return to implement Monad. In fact Dr. Milewski implements Monad in Haskell three ways on those pages. --Ancheta Wis   (talk | contribs) 01:08, 29 October 2022 (UTC)

@"which is it": The two alternatives have the same meaning. Even more: They already have identical parse trees. --Daniel5Ko (talk) 00:40, 30 October 2022 (UTC)

Firstly, sorry for replacing the pseudo-code with Haskell code without reading the talk page first: I didn't realize there was an effort to avoid Haskell code. I will say though I found the pseudo-code confusing. My feeling (for what it's worth) is that psuedo-code that has no clear meaning to most people defeats the point of pseudo-code and you're better off going with an actual language like Haskell. Nbrader (talk) 01:21, 30 October 2022 (UTC)

The equation "(f >=> g) x = (f(x) → mb) >>= g(y = b)" is very confusing, it's unclear where mb and y are bound; I have never seen anything similar. The explanation in this thread is also misguided: x is not a type and there is no substitution happening that forms functors.

It makes sense to avoid Haskell-specific notation, but here the only notation used is function application written as "f x", and binary operator "f >=> g". I restored the equation, using f(x) as function application. That should be understandable without additional prerequisites. 2001:861:3F42:1B60:AEFC:B99:1842:A29E (talk) — Preceding undated comment added 07:57, 24 November 2022 (UTC)

Hi everyone, I'm still going to be away from Wikipedia for the foreseeable future, but I did get the ping for this conversation. I'm going to try to keep my response simple. For the specific expression about monadic composition, just like you guessed @Ancheta Wis, the "g(y=b)" expression is a kludge to show variable binding and application in the few cases leaving them implicit is ambiguous. It's not the cleanest way for sure, but it does allow avoiding lambda calculus as a pre-req to understand the article.

Big picture, anyone that wants to think through & change the code has my full support. I left a lot of comments and notes in the Talk archives while finishing up my changes though. My main opinions are pretty much:

• Avoid making mostly independent concepts like lambda calculus or currying pre-reqs to understand the article
• Try to be consistent and head-off misinterpretations around things like order of evaluation
• The "right thing to do" would probably be to hash out functional pseudo-code guidelines for Wikipedia at large
• Barring that, I do feel math-ish notation is preferable, followed by something like an established functional language (just looser & more accessible)

I don't expect people to read my notes (they're long), but if you are willing to, you may still want to factor in my rationale at some points. Zar2gar1 (talk) 05:49, 28 November 2022 (UTC)

Talk for BRD -- Ancheta Wis   (talk | contribs) 02:03, 7 November 2023 (UTC)

It was added at https://en.wikipedia.org/w/index.php?diff=438062307 that the monoid being "non-commutative and idempotent" implies permutation. I think the property as described cannot mean "free and idempotent", as [a, b, a] wouldn't be called a permutation. Is there a way to clarify the property to really give permutations? Otherwise, is it even meaningful to name the collection type arising from free and idempotent monoid? Junghyeon Park (talk) 04:27, 11 December 2023 (UTC)

@J824h: Sorry it's almost a year later, but that was a really good catch. I reorganized that section into the table a few years back but didn't bother to think through the content enough.

If you have idempotence but no commutativity to allow reduction, then I'd guess you have the most free regular language with no immediate repetitions over a given alphabet (of size N). Which itself is isomorphic to the maximal, loop-free, digraph with N vertices (interpreted as a finite state machine over the alphabet)? Anyways, even if that's interesting, it doesn't strike me as particularly noteworthy or relevant to the article.

I feel like the ability to generate permutations from a monoid is noteworthy though so I corrected the line. To distinguish from the free monoid, it explicitly says "partial permutation" now. And maybe it's a bit of hand-waving, but now it just describes the monoid as "non-commutative without repetition". Does that sound good? -- Zar2gar1 (talk) 17:37, 21 November 2024 (UTC)

@Zar2gar1 That constraint on List should suffice to give "permutations". I wouldn't even call them "partial", as in the other rows not explicitly alluding to the relation to the underlying set or basis (like saying "subsets" for sets). I guess a permutation here should have implied an arrangement, not a mapping.

Coming back to this, I wonder whether permutations have well-defined associative join from the first place. How do I define [a] ++ [b] ++ [a]? I might be missing something. Junghyeon Park (talk) 14:37, 27 November 2024 (UTC)

Right, I think what makes it tricky to describe these container monads is also why they're interesting. A monoid is typically described in algebraic or formal language terms, but when you apply the monad structure, you get these containers that feel more combinatoric.

I could be wrong, but my gut feeling is the original editor intended the idea of "without replacement" by listing "permutations". Definitely double-check me, but viewed as selections, ordered selections with replacement would yield a full permutation (which is effectively the free monoid), unordered selections with replacement would yield multisets, and unordered selections without replacement would yield sets?

The obvious 4th piece would be ordered selections without replacement, which I guess would technically be partial permutations? The symmetry is really easy to see combinatorically, but our current table lists the property of the monoid, which isn't nearly as elegant.

Per your specific question about a well-defined join, if I'm thinking through this right, both full and partial permutations would have a well-defined join on their respective domains. In a full permutation, there's no restriction on the domain so the join yields [a,b,a] without any issues. For a partial permutation though, listing 'a' twice is prohibited at the monoid level so in your example, the ++ would yield a type error at the 2nd 'a' prior to any join. As long as nothing is repeated though, there's no reason the naive join wouldn't work just like with the full permutation / free monoid. -- Zar2gar1 (talk) 19:11, 28 November 2024 (UTC)

[a, b] + [a] does need to be defined as long as both [a, b] and [a] are in the monad. To get permutations, we need a relation that identifies [a, b, a] to either [a, b] or [b, a], that is, a choice of left- or right-bias for each element. We don't have a unique but multiple valid concrete structures, which seems kind of unfortunate. Otherwise, we might simply accept [a, b, a] = error as a monadic value, which would be without a surjective homomorphism to sets and fit worse in the table. Do I make sense?

Regarding the whole table, I would see this table as a commutative diagram of "list → multiset → set", "list → permutation → set". The combinatoric interpretation is interesting. For the permutations, choosing universal left-bias might correspond to enforcing causality (the items selected earlier is removed from the pool and forbidden).

I don't think full permutation allowing duplicates is a standard terminology. Also, I stand by just permutation instead of partial permutation, as there is nothing to disambiguate in the context, and being partial can mean many things! Junghyeon Park (talk) 15:18, 29 November 2024 (UTC)

Ahhh, you're right, I totally forgot about the closure there. I also think you're exactly right about biasing the operator so that it's well-defined.

Because the join is a natural transformation, that would probably still remain naive, and the + would need to implement the bias. I would think either direction could work though; the append would just need to directly compare the items, then drop duplicates from either the left or the right. And like you said, you could interpret the left-bias causally like selection without replacement (and the right-bias is... anti-causal?)

That said, I also think you're right that we're getting into the weeds about the permutation bit. There's actually not even a citation either so while I think technical articles (especially hard topics) need some flexibility to work out the math / logic oneself, we're probably veering into WP:SYNTHESIS at this point.

So I just cut any mention of the permutations from the table for now. I also consolidated the table layout a bit, but noted the combinatoric properties (so the potential symmetry I mentioned is still implied). If you think it needs more work though or that it should be cut, you should probably go for it. This article definitely needs more attention to the technical details. -- Zar2gar1 (talk) 17:26, 3 December 2024 (UTC)

Leaving only the relatively obvious varieties makes sense. About the additional columns, I personally see them redundant but having both perhaps helps readers less familiar with algebraic terms. We should defer a potential improvement on this part to a separate discussion. Thanks for the discussion! Junghyeon Park (talk) 16:09, 4 December 2024 (UTC)

You're right, the new columns are redundant for anyone that knows the mathematical definitions or can understand the linked articles. But that can be a good thing for new readers.

Thank you too for talking through it with me; it was kind of fun. Maybe I should get over my bad feelings from university and go back to grad school someday. -- Zar2gar1 (talk) 02:39, 5 December 2024 (UTC)

Hi all. I would like to ask regarding the Rust example. It is written in Monad (functional programming)#An example: Maybe that the Rust example is using Maybe, Just, and Nothing, while Rust actually uses Option, Some, and None respectively . Is this intended to be written this way? Mangkoran (talk) 11:19, 19 December 2023 (UTC)

It is not claiming to be in std namespace. While it is probably influenced by the crate https://crates.io/crates/rsmonad, I'm not sure if it's worth mentioning since the API seems pretty generic. Would some clarification help maybe? Junghyeon Park (talk) 07:36, 19 January 2024 (UTC)

This article reads as an informal guide for programmers, contrary to WP:NOTAGUIDE. Almost half of all sources are Internet postings, conference talks, and Haskell wiki pages and many, not limited to these types, are strongly opinionated or tutorial; following these, the text comes across as WP:OR outside a few more encyclopedic sections like History. Normative statements about usage should be contextualized as proper to the norms of functional programming, where they can be supported as such, and otherwise avoided as editorial. Lengthy segments are motivated by only appeals to naturalness, enumerations of supposed advantages, or assertions about what 'many programmers prefer', if at all, and sourced only to guides and documentation, if at all. In my view, major cuts and rewrites are required. Looking at how the subject is handled in other languages, I can recommend the German article as being a fraction of the length and proceeding from definitions to context to a focused set of examples. Terminator 2 really happened (talk) 22:06, 8 August 2024 (UTC)

@Terminator 2 really happened: I worked on this article a while back, and while I don't really plan to much more, I mostly agree with you. I think the one thing that keeps me checking back in is that I never redid the Continuation monad section. And it bugs me for some reason (call/cc is honestly still a riddle I haven't entirely wrapped my head around).

If you're ready to prune the article, especially to harmonize with another wiki, I say go for it. My only two thoughts :

• I think the monad concept itself is difficult enough that it warrants some motivation and exposition. In other words, maybe WP:NOTAGUIDE should be done with a chisel instead of a sledgehammer on this one. I know my edits were still too conversational in retrospect, but for example, it might still be helpful if sections are allowed to build on each other.
• Referring to the Haskell wiki pages is definitely less than ideal, but the talk page already saw a lot of back-and-forth on moving away from Haskell more. I think the core issue is that while we can do examples in other languages, we don't have a better idiom than Haskell-ish terms and pseudocode for explaining the actual concepts. A lot of the historical record out there on using monads is based in Haskell too. Even if it's still Haskell-centric, another harder reference (like a book) might be a good first step. At least that gets us away from citing Haskell's community wiki.

Like I said, I can't dedicate much time to this article going forward, but if you think I can help somehow, feel free to ping me. -- Zar2gar1 (talk) 18:05, 21 November 2024 (UTC)

The first paragraph refers to two operations: "return : <A>(a : A) -> M(A)" and "bind : <A,B>(m_a : M(A), f : A -> M(B)) -> M(B)". The notation is not explained nor is there a link to a resource to understand them. There is a slight attempt to explain them with "which lifts a value into the monadic context" and "which chains monadic computations", but in introducing the idea of monads — which I'm still trying to understand — such things only serve to confuse. For example, what's a monadic context and why must a value be lifted into that context?

That same paragraph purports to provide a simpler explanation via, "In simpler terms, monads can be thought of as interfaces implemented on type constructors, that allow for functions to abstract over various type constructor variants that implement monad." However, I have no idea what a type constructor is, how functions can abstract over various type constructor variants, or what it means for such type constructors to "implement monad", so how does any of that jargon help me figure out what a monad is? 141.162.102.57 (talk) 16:56, 5 February 2025 (UTC)