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

41–50 of 187 posts

Re: List is a monad

#41

Post by pkal »

blakehawkins wrote: post #33
nemo1618 wrote: post #31

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…

Can you explain the nondeterminism part of your comment more?

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.

Re: List is a monad

#42

Post by wk_end »

blakehawkins wrote: post #33
nemo1618 wrote: post #31

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…

Can you explain the nondeterminism part of your comment more?

When you bind with (the Haskell definition for) the List monad - `someList >>= \someElement -> ...` it's like you're saying "this is a forking point - run the rest of the computation for each of the possible values of someElement as taken from someList". And because Haskell is lazy, it's (pardon the informality here) not necessarily just going to pick the first option and then glom onto it if it, say, were to cause an infinite loop if the computation were eagerly evaluated; it'll give you all the possibilities, and as long as you're careful not to force ones that shouldn't be forced, you won't run into any problems. Nondeterminism!

A nice demonstration of this is writing a very simple regex matcher with the List monad. A naive implementation in Haskell with the List monad Just Works, because it's effectively a direct translation of Nondeterministic Finite Automata into code.

Re: List is a monad

#43

Post by robinhouston »

Garlef wrote: post #18
robinhouston wrote: post #4

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.

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` toget…

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.

Re: List is a monad

#44

Post by ryandv »

pkal wrote: post #41
blakehawkins wrote: post #33

Earlier quoted context omitted.

Can you explain the nondeterminism part of your comment more?

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.

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

[1] https://en.wikipedia.org/wiki/Nondeterministic_finite_automa...

Re: List is a monad

#45

Post by whateveracct »

Jaxan wrote: post #35
nemo1618 wrote: post #31

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…

Isn’t it the case that for a given functor (on Set) there can only be at most one Monad structure?

Nope. It's that there's only one lawful Functor instance. But Applicatives and Monads can be multiple - lists are the classic example (zip vs cross-product)

Re: List is a monad

#46

Post by ryandv »

tel wrote: post #40
pdhborges wrote: post #12

Earlier quoted context omitted.

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

The more constrained your theory is, the fewer models you have of it and also the more structure you can exploit. Monads, I think, offer enough structure in that we can exploit things like monad composition (as fraught as it is), monadic do/for syntax, and abstracting out "traversals" (over data structures most concretely, but also other sorts of traversals) with monadic accumulators. There's at least one other pract…

> There's at least one other practical advantage as well, that of "chunking".

> When we have a grasp of relevant, powerful structures underlying our world, we can "chunk" along them to reason more quickly.

This is one thing I've observed about Haskell vs. other languages: it more readily gives names and abstractions to even the minutest and most trivial patterns in software, so that seemingly novel problems can be quickly pattern matched and catalogued against a structure that has almost certainly been seen before.

One example: I want to run two (monadic) computations, and then somehow combine together their results (with some binary operation). Such a trivial and fundamental mode of composition, that seems to lack a name in almost every other programming language. Haskell has a name for this mode of composition, and it's called liftM2.

Never again will you have to re-write this pattern for yourself, leaving yourself open to error, now that you have this new concept in your vocabulary. Other languages will happily let you reinvent the wheel for the umpteenth time, or invent idiosyncratic patterns and structures without realizing that they are just particular applications of an already well-studied and well-worn concept.

Re: List is a monad

#47

Post by kelseyfrog »

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

2. https://en.wikipedia.org/wiki/Knowledge_argument

3. https://en.wikipedia.org/wiki/Physicalism

Re: List is a monad

#48

Post by Jaxan »

whateveracct wrote: post #45
Jaxan wrote: post #35

Earlier quoted context omitted.

Isn’t it the case that for a given functor (on Set) there can only be at most one Monad structure?

Nope. It's that there's only one lawful Functor instance. But Applicatives and Monads can be multiple - lists are the classic example (zip vs cross-product)

Ah right. Didn’t remember it correctly.

Re: List is a monad

#49

Post by [deleted] »

whateveracct wrote: post #45
Jaxan wrote: post #35

Earlier quoted context omitted.

Isn’t it the case that for a given functor (on Set) there can only be at most one Monad structure?

Nope. It's that there's only one lawful Functor instance. But Applicatives and Monads can be multiple - lists are the classic example (zip vs cross-product)

[deleted]

Re: List is a monad

#50

Post by hirvi74 »

gr4vityWall wrote: post #27

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

Reminds me on an analogy for a monad I once heard. Not sure if it is correct because I lack the mathematical understanding to verify.

Anyway, a nested To-Do list is (allegedly) a common form of a monad. Say I am trying to clean my whole house. Well, I could have an item for a task like cleaning the kitchen that has each task I need to do in the kitchen in order for the kitchen to be cleaned. I can do the same for the living room, garage, etc..

However, that is mainly for organization purposes. While I may write the tasks in a nested manner, I could very well write each item as just a long flat list of To-Do tasks, and in reality, all the tasks are effectively completed as if they were one large flat list.

Is that kind of what you mean by 'flatMappable'? Nested To-Do lists being flattened and mapped to one large list? As in, a To-Do list of To-Do lists is just a single, larger To-Do list?

Post reply on HN