Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Arrive at monads by going from composition of p...

Arrive at monads by going from composition of pure functions to composition of effectful functions

Arrive at monads by going from composition of pure functions to composition of effectful functions - I made some summary/overview slides of Rob Norris' (https://twitter.com/tpolecat) very interesting talk: 'Functional Programming with Effects' https://www.youtube.com/watch?v=po3wmq4S15
He starts from pure function composition and uses math to derive Kleisli composition and Monad.

Keywords: pure functions, effectful functions, effects, function composition, functional programming, kleisli composition, monad, scala.

Philip Schwarz

August 26, 2024
Tweet

More Decks by Philip Schwarz

Other Decks in Programming

Transcript

  1. Arrive at Monads by going from composition of pure functions

    to composition of effectful functions summary/overview of Functional Programming Effects by Rob Norris @philip_schwarz slides by http://fpilluminated.com/
  2. [In functional programming] all we have are values and pure

    functions. We have given up a lot of expressiveness to do this. • Functions have to have an answer, but in Java sometimes you return null. How do we deal with that? • We are in the world of expressions, and expressions don’t throw exceptions. • Functions have to have exactly one answer • The power of FP comes from, it gives us the ability to reason locally about stuff, and if we have this sort of big global scope that is introducing stuff that any part of our program might depend on then that hinders our ability to do that. • Logging is a side effect, right? The whole point of logging is to see when things are happening, and in FP we are dealing with expressions, we don’t care when things happen: it doesn’t matter. So what happens to logging [in FP]? • Mutable state, obviously we don’t have var any more. • And imperative programming in general: where does it go? It seems like a lot to give up, right? And a big barrier to learning FP is understanding what to do when you need one of these things and what FP principles do you apply to solve these problems that you run into all the time when you are writing programs. This is where effects come into play Effect is a very vague term and that is ok because we are trying to talk about something that is outside the language. Effect and side effect are not the same thing. Effects are good. Side effects are bugs. Their lexical similarity is really unfortunate because it leads to a lot of people conflating these ideas when they read about them and people using one instead of the other so it leds to a lot of confusion. So when you see effect, think a little bit about what is going on because it is a continual point of confusion. So what I want to do is talk about six of the effects, they are kind of the first ones you learn when you start doing FP. They are kind of the first things in your toolbox. There are many more and many ways to classify them but we are going to start small. We are going to talk about these effects… what they mean and … so hopefully by the end we’ll have a pretty precise definition of what these things have in common. Rob Norris @tpolecat
  3. Partiality: we can define functions that might not return an

    answer. If we could combine f and g the effects would have to be combined. If either of them failed, we couldn’t possibly get a C out. So if we had a way of smashing them together by doing function composition that would be pretty powerful but we can’t. You can have functions that might fail but also give you a reason why they failed. This kind of gives us exceptions back. We can’t compose f and g. If you were able to compose them together, if you finally got a C out, you would know that both of the computations worked. If one of them failed you woud get a Left and you would get the first Left that was encountered because the computation would have to stop there because it wouldn’t have a vaue to pass on. But again that composition operator isn’t defined. But can you see the power that you would get by being able to do that, by chaning these things together? In FP we take an interesting interpretation of List, we sometimes think about it as a kind of nondeterminism. We can define functions that might return any number of answers. And if we were to compose these two together end to end we would want to get every possible answer that we could have got from these two functions. But again: we can’t do that. We can compute values that have a dependency. I can construct this computation p with a path and then I can run it with different hosts and I’ll get a different answer back. It’s just sort of a currying thing at this point, a partial application thing, but if we were to compose these things we can have multiple computations that were dependent on that same configuration. We could compose them together and get a new computation and pass the configuration in and get our complete answer back. We can’t do that because we haven’t yet defined function composition for that type. This is another effect, that’s a pair of some value W and an answer A. And the intuition here is functions that can annotate the values that they compute…[with some info] and the info might be a log message. If we were able to compose these things together, what we would get are computations that can talk about what thery are doing and then if we had a way to smash those infos together we could make a big computation, run it, and get an answer and some kind of extra collected bits of information like a log for instance. A computation that takes some input state and computes a value and returns another state that might have been modified. And if we were able to compose these things together then we would have our state threaded through our computation, which is nice, that kind of gives us mutability back, or a lot of the cases that mutabiity is used for. Partiality Nondeterminism Logging Mutability Dependency Injection Exceptions Functional Programming with Effects https://www.youtube.com/watch?v=po3wmq4S15A Rob Norris @tpolecat
  4. Because effectful value takes too long to say, we sometimes

    call them programs That’s our problem. So what can we do? What would it take to make them compose? Here is our function diagram for pure function composition. And if we sort of replace things with effectful functions, they look like this, so we have something like andThen, looks something like a fish, and every type has an id, we are calling it pure. If we were able to define this and make it compose then we would get that power that we were talking about. So how do we write this in Scala? We can implement compose, the fish operator using flatMap, so the fish operator is something we can derive later really, the operation we need is flatMap. Rob Norris @tpolecat
  5. So we implemented the fish operator and we can do

    this kind of composition, but what we have forgotten about are all the rules for the category. So what we want to do is figure out what this means in terms of flatMap So I am going to tell you what we have been doing: this is called the Kleisli category. And this Fishy typeclass that ve derived, from nothing, using math, is Monad. So this scary thing, it just comes naturally and I haven’t seen people talk about getting to it from this direction. And so I hope that was helpful. We also derived all the laws, but notice that unlike the rules for function composition, which we proved were true and are necessarily true from the types, this is not the case for Monad. You can satisfy this type and break the laws. So when we define instances we have to verify that they satisfy the laws, and Cats and Scalaz both provide some machinery to make this very easy for you to do. So if you define instances, you have to check them. So we have pure and flatMap that are abstract but we can define some familiar operations in terms of them, e.g. map and tuple. We can define a syntax class that adds these methods so that anything that is an F[A], if there is a Monad instance, gets these operations by syntax. Rob Norris @tpolecat
  6. Let’s not, because I have to introduce Monoids to do

    that. The gist of it is you can get logging back Partiality Exceptions Nondeterminism Dependency Injection Logging Mutability Rob Norris @tpolecat