Free monads from scratch | Hacker News Reader

Free monads from scratch

siraben.dev

22 pointssiraben16 comments

> While it looks like boilerplate, we can more or less mechanically write out the instances…

Yes so why doesn’t some GHC extension do this?

The issue I have with this and Functors and Monads and Monad transformers is that there is a lot of boilerplate. I wish i could apply f x y instead of lift $ f <$> x <*> pure y. It would be awesome if there was a ghc extension which, whenever it encounters something like ‘(a -> b -> c) applied to (f a and f b, expected to return g (f c))’ it automatically adds the appropriate ‘fmap’, ‘bind’, ‘pure’, ‘lift’, ‘inj’, ‘Impure’ etc. Then combined with do-notation, you can write truly imperative-looking code, without having to manually convert ‘a’ and ‘State a’ and ‘Reader a’ and ‘Exception a’ into ‘(State :+: Reader :+: Exception) a’.

IMO free monads are an implementation detail for how to enable typed effects and subtypes in a pure language. They’re still kind of important for users to understand, but they would be easier to explain if you let users write imperative-looking code first and then convert it into free monads. That would fix the question most people have when learning about category theory, “why?” - most people don’t know what to make with category theory abstractions because they don’t know what they’re for.

> I wish i could apply f x y instead of lift $ f <$> x <*> pure y.

In "Applicative Programming with Effects"[0], the authors use such a notation, and even leave it as an exercise to implement it in Haskell using MultiParamTypeClasses:

> Given Haskell extended with multi-parameter type classes, enthusiasts for overloading may replace ‘⟦’ and ‘⟧’ by identifiers i[ and ]i with the right behaviour.

So they have code that looks like

  eval :: Exp v -> Env v -> Int
  eval (Var x) = fetch x
  eval (Val i) = ⟦ i ⟧
  eval (Add p q) = ⟦ (+) (eval p) (eval q) ⟧

> Yes so why doesn’t some GHC extension do this?

It's possible to derive the functor instance automatically if the data type is built from products, sums and arrows. However even for Applicatives you can't do this in general because there can be many lawful Applicative instances for the same type, for instance[1] for lists.

[0] http://strictlypositive.org/IdiomLite.pdf

[1] https://hackage.haskell.org/package/base-4.16.1.0/docs/Contr...

It is possible to derive Applicative.

The next release of GHC is able to derive Applicative for product types: `deriving Applicative via Generically1 F`.

If you have a sum type you can derive Applicative as well, but as you mention there are often multiple options so this requires user assistance: `deriving Applicative via Idiomatically F '[LeftBias Id]`.

Here is the library that allows that: https://hackage.haskell.org/package/idiomatic

Doing the magic stuff you say doesn't work well due to the ambiguities that could result.

Applicative style is so trivial that it's hard to say it's worth it to automate it at the cost of ambiguities.

Feel free to write a GHC proposal to solve this trivial deficiency - anyone! I dare you! I'd like to see this complaint's rubber hit the road.

Monads are hard. I read many articles explaining what a monad is and what is good for but I never really grasped the concept. I probably have to learn Haskell.

https://fsharpforfunandprofit.com/rop/ is by far my most recommended starting point, using a railway analogy. To grossly oversimplify, as far as I can tell, a monad is a type well-defined enough that you can hook up functions that work with it in a “parallel tracks” manner. So it’s great for chained functions, and reusing and weaving those functions, where you accumulate information other than the “obvious” thing to return as you go along, like errors or logging or IO.

I know that also. Not great not terrible. Still couldn't clarify the thing.

From personal experience Scala also works. It's 100% possible to learn monads using https://scastie.scala-lang.org/ as a scratch pad.

It strongly depends on your background. What kind of programs are you writing? If you have a lot of boilerplate for error handling, creating chains of promises or passing a file handler to log to around, that's the kind of thing monads can help abstract away (from a programming point of view).

They are a more general construction in category theory but knowing that doesn't tell you how to use them (because the full generality is not often needed).

How about [2013 Philip Wadler - The First Monad Tutorial](https://www.youtube.com/watch?v=yjmKMhJOJos&t=1490s&ab_chann...)

There's an endless stream of monad tutorials and I think they (almost) all misunderstand the point of confusion. No one gives a f*** about monads, they care about state.

If you've internalized reasoning about a program's execution symbolically and in a time-independent way, then monads solve the problem of how you enforce a correct sequencing of otherwise time-independent operations at a library level without any fancy modifications to the type system. And oh by the way, this structure shows up everywhere and isn't that pretty cool. People who hang around in the formal PL world tend to assume this already because it emerges naturally from how we talk about the semantics of languages via symbolic manipulation.

But if you haven't grasped that yet, then monads solve a problem that you probably don't even realize exists and no amount of rephrasing the monad laws will help you.

I'd almost always recommend anyone new to Haskell ignore monads as much as possible. Fiddle around with evaluating toy functions with pen and paper symbolically to reason about the semantics, and then try to imagine how you could represent the state of a program changing across the page by creating a new object representing the state of the program from the old state. Then, dig in to the RealWorld type and how the IO Monad actually works (not at a type level).

Thanks for explanation. The point is that I do not really intend to learn Haskell (I don't have the motivation for), I've been just (very) curious to understand what's about these concept called monad: - Why does should exist? Why can't they be simply replaced with control structures (if, case, switch etc.) ? - Why there is so much fuss on the web, in the FP world, about monads?

They can't be explicitly replaced with control structures because implicit in that suggestion is the idea that when writing code you write what the code _does_. If you call the same function with the same inputs you can expect exactly the same machine level code to execute (perhaps taking different branches based on external state it reaches out for).

Contrast that with what happens in Haskell and friends. When writing code you define what the _inputs and outputs_ for particular functions should be. The actual code generating those inputs and outputs is free to be replaced or removed as the compiler sees fit. That buys you a lot of things (trivial parallelization, excellent type checking, ...), but it self inflicts an extra problem we didn't have in the previous paradigm:

In the real world, we don't in fact just want to run a program and get an output. The way we interact with, e.g., a GUI is an important part of the program's behavior. If your mental model of code is that we're sequentially doing a series of things then this isn't ever a problem you would even have because you would just write your code to do the right things at the right time, but if you've adopted a model where you're defining outputs for your inputs you need some way to shove state and order of effects into that system for it to be useful.

Enter stage-left: monads! Yes they're pretty and ubiquitous and whatever, but the problem they solve for us is specifying an order of events (by virtue of taking the entire monad in as an input and spitting it out as an output) in a way wholly compatible with the type system we've already developed.

Yes, and monads in Haskell seem a bit different from monoids in the category of endofunctors.

I read once, somewhere, an advice from a computer scientist: one with OOP background should perceive a monad as a class that has everything contained: types, declarations, methods, error handling. Is it true ?

This was how it was taught at my school in Java [0], although thinking about monads as a container is weird since functions are monads as well.

[0] https://nus-cs2030s.github.io/2021-s2/33-monad.html

Reply on news.ycombinator.com