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

List is a monad

alexyorke.github.io

Post reply on HN
Print view View original

161–170 of 187 posts

Re: List is a monad

#161

Post by housecarpenter »

perlgeek wrote: post #156
Smaug123 wrote: post #19

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 ` is a nondeterministic result; one could implement `List -> T` by selecting an answer uniformly at random from the finite multiset).

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

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.

Re: List is a monad

#162

Post by feelamee »

gpderetta wrote: post #160
kevinventullo wrote: post #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 . ———…

A monad would not be a template class in C++, it would a concept (more or less the c++ equivalent of an Haskell type class).

monad like an idea - yes, it will be a concept. But a concrete monad - like list or maybe - will be a template class. Probably comment author means this

Re: List is a monad

#163

Post by immibis »

bjourne wrote: post #38
ChadNauseam wrote: post #16

Earlier quoted context omitted.

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

What can a Haskell monad do that a Python class cannot? 99% of all monads I've seen only facilitate local state manipulation.

Haskell monads have been described as "programmable semicolons" because they specify ways to interpret "do" blocks.

In some sense they are a little bit similar to Python classes. A Python class is a block of code, which runs in a normal Python way, and then the variables put in scope by that code are passed to a metaclass constructor which creates some kind of object based on them. Monads are nothing like that, but they are similar in that user code is interleaved with framework code to produce an effect similar to a DSL. Monads run one statement at a time, interleaving one statement execution with one monad join operation.

Re: List is a monad

#164

Post by feelamee »

Kranar wrote: post #145
kevinventullo wrote: post #117

Earlier quoted context omitted.

I mean if someone is learning chess for the first time, then yes you should start with the rules rather than jumping right into waxing philosophic about positional strategy to show off how smart you are.

Yeah I am aware that most teachers, like another commenter said, do teach math just by spitting out the rules and then people memorize them and sure who am I to argue against that. It's not how I learned math and most people I know who are well versed in math including those with PhDs (and working as a quant I am fortunate enough to work with many) also don't really learn things that way either... When I taught my da…

it's great you should write an article about this!

Re: List is a monad

#165

Post by 4ad »

recursive wrote: post #143
4ad wrote: post #111

Earlier quoted context omitted.

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.

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…

Learning category theory to the level of understanding monads should take half an hour at most, and would constitute real understanding of what a monad is, versus this C++ explanation which is handwavy even in terms of C++. C++ can't even encode monads accurately!

But one doesn't even need to learn category theory. I assume that everybody has learned abstract algebra in high school, monoid, rings, groups, vector spaces and all that. A monad is just another kind of a structure like that. If you have studied abstract algebra in school then it should take 5 seconds to read the definition of a monad, a minute to understand it, and perhaps 10 minutes to see how various things such as errors or lists form monads.

Learning category theory, or indeed any sort of math from Wikipedia is an absolute futile endeavour.

Re: List is a monad

#166

Post by gpderetta »

feelamee wrote: post #162
gpderetta wrote: post #160

Earlier quoted context omitted.

A monad would not be a template class in C++, it would a concept (more or less the c++ equivalent of an Haskell type class).

monad like an idea - yes, it will be a concept. But a concrete monad - like list or maybe - will be a template class. Probably comment author means this

Good point. In the same way we say that a pointer is an iterator or a vector is a container, when more precisely we should say that they model the iterator concept and container concept respectively.

Re: List is a monad

#167

Post by fud101 »

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.

Re: List is a monad

#168

Post by kerblang »

lmm wrote: post #128
stronglikedan wrote: post #58

Earlier quoted context omitted.

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.

You might like https://philipnilsson.github.io/Badness10k/escaping-hell-wit... which is a longer version of the same kind of argument.

As original commenter I'll vouch for this one! It does give a much better & more detailed explanation of what I'm hinting at without math gibberish and whatnot.

Re: List is a monad

#169

Post by empath75 »

t43562 wrote: post #81

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…

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.

Re: List is a monad

#170

Post by housecarpenter »

4ad wrote: post #165
recursive wrote: post #143

Earlier quoted context omitted.

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…

Learning category theory to the level of understanding monads should take half an hour at most, and would constitute real understanding of what a monad is, versus this C++ explanation which is handwavy even in terms of C++. C++ can't even encode monads accurately! But one doesn't even need to learn category theory. I assume that everybody has learned abstract algebra in high school, monoid, rings, groups, vector spac…

At least in my country (the UK), people generally do not learn abstract algebra in high school. That's a university-level topic.

I think there is a definite "step up" in complexity between the structures of abstract algebra such as monoids, rings, groups and vector spaces, and monads. All of those algebraic structures are basically just sets equipped with operations satisfying some equations. Monads are endofunctors equipped with natural transformations satisfying some equations. "Endofunctor" and "natural transformation" are considerably more advanced and abstract concepts than "set" and "operation", and they are concepts that belong to category theory (so I don't see how you can read and understand the definition of a monad without that basic level of category theory).

Your time estimates also seem wildly optimistic. A common rule of thumb is that reading a maths textbook at your level takes around an hour per page. I think the definition of a monad can be compared to one page of a textbook. So I'd say it'll take on the order of hours to read and understand the definition of a monad, and that's assuming you're already entirely comfortable with the pre-requisite concepts (natural transformations, etc.)

Post reply on HN