Hacker News Reader

Comment by urxvtcd | Hacker News Reader

While I _think_ I understand monads on some rudimentary level through how join and bind operate, your "just sequencing" doesn't tell me anything. And this is a problem with a lot of these texts. Maybe that's trivial to the writers, but it makes me feel even dumber when I cannot understand a concept I already understand, lol.

View on HN

This is one of those things where looking at the type signature hard enough eventually gives the game away, but most writing on it sucks:

    bind :: m a -> (a -> m b) -> m b

Because that function in the middle takes an `a`, your implementation of `bind` needs to be able to take an `m a` and pull an `a` out of it, which means it also has to evaluate however much of `m` is needed to actually get to that `a`.

Because that function in the middle returns an `m b`, binding again with a function `b -> m c` requires you to pull `b` out of `m b`, which in turn forces pulling an `a` out of `m a` to make progress. This is where you force sequentiality — you can only evaluate the `m` in `m b` after you've evaluated the `m` in `m a`

Caveat: there is the trivial case of calling the middle function zero times. Which does happen (in the case of a Maybe type) but presumably any useful code needs to be able to call the function sometimes.

This makes a lot more sense than anything I've read about this in the past, thanks for the explanation!

Thanks, that's reassuring. I've long been frustrated by just how bad monad posts are in general, and been meaning to write something up about it that makes it clearer. It's good to know that I'm at least going in the right direction :)

A big problem with "just sequencing" is that there are a lot of ways of sequencing that either don't require the complexity of a monad or for which the monad interface is insufficient.

The former is probably uncontroversial but I'd love to see some examples of the latter since my understanding was that monads are essentially the generalization of sequentiality.

One obvious place to look is things that are almost a monad but can't be lawful and which might nonetheless be useful. An example that comes to mind is trying to use Set as a monad (for nondeterminism like the list monad, but with deduplication), which you can't do for some potentially avoidable technical reasons (it would have to be restricted to things you can Ord) but more importantly Set can't be a monad because Set can't be a functor, because `x == y` does not actually imply that `f x == f y` (even for reasonable definitions of Eq), so `fmap (f . g)` might not be equivalent to `fmap f . fmap g`.

I thought it was the case that you can't implement the Monad type class using the built in Data.Set implementation of Sets but there's no reason in principle why you couldn't build a Set Monad that works that way, right? Perhaps I am mistaken so I will investigate further.

Looks like https://hackage.haskell.org/package/set-monad is an example.

There is a reason in principle that you can't build a Set Monad that works that way: it violates the functor laws.

In order to be a functor, you need `fmap (f . g) == fmap f . fmap g`.

The problem is that some functions (for instance, Data.Set.showTree) can produce different results for two values that compare equal.

For instance, imagine we have a set containing (only) the lists `[1,2]` and `[2,1]`; let's call it s. How many elements are in `fmap (Data.Set.showTree . Data.Set.fromList) s`? Two, because the result of fromList winds up being order dependent in the structure of the internal tree, even though both Sets represent the same set of values. On the other hand, how many elements in `fmap showTree . fmap fromList`? Just one, because the Set has a chance to "see" the output of fromList and notice that they are equal according to Eq.

Does this violation of the functor laws matter? Maybe; likely not; it depends on your use case.

But mathematically it means that the thing we are working with is not a functor, and so the thing we are working with is also not a monad (as all monads are functors).

İ prefer to say that show tree violates the abstraction. You can have s1=s2 but not f(s1)=f(S2). So f (show tree) is not a real function (or = is not a real equal). But showtree is a debug function, it doesn't count. İt's like saying in C that a=13 and b=13 isn't a real equality because &a and &b are not equal. There is the underlying structure and the structure after the equivalence. You have to know of what you're talking.

I'm not unsympathetic to that position, but I think it's ill advised to take it as far as "Functor means functor up to Eq". I grant that showTree in particular is a debug function that will usually be called at the end of any meaningful computation, and handwaving it in particular away is probably fine. I don't think we can say the same of something like splitRoot, which instead breaks the abstraction for the sake of efficiency.

> You have to know of what you're talking.

And the language (/ecosystem) gives you no way of specifying, so we have to be somewhat conservative. I've actually been thinking (partly driven by trains of thought such as under discussion here) that it might be very interesting to have a language that let you reason explicitly about different sorts of equality (tentatively defined, in the context of the language, as indistinguishability relative to some interface).

It's called math.

Reply on news.ycombinator.com