The Functor, Applicative, Monad talk

scale.bythebay.io: Adelbert Chang, The Functor, Applicative, Monad talk

Recording: scale.bythebay.io: Adelbert Chang, The Functor, Applicative, Monad talk

so my name is Alec poore Cheng I am a data engineer at Target which is the same target where you guys hopefully buy stuff I work on deployment infrastructure there and today I want to talk to you guys about functors and Flicka tips and monads now when I started thinking about this talk a couple weeks ago I realized had 40 minutes to cover three of probably the most fundamental concepts of functional programming and I'm aware that braver speakers and I have tried have tried to cover less and more time nevertheless I'm going to attempt to do this anyways so please bear with me and I hope that you guys can leave understanding these three concepts and understanding why functional programmers care so much about them so to start things off we're going to make one big assumption is that we are interested in doing pure functional programming okay that's sort of the private self is talking and I'll build on top of that and we do pure functional programming we sort of look for two properties in our programs one is that it's sort of like by definition is that every function in our program is a function in the mathematical sense which means if I if I have a function from A to B and I give it an A I should get a an actual B value back all right so this will image things like Nobles and exceptions the second thing is for all expressions say f of X we want to be able to sort of factor it out in our program so if I have a larger expression say G of f of X f of X I want to be able to pull f of X out into a variable and a substitute e wherever f of X was and these two district factoring should give me the exact same program so what I've just done is I've said so for example the first property of saying all our functions must be functions I've eliminated null and exception thrown so that's one implication event the second application is we cannot have mutation print statements we're just side effects in general so as a sort of demonstration let's say we had a mutable variable X and then I increment X twice we can sort of test to see if this is this meets our criteria by factoring out that increment expression to e and is substituting e to where those two things are and these two programs are not identical right and in one case you can observe that X is going to be two and the other case you can observe that X is going to be one so and so this this violation will happen in general with any sort of side effect so we can't have that now what I've just done is I've said all right you guys can't use Knowles you can use exceptions you can't use mutation and kind of side effects but what I'm saying is we're eliminating sort of the implementations of these things but we still want to talk about the concepts they represent right so for instance for null the concept of enola useful right what knowledge is generally used to communicate is to have a value that may or may not be there right so maybe you do something like look up a key in a dictionary and the key isn't there so your return tool instead but what you're trying to signal is you have no value to return so you're returning null so what we can do to sort of regain that power without introducing this just weird sentinel value that just magically inhabits every type as we can just make the notion of not having not Hanako value a completely separate type so in scala we have this option type where we sort of decide separate from a so if I have an A in a world without null I can say I definitely have an A and I can do things with a passive it functions whatever and I shouldn't have to worry about it like somehow being missing and then we have a separate type called optional a which has either a sum of the actual value we care about or it has none and the big difference here is for one option of a is a completely separate type from a which means we can't treat optionally as just an A and hit some sort of like null pointer exception the second thing is in a world without null when I have an A I know for sure that I have an A and then when I have an optional a I know okay this thing may or may not be missing and so when I go to work with it I know I have to handle the case where it's not there we do a very similar thing with exceptions right so exceptions themselves we're going to disallow but sort of the concepts underlying exceptions to partiality of functions we still want to have because not all functions are going to be total at least in Scala type system so we will have some functions that will be partial we maybe we read from a database in a database is down or something like that so just like before instead of giving an A we're going to return this data type called either there's going to be either an error or a and as its name suggests it has two cases you either have a left of some sort of error value maybe it's a string maybe it's like your own data type and we have right of the actual value that you care about and so again when we have an a we know we definitely have an A and when we have something that may or may or may not fail we'd return either some error and an a do two separate types I can't treat an either as an A and when I go to work with either then I have to handle the error case mutation is a little bit trickier but it's still doable so we still are gonna have computation that needs to have some notion of reading and writing state places where this may come up are like maybe random number generation where you need to keep track of some seed value do they generate the random number off of a more interesting one maybe it's like a retry policy where you have to keep track of how long you waited to retry to request a previous time and then if that failed again you know how much to wait the next time so if you're doing something like exponential back-off for instance and so what we can do is instead of just viewing it as a regular sort of value that has that can mutate stuff like ambiently if we're going to treat it as it's really a function that takes in the start state and produces a value and to sort of quote mutated state and we can represent this literally as a function from s to the tuple a comma s where s is going to be the state we keep track of so maybe it's long in the case of random number generation or to finite duration for like retry policies and then a will be like the actual value that we're going to emit they were gonna produce from that state so there's a general pattern here right for all our functions a to be that sort of do something besides produce a B so it possibly fail possibly missing and need to mutate stuff instead of returning just a B we're gonna return sort of an Augmented B so some examples would be like if I have foo which returns a value that may or may not be missing I return option of bar if it can fail I return either an error or a bar or maybe if it needs access to than some state I just return like a state action associated with it and some terminology that I'm going to use throughout this talk and that you guys might hear and sort of just talking to other functional programmers these these kinds of functions are often referred to as effect full functions so option either and state are examples of effects and values without these without these behaviors are referred to as pure so so the functions here will often be refer to as effectual functions if we're looking at say just a bar as opposed to an optional bar you might hear that being referred to as a pure value it's just a value in its own right it doesn't sort of have any additional behavior with it so now we have all these effects we want to work with them right because we want to do useful things to our programs so as an example let's say we're parsing an integer off a string and if the parse fails we return none if it succeeds and return some of the integer and now we want to say make sure the integer is not negative so we because we know it's option and we can't just say like xmax zero because that wouldn't type check so we say all right if we have a sum which means we have the value then I'll do a Mac zero but now we have to handle this none case right and so with none unless like we don't have an old we're returning null and exceptions don't exist so we can't really like put null here so what can we do well we know X is some computation that may or may not that produces a value that may or may not be there and why it depends on X which suggests that Y itself then may or may not be there so what we can do is instead of expecting Y it just be an integer we say Y really should be an option integer and in the case where X does have a value then Y has a value and in case where X doesn't have a value then why doesn't have a value we do a very similar thing with either right so either maybe we're reading off config and we're getting the host key and parsing it as well and if we have every part successfully didn't want to add like an API and point to it otherwise if we failed when you do something with FA later we can't throw exceptions so what we can do is do the same thing we did before as sort of just propagate that error through because if we depend on some computation that can fail then we ourselves can fail state is a little bit trickier but it's going to be more or less the same pattern so let's say we have X which is going to be some state action that will eventually produce a random integer right so remember that state long int really as a function long to the pair int long and we know if Y depends on the state action then Y itself should be a stateful thing and so we can we can off by creating a state action we know that the input frame is going to be long we know V X the the return type of this lambda is going to be a pair of a double and along so we can do is run the first state action that we depend on so we get our random integer and then the new scene that it may emit and then right before you turn it maybe we want to take the reciprocal of it for instance so we just do one point no divided by random in and then we thread and you see through so all of you follow more or less the same pattern we want to apply a pure function to an effectual value and we can just do this sort of by to normal mechanism because an F of a can't be treated as an A if it could this whole exercise work would be futile so the whole point is F of a is separate from an A but we still want to be able to apply fun functions expecting an A to this value and so what we've seen is in for each F option state either they have some notion of getting inside the value and observing what that a is and then indicates what we do have an A apply to function and then we're also going to plumb some extra bits through and these sort of extra bits are the something that the effectual functions do so for option it's sort of propagating the effect of not having a value for either you propagate the error and for state you're propagating the seed or the state and so being the good programmers that we are we see the same pattern occurring over and over again and we want to be able to talk about them generically so we unify this pattern into this type class you think of as an interface called functor and functors basically talked about tech constructors so here I call it f you can substitute F for option either state I Oh list future and in order to be a functor you need to support this rare generic map operation we're given an effect well value a and a pure function from A to B I want you to somehow apply that function tree to affect what value so f of A to F of B so here's an example invitation or option for option we're going to pattern match if it's a sum apply to function we wrap it in some if it's a none we have nothing to do so we plum it through similar case for either okay if we have a right then we can do what we want if we have a left we plumbed that through and then similar thing for state and so with that so with that map operation implement and we could envision sort of a map syntax that gets put on all these effect types right so we can imagine a map method that exists for option for either and state and now what we can do is we can just call map and then just give it the function that we actually care about and we no longer have to deal with sort of doing the boring plumbing so in the case of like we parse an integer I am going to back over it and just give it a function I care about and no point do I explicitly say property to none through because that's sort of boring similar with like the config reading we just say part of my host if the host exists I want to attack an endpoint onto it if it doesn't then I just get the left of the left of the error message and it for energy for my random integer take the reciprocal and no point am I explicitly propagating the new state because that's all handled under the covers for my map method for them drink some water so functors are all about applying a pure function to a single effective value but more likely than not we're going to want to work with multiple effective values right presumably we'll have more than one thing that can fail it'll have more than one thing that's going to depend on state how do I combine those two so we can generalize what we've been doing to apply a pure and airy function to end effect flow values and what we're going to do specifically is focus on two pulling in two values so I want to implement this operation we're given an F of a and F of B produce F of two pair a B and from there we can use map to actually go inside the quote go inside to F D structure to a point and apply our pure energy function so we're going to focus on just troop link which is like the simplest thing we can do to combine two effective values so we can try to do this generically with just functor so let's say we have an F of a and F of B where F is functor I want to produce F of the pair a B we're going to need an aid to like tuple of values together so we're going to map over F a and then we also need a B so maybe we try to map over FB and pair it up but this doesn't quite work out because what we end up with is an F of a F of a and B and we have with just functor we don't know like how to flatten the two F together so imagine like this will give us an option of an option of an endpoint and if you have three effective values which will give us option of option option and it gets really like nightmarish so this suggests that we needed some additional power beyond functor so let's look at what this looks like for different effects again so for option you're going to have an option video an option B and we want to get an option at the pair so in this case we want to pattern match mature options and if they're both our sums then we compare them up otherwise if either of them are none then we have to threaten done through which makes sense because if I want to compose two values and either of those values may not be there then I don't really have a way of composing them so I have to fail the entire thing similar case with either if I have both rights then I can do right of right of the pair two values otherwise if I have an error then I need to propagate that error through because if I have again if I want to compose two values that they can fail then if either of them failed I need to fill the entire thing because I don't have both values in order to tuple them together it's gonna be a similar thing with state but again is going to be a little bit tricky because we're working with like not a seal trait so we'll walk through this one I have to say for conversations one that produces an a and another that produces a B both depend on some state s and I want to produce some state action that will produce the pair a B given some status so we'll create a state with the current state we'll do what we did before we can run the first one and that gets us an A and the next state where it's just interesting now as I can now run the second state action but I run it against the state return by si which means when I run SB it can observe any state changes that si made so for example I generate a random integer and I get a new seat back and then generate another random integer that second random integer can get some new seed and so we you actually get a different random integer whereas if I just passed in like current state again I would just get the same integer over and over so that's kind of that would not be that useful and now I pair a and B together and then I thread the final state there and again we're going to do the same thing that we did before these all follow more or less the same pattern we have a notion of looking inside to effectual values and then pairing them up together while remaining inside the effect and this is what applicable are all about so applicative talks about type constructors that support the zip operation and support the secure operation so so zip takes an F of a and F of B and produces the tuple suggest the one that you've been looking at so far and then Pierre is this one that we haven't really talked about yet but it basically takes a pure value and lifts it up into the F for some notion of like lifting and of course we also want all Victor's to have this map operation because in order to work with and affect full values we're going to zip them together so we get a pair and then we're going to map over it to D structure to pair and actually apply or enter a function and it also can conceptually make sense because if we claimed to work with an independent effect for values then I certainly should be able to work with a single effect well value so here's some implications for the data as we've seen for option it's a pair option that we saw and if we're pure we're gonna just take the a and wrap it up into some for either it's gonna be the pair either that we saw and if we're pure it's gonna wrap it in a right and therefore state it will be the pair state that we saw and then the peer is a little bit more interesting it just takes the state and it produces the value you gave peer without changing the state alright so you're sort of for pure does the minimal amount of work to take a pure value and lift it into the effect as a quick note if you go to say cats where scholars said today or Haskell even and you look at applicative what you'll see is this app formulation instead so what I presented is zip map and pure will you'll typically see as app and at the sort of has a weird type signature at least in Scala where you have a function inside of an F and then you have an effective value I want to apply to function to type value all while remaining in F and this has a nice theoretical story it sort of has a nicer story in Haskell it's related but in Scala this is sort of makes for an awkward API and so I like to introduce applicative in terms of zip and map for that reason I think they make for a better story and I think zip is conceptually simpler because you can sort of see that zip is about composing two values and the easiest way possible whereas app sort of has a weird signature that being said app is for historical reasons world like the canonical representation of applicative so if like after just talk you go look at what implicative is you'll probably see app as it's just a quick note you can implement app in terms of math and zip like I have here you can also go to other ways you can implement zip and map in terms of that and so you exercise leftover here so here's some stuff that you can do now with that you couldn't do a functor that we can do with applicatives so let's say i parse two integers now both of which may or may not fail I'm going to zip them together and then map over it and then figure out which would have those two integers are large a larger and just give me back an option of and I can parse two keys from a config or I could parse three or four keys if I wanted to and then zip them together and map over it and then get point and that gets me either an error of an endpoint and if either of if any of those parts is failed and I just get the first error that I hit and then for random numbers maybe I generate two random numbers and then compute the greatest common denominator between those two random numbers and I do this all without sort of explicit again not explicitly threading through option or nuns or errors or some sort of state seed I just sort of apply to functions and I care about and all the plumbing happens for me behind the scenes because we sort of did all that work upfront when we implemented applicative now I've been talking about sort of unifying all these data types under functor and applicative but I haven't really motivated why you want to you would want to do that it's very possible that maybe you just have zip and map directly on the data type as opposed to this weird like a trait that we have but so I didn't do for functor because functor is kind of like a boring thing you can't it turns out you can't really do much with it but flicks it becomes much more interesting and so we we talk about these things in terms of T's abstractions for the same reason we talk about any abstraction we want to be able to write functions against these things generically so that anything that implements that gets all these functions for free so one example is this function called Traverse so I'm gonna assume people here know some Scala how many people have used like future dot Traverse in the standard library okay it's a fair bit so I've been writing a Scala for six seven years now and by by far the most common question that I've seen at work that people ask me and chat rooms whatever is how do I do something like future dot Traverse except instead of future I want it with like option or if either and in a standard library you sort of don't get that right so you're the response into things well you can write your own little traverse option and then maybe you'd write it like that and then now you want to do it for either so then you write another function that says Traverse either and you're right enough and so like in my previous job we had like a file that was traverse option Traverse either Traverse XYZ and you look at enough of these and you say well there's a sort of common pattern here we have one thing here that's lifting an empty list into some are effect and then we have this notion of combining to effect four values the standard library does not have a notion of does it have an abstraction that talks about these things so you sort of need to either write these ourselves or reinvent implicative and so since we have applicative now we can actually write a generic Traverse once and for all so resort i went sort of fast for the previous slide so I'll walk through this one so Traverse list says given a list of a s and a function effectual function a to F of B give me an F of a list of B so I want to apply this function to each element of the list as sort of collects the results along the way for some notion of collect depending on what F is so we walk down the list we start out with an MPV value that we listen to F to start us off so that's what peer comes in useful and therefore each a that we encounter and the accumulator so far we applied a federal function to to a to get our F of B we zip it with the accumulator and then we map over it to actually prepend it so now what we can do is take that single function every road and stay in tune it to different effect types so maybe instantiate it to option or to either of some error and so this sort of has if you look at a type signature it's sort of like given a list of strings and a function that parses the string into an integer give me an option of the list of integers and this has the effect that if everything part is successfully Dec it is some of my list of integers or if any of them fail then I get a none at the end look Traverse state it's for each element of the list apply this function that needs access to some state to each element and produce some larger state action that you can actually produces a list of V and what's even cooler is as you go down the list the func the state action that eventually gets executed for elements further down a list can observe state changes made by elements above so if I had if I was producing if I had like a list of say a bunch of integers and I was producing a random integer from each one as we're producing random integers it's changing the state behind-the-scenes and random number generation down the list can observe see changes made by elements above the list and so we have a radically different behavior for a variety of data types and these are all backed by the exact same function I just Traverse list and Stan cheated two different effects and this is the kind of like code reuse that we wouldn't be able to get without being able to talk about applicatives so I've sort of ratifying things that we normally assume to be ambient we can leverage them to to do really cool things so this is one I'm like the prime examples of code reuse we talked about functors of liquids and monads so so far I've been talking about applicators working with specifically independent effect well values and what this means is we have our values up front right F of a and F of B are given to us up front our function says given F of a and F of B give me an F of the pair a B but what if we wanted to have an FB that is dependent on the value of an F of a right so let's say I have a function called next step that takes a foo and produces an F of a bar and then I have an F of a foo and I want to produce an F of a bar so one thing we can try is well we need access to a few in order to produce the bar so we'll map / foo and we'll get the X out and so X is a type through here and it may be we apply a next step to it that gives us an F of F the bar similar situation to what we learned before and we have no notion of sort of smashing together two FS so like before this suggests that and we can try other things as well but it's not going to work out this suggests that we need power beyond just applicative when you something that allows us to compose dependent effectual values not just independent ones so let's look let's again look at what this looks like for various data types for option given an option a and the function from a to option that we get an option of B so what you can do is pattern match an option it with some none and we threaten on theory as before otherwise if it's a sum then we can produce the next option and this is sort of where the data dependency comes in where we can't really produce an option of B without an A being present so you can begin to see how the existence of options B is dependent on whether or not a is there similar case with either if it's a left we have nothing to do so we plummet through if it's a right then we can do the next step of our computation that itself may or may not fail but the dependency is we need to be able to know what that value is we won't know until like it's a runtime thing state a similar thing we're gonna walk through this so we have some state action that's eventually gonna produce an A and depending on what that a is I'm going to produce some be that itself depends on the state action so we're going to first run the thing that produces an a so that gets us a and the next state we're going to run F against a so we get our next stateful action depending on what that a is and then we're going to run the new state action against the state return by running the first one alright so you can hopefully see how this is sort of different than previous ones we have a data dependency now and this is what Mon eyes are all about so you might hear or see like a lot of tutorials that try and make different analogies but I think the one that's where clicked most for me is monads are about composing dependent effective values so if I have an effect effect for a and I have a function that produces an effect will be dependent on what that a is I want to be able to work with those so that's what flat map is all about and pure is the same period I saw from thicket 'iv and it turns out if you have flat map and pure we can implement the methods that you saw before map and zip which means if you can implement Damona interface for option either state you sort of get map zip Traverse all for free so this is one of the benefits of abstracting over these things is code reuse and so now well now all the things you can do with same with monads that we couldn't do before is do like additional parsing so maybe we parse a header from a file and depending on what that hitter is all parts the body in different ways that's something we couldn't do before maybe you're hammering config I read like this type key and if that key is serviced then I depending on what the value of that key is will parse different keys so if it is serviced in all parts like the doctor key if it's otherwise we assume like it's a jobs where you parse the job key instead so what we parse depends on the value of an earlier course and therefore like a random integer example maybe we generate a random integer and depending on what the integer is we generate a random number that's bounded by the integer I said these are things that we're going to have computation that depends on earlier steps and that's something that we couldn't do before with just Fontaine applicative so we now have a vocabulary for working with effects this is what we've been building towards sort of summarize we have functors which let us work with a single effect we have applicatives which let us work with multiple independent effects and we have monads which work with multiple dependent effects and sort of as a slightly more real-world example you can imagine that this is some some composition of values that takes a username and password authenticate it and then like draws out what the newest profile what the profile of that user is and so that within here at no point already sort of explicitly propagating state through or side-effects through or air-handling or possibly missing values now what does happens behind the scenes behind the scenes a flat map zip map and so on and so forth the only gripe about this is that it's kind of ugly right here I'm doing like three flat maps and it's already being in a fall off the right side the screen so what Scala provides is a syntactic sugar for this so without getting too much into it this this for comprehension these sugars in tune what you saw in the earlier slide and this reads really nicely I just sort of reads more or less like an imperative program the difference now being all the boring stuff for one is being handled for you so if like say getting the username fails then that whole thing just fails and that's handled for you you don't have to explicitly like catch or or anything like that if I authenticate fails and that's sort of 30 through so you sort of are able to now focus on actual business logic of the code without having to do things like if bang if this double equals null or if this needs to catch an exception or I need to mutate this variable so on and so forth so that's all I'm going to attempts to cover today I think thing I went a little bit fast but feel free to I'll be around today and tomorrow so feel free to like ambush me in the hallways and I will keep you like a better in depth tutorial if you wish but I didn't have time to cover your day that's still important laws so I mentioned in order for things to be like a functor or elective no dad you sort of have to implement this interface just implementing the interface and type-checking it is insufficient we expect these to have certain behaviors so for instance one thing is for functors if i do math with the identity function that should be the same as doing nothing at all that's an example of a while so each of these things have lost every that we want implementers to satisfy we didn't cover in competition with more than one effect so I've been caught I've been covering option either state in isolation but it's reasonable to say I want a stateful value that can fail and as possible to do that and if you want the Google term it's gonna be monad transformers but it's possible to do that and you get sort of the same benefits that we have and another thing I didn't cover is tracking iOS in effect if you are at John's talk earlier today he did show you what that kind of looks like but tracking iOS effect can almost be well it is a talk by itself so I encourage you guys to go out and see what the literature is like that this is just the tip of the iceberg I try to cover three very fundamental topics in a short amount of time so I had a skip over a bunch of stuff and leave out a bunch of very related things so I encourage everyone here who hopefully feels inspired to go to Rob Norris's talk tomorrow at 11:14 functional programming with effects we coordinated a bit this year on our talk so I was supposed to lay the groundwork hopefully I did a non terrible job of doing that and so you guys can go into his talk with this background and he'll sort of tell you how do you like what the next steps are if you want to learn even more sort of on your own outside this conference I encourage you to buy this book called functional programming of skull by rune artisan and apologize I know it's often when finally referred to as a red book buy it do two exercises internalized it it's a really good book not just for functional programming in Scala but just functional programming in general some stuff I didn't have time to cover that are that's tangentially related is I mentioned all the effects I've been talking about sort of track very general things like the general notion of state or the general notion of failure if you want to track more even more specific things like I want in fact wherever I make a database access or I want to track wherever I make a network Hall there's techniques to do to do that sort of like some Google terms finally Otago is free mode ads and sort of a thing that I've been getting into that I want to be doing pushing people is think about functional programming in code but also think about how you can apply it outside of code as well how can you apply it to like larger scale systems so some examples of this will be Nick's or Nick's OS so Nick's is a package manager that works across operating systems that applies functional programming principles to package management and if they have an operating system built around it and this is not like a toy project that like some person is like implementing out of the basement like people like at Target we're using Nick's there's a lot of companies are using the X and people run Nick's OS as like their main distribution so stepping a very real project and interesting if only for the applications of functional programming to something that's not traditionally traditionally functional programming related there's been some hype around reproducible builds and you will infrastructure are reproducible environments these are all sort of applications of functional programming ideas to larger scale systems and one more talked I encourage people to go see is a talk on Nelson which will be on Saturday and 9:50 a.m. by Tim parrot and that's essentially an application of functional programming ideas to automated service deployment so applying ideas from like immutable data structures to how you automatically deploy systems and that's all I had for you guys today [Applause]