4 ms·

It looks like this article jumps right into the deep end. I'll try to speedrun some context: * You have monads in your language: - Optional, Future, Prom

by mrkeen 3y ago

It looks like this article jumps right into the deep end. I'll try to speedrun some context: * You have monads in your language: - Optional, Future, Promise, List, Observable, etc. * Your language's type system can't refer to them generally. This is why you don't see the word Monad in your language. If it could, you'd see: - Optional<A> implements Monad<A> - Future<A> implements Monad<A> - etc. * Why is this important? It means you get to reuse the same (familiar!) machinery even when faced with a new library: - Turning a List<Future<A>> into a Future<List<A>> uses the same few standard library functions as: - turning a Vector<Arbitrary<A>> into an Arbitrary<Vector<A>>. * So what's the limitation of Monads? They only compose with their own concrete type: - Optional compose with Optionals. - Futures compose with Futures. - What if you want both, e.g. a FutureOptional<A>? * Monad Transformers let you stack different types of Monads on top of each other, e.g: - FutureT <Optional, A> - OptionalT <Future, A> - EitherT <L, ReaderT<E, State <S>>, R> * This means you can write functions which use features from any of those monads, but importantly, you can reuse any code written for only one of those monads: - An Optional<A> cannot become a Future<A>, but - both Optional<A> and Future<A> can trivially become FutureT <Optional, A>> - This is called lifting.

Twey 3y ago
Semi nit (but semantically quite important): not `Optional<A> implements Monad<A>`, but `Optional implements Monad`. The reason many languages can't encode the `Monad` type class correctly is due to this fact: type constructors like `Optional` (higher-kinded types, in the lingo) are second-class in a lot of languages, so you can't refer to them directly in your type class definitions/implementations. The practical upshot of this is that (similar to what's touched upon in the article) if you have a true `Monad` constraint you can use the `Monad` operations for any choice of `A` without requiring a different constraint for each possible `A` (which you would otherwise need, because there's no guarantee that `Optional<A> implements Monad<A>` implies that also `Optional implements Monad)`. If you have sufficient machinery available (universal constraints, basically) you can hack around the lack of HKTs by using a constraint like `forall A. Optional<A> implements Monad<A>` and having some kind of type-level map function that gets you from `Optional<A>` to `Optional` for any `A` and `B`. This is the trick people use in Rust, for example.
- Tainnor 3y ago
 > there's no guarantee that `Optional<A> implements Monad<A>` implies that also `Optional implements Monad In a language like Java (and presumably many others) a generic type argument is implicitly universally quantified. Optional<A> implementing Monad<A> would therefore imply that Optional implements Monad. The problem for why you can't define "monad" as an interface in Java is because you can't refer to the type constructor (due to the lack of HKT, as you yourself explained). That means that you can't even define "map" generically. You can define it for Optional, or List: class Optional<A> { ... Optional map(Function<A, B> f) { ... } ... } class List<A> { ... List map(Function<A, B> f) { ... } } but you can't extract map into a Monad interface because you'd have to write the return type as "T" or something and that's not possible (for a non-concrete T).
 - Twey 3y ago
 The universal quantification works for defining the _implementation_, but (by itself) not for defining the constraints. Yes, if you write an implementation for `Optional<A>` then it _is_ implemented for any `A` — but it's impossible for an implementation to _require_ it to be implemented for every `A` (and thereby be able to take advantage of that fact, e.g. to be able to know that `Optional<A> → Optional` is well-defined for any `A` and `B`). :)
skybrian 3y ago
Thanks for writing this explanation. Now I’ll explain the case against it: I think I’d want write out the function for a transformation from a list of futures to a future containing a list, give it a name, and explain what it does. This is waiting for all the futures to settle, right? And you have to explain what happens when any of them fails. And indeed, this is a standard library function [1]. Deriving it instead of naming and explaining it will make it harder to understand any code using the derivation because you can’t look up what Promise.all does. If the code and explanation is written in terms of Arbitrary instead of Future then the explanation will be difficult to write and difficult to read. Defining it for an arbitrary datatype instead of a List would complicate the explanation too. The lesson of monad tutorials is that there are some levels of abstraction that are usually not worth it because they’re too hard to explain. Explaining how async works is difficult enough. [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise/all https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- tsss 3y ago
  And how are you going to write all the functions for the countless different combinations of types? This is what many users of the mtl library do and it's clear that it doesn't scale, it's error prone and the code is often not even much more readable. Clearly, some kind of mechanism that is easily composable without ceremony is needed. The real problem is that lifting/unlifting monad transformers which are not monad morphisms (mostly those that have some kind of state) is inherently unsafe. This is where MonadTransControl and MonadBaseControl classes come into play and the whole controversy surrounding them. Haskellers have debated for years about the correct semantics to use here.
  - skybrian 3y ago
    I don't need to write all those functions that I'll never call. I write the few that I use in my own code, which is probably doing something fun or practical rather than abstract. (But if you use these abstractions extensively, maybe Haskell is for you?)
- sfvisser 3y ago

by mrkeen 3y ago

Twey 3y ago

Semi nit (but semantically quite important): not `Optional<A> implements Monad<A>`, but `Optional implements Monad`. The reason many languages can't encode the `Monad` type class correctly is due to this fact: type constructors like `Optional` (higher-kinded types, in the lingo) are second-class in a lot of languages, so you can't refer to them directly in your type class definitions/implementations. The practical upshot of this is that (similar to what's touched upon in the article) if you have a true `Monad` constraint you can use the `Monad` operations for any choice of `A` without requiring a different constraint for each possible `A` (which you would otherwise need, because there's no guarantee that `Optional<A> implements Monad<A>` implies that also `Optional implements Monad)`. If you have sufficient machinery available (universal constraints, basically) you can hack around the lack of HKTs by using a constraint like `forall A. Optional<A> implements Monad<A>` and having some kind of type-level map function that gets you from `Optional<A>` to `Optional` for any `A` and `B`. This is the trick people use in Rust, for example.

Tainnor 3y ago
> there's no guarantee that `Optional<A> implements Monad<A>` implies that also `Optional implements Monad In a language like Java (and presumably many others) a generic type argument is implicitly universally quantified. Optional<A> implementing Monad<A> would therefore imply that Optional implements Monad. The problem for why you can't define "monad" as an interface in Java is because you can't refer to the type constructor (due to the lack of HKT, as you yourself explained). That means that you can't even define "map" generically. You can define it for Optional, or List: class Optional<A> { ... Optional map(Function<A, B> f) { ... } ... } class List<A> { ... List map(Function<A, B> f) { ... } } but you can't extract map into a Monad interface because you'd have to write the return type as "T" or something and that's not possible (for a non-concrete T).
- Twey 3y ago
 The universal quantification works for defining the _implementation_, but (by itself) not for defining the constraints. Yes, if you write an implementation for `Optional<A>` then it _is_ implemented for any `A` — but it's impossible for an implementation to _require_ it to be implemented for every `A` (and thereby be able to take advantage of that fact, e.g. to be able to know that `Optional<A> → Optional` is well-defined for any `A` and `B`). :)

skybrian 3y ago

Thanks for writing this explanation. Now I’ll explain the case against it: I think I’d want write out the function for a transformation from a list of futures to a future containing a list, give it a name, and explain what it does. This is waiting for all the futures to settle, right? And you have to explain what happens when any of them fails. And indeed, this is a standard library function [1]. Deriving it instead of naming and explaining it will make it harder to understand any code using the derivation because you can’t look up what Promise.all does. If the code and explanation is written in terms of Arbitrary instead of Future then the explanation will be difficult to write and difficult to read. Defining it for an arbitrary datatype instead of a List would complicate the explanation too. The lesson of monad tutorials is that there are some levels of abstraction that are usually not worth it because they’re too hard to explain. Explaining how async works is difficult enough. [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise/all https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

tsss 3y ago
And how are you going to write all the functions for the countless different combinations of types? This is what many users of the mtl library do and it's clear that it doesn't scale, it's error prone and the code is often not even much more readable. Clearly, some kind of mechanism that is easily composable without ceremony is needed. The real problem is that lifting/unlifting monad transformers which are not monad morphisms (mostly those that have some kind of state) is inherently unsafe. This is where MonadTransControl and MonadBaseControl classes come into play and the whole controversy surrounding them. Haskellers have debated for years about the correct semantics to use here.
- skybrian 3y ago
  I don't need to write all those functions that I'll never call. I write the few that I use in my own code, which is probably doing something fun or practical rather than abstract. (But if you use these abstractions extensively, maybe Haskell is for you?)
sfvisser 3y ago