A Tour of Functional Type Classes via Sc...

SBTB 2015: Michael Pilquist, A Tour of Functional Type Classes via Scodec and Simulacrum

Recording: SBTB 2015: Michael Pilquist, A Tour of Functional Type Classes via Scodec and Simulacrum

Thanks I'm a little shorter than Jason so thanks for coming to my talk I have a lot of material to cover today I want to cover three different topics I want to cover an open source project called s codec another one called simulacrum and I also want to look at a lot of the functional structures that are prevalent in functional programming in Scala and what I mean by functional structures are like type classes and data structures maybe some techniques and patterns as well and we'll see those throughout the talk as far as an agenda today I'm gonna use s codec as the grounding point throughout the talk and will actually tour through various type classes you know we'll start with functors and monads things people are familiar with and we'll move into some at the very least like experimental territory some things that come up in s codec and also come up in some other libraries but you know aren't like well-known in functional programming literature I got one slide about me you know I've been working with Scala professionally since 2008 you know I work for a joint venture between Comcast and Aris group we build conditional access software and control systems for managing digital set-top boxes we also do a lot of stuff with like head end equipment and video feed equipment that deals with sending like MPEG transport streams to devices I do want to call out that I'm not a Haskell earth by Nature and so if there's one thing you take away from this talk is that a functional program in Scala is absolutely a valid and useful technique to apply even if you're not familiar with Haskell not that there's anything wrong with Haskell but uh you know I am NOT trying to implement Haskell in Scala so I want to start with a brief introduction to s codec and so nothing's ever easy to explain s codec is not just a library but rather is a suite of libraries and it's split in two I'd say two different categories there's the primary libraries made up that's codec bits core and stream and then a set of Interop or secondary modules that provide integrations between other libraries in the functional ecosystem so for example if you're doing a lot of work with unsigned types from spire there's some s coda expire integration there's currently as codex ecology integration and there will soon be as codec katz integration they'll probably soon be in s codec akka integration for reactive streams and there's some you know streaming support in the way of the scholars estream project I am gonna spend most the time today in this s codec core library because we're the the core data structures come up so Escada core can basically be approximated by this single slide we have two really primary data types the first is this encoder abstraction so an encoder is a trait that's prized by a single type parameter a and what it does is encodes a value of type a to a bit vector and so a bit vector is a you know persistence data structure immutable you know sequence of bits and it's designed to be really really fast for the types of access patterns that is common when working with binary data you know this morning in the keynote we heard about how every library defines their own you know either/or based data structure so as codec does that as well and we have this attempt based data structure it's very similar to like scholars try but we're try renting as a throwable attempt represents failure with a domain-specific data type called error you know it's also similar like skylersays disjunctions Galactic's or Katz's X or similar idea encoders also have a size bound and we're not going to really look at that today you'll see the size bounds throughout the slides as we look at various encoders size bounces they just tell you you know a minimum maximum size that could ever be generated in it you know a generative impactor the size that could be for any given value of typing we also have decoders so decoders just do the inverse right given a bit vector we want to attempt to decode it and this is where things look a little bit different from like a normal serialization framework because what we get back is not just an attempted decoded value but rather we get back this pair this decode result that has the value that was decoded and also has some remainder and this remainder is like any unconsumed bits that the client might want to do something else with so a good example is if you have like a you know 100 bit bit vector and you have to decode a 32-bit integer out of it you know you would consume those 32 bits and return the result in the remainder and then of course we can mix those two together and we get the primary data type of us codec which is just called codec one other thing to point out here is that unlike a lot of serialization frameworks the encoder type it doesn't return an attempt it's defined partially over the possible inputs of type a a lot of times you'll see see relation frameworks to find that totally right to say that encoders can always encode to a value and just can you know and can't when they decode that they'll be defined partially with us codec we didn't want to like force dealing with numeric types like integers and and unsigned integers we didn't want to force the size limitations of those fields into the type system like we knew how to we certainly could have had a type tag or some type of value class that represented like an integer bounded between you know one and 8191 and then defined encoders for it but with Eze codec it was an intentional design decision that we would rather represent that as like an encoder type int and then I'll while this encode to fail with an error and you'll see some uses of that coming up so I'm going to do a couple examples of using s codec and then we'll get started with our functional structures so just starting very simple we have three case classes here you know point made up of two integers alignment up with two points and an arrangement made up of a collection of lines and of course we can instantiate that and store it into this ARR value and one of the most common use cases for serialization frameworks at least is to auto-generate some binary format that lets serialize these things these case classes without any input from the operator so s codec absolutely supports that we can import this s codec codec implicit SPAC egde and if we do that we can immediately begin encoding our arrangement datatype you know here we call this require method the require method is sort of like calling get on an option so like it's really great for our slides and it's really great for working in the repple it's not so great for production code it will throw with like a very descriptive error message if something you know fails but if it doesn't fail you know it just unwraps the attempt and gives us back a single value so of course you know with with zero code being written only in putting this one import we can encode our arrangement type into this 288 bit bit vector similarly we can decode this bit vector and get back our arrangement type frame so and this is sort of like the the lowest bar we can put in place for a serialization framework we can control you know how any individual component in our case classes are serialized by playing games with implicit scope so instead of importing the entire implicit SPAC äj-- if we imported everything but like this implicit in codec and then defined a different codec event in implicit scope here's ones that encodes into an 8-bit unsigned integer field then when we encode our arrangement we end up with something is only 72 bits large and we know it's a little bit different here's when we go to encode this other arrangement value one that has a negative one in the last position there we get at this you know very descriptive error message saying that negative 1 is less than the minimum value 0 for an unsigned 8-bit integer and it includes like this path through the data structure you know saying starting at the arrangement go to the lines property from there go into the first index of the vector you know and so on navigate its way through that structure and tell you exactly where the error occurs so this automatic derivation support is all powered by shapeless and it's and you know it's MIT's magical stuff shapeless is is a wonderful library for supporting this type of derivation but this really has nothing to do with like why as Kodak came about right if you don't care about your binary format there are wonderful serialization tools you know that you can use that are very fast or very performant you know all sorts of different types that you could select what s codec is really about is dealing with these explicit codecs so you've got some binary format that's like defined by a standards body like in my world I deal a lot with mpeg-2 transport streams so I'm going to work a lot with data types that are predefined maybe our you know 20 25 years old and I need to worry about the position of each and every single bit in a data structure and so we wanted a very compositional based library that lets us build these codecs in a way that um you know it you know keeps the encoding and decoding logic together and lets us work very algebraically with the resulting data types so here's a very simple example there's this data type that appears in the MPEG world a lot called a packet identifier or a pid' it's really just an integer that's bounded by 0 and 8191 we can define an implicit codec for it and its companion object and we would do that by using like this you int method that comes from s codec that gives us a backup codec that can handle an arbitrary number of bits we'll say give us a 13 bit integer and then we have two different options we can use like this X map operation and basically give it two functions a function that converts from an integer to our data type bid just by wrapping the integer with our constructor for our Pig class as well as you know the inverse of that you know unwrapping a pit back into an integer and if we do that you know we've successfully transformed our codec of integer into a codec of pid' and you know I did want to point out we're going to look at X map quite a bit today but you know an example this simple typically would be written you know in the syntax here in the second way where we just called the as method and you know basically ask the compiler to figure out a compile time using shapeless how it can go about X mapping and integer into a pit in an automatic way of course in this case it's easy because there's only one field in our case class but if we move forward and look at some more complicated case classes that same syntax will still work so you know here's another very common data type that appears in the MPEG world you know it's a transport stream header from like an mpeg-2 transport stream the values here aren't particularly important it's just set of boolean x' and a few integer field some of the integer fields are wrapped in case classes and this is what a more typical codec definition would look like maybe not quite production quality but at least pretty close you know here we have effectively we laid out this codec to kind of mirror the definition of this data type in the you know the ISO specification that defines the MPEG transport stream header we've got there's this table or in the left hand side of the name of each field on the right hand side we have some data type description of what it looks like this is not a DSL or at least it's not a DSL in the sense of like an external DSL that's getting compiled into Scala code everything you see on the right-hand side and those data columns they're really all just codecs putting a string pipe and then another codec really just adds error information to a codec and returns as a codec all right so everything on the slide there's there's probably I don't know a few dozen codecs being instantiated the first time this implicit vowel is is computed and then cached in the companion and then of course when we finish we blow up all of these individual fields we just say convert this to a transport stream header and that binding of all of these individual fields into that case class all that's happening at compile time so at runtime there is zero reflection you know and certainly no significant overhead there's some shapeless stuff going on here too but that's an entirely different talk the last example I want to get from s codec is just one more data type building on this transport stream header data type and I don't really need to go into a lot of detail on this one but basically there's other more sophisticated transform operations besides our X map transform in this case our case class is really simple right we've got a header and two optional fields and the existence of those optional fields is going to be dictated by some value in our header and so like the Kodak here is using some flat prepend operator you know whatever that does it's using some additional Combinator's like this conditional one to bring in optional fields so you know don't worry about what those exactly do just the idea that there's a lot of very sophisticated transform operations available on this codec datatype so what I want to talk about today is looking at encoders and decoders and codecs and really studying this core algebra of the library and what would the talk about or what the talk is about today is how we can get inspiration from these very basic type signatures with a little bit of knowledge from functional type classes and use that knowledge to help build a bigger and better library to help discover new Combinator's in the library ok so let's start with decoders the first transform we'll do with the decoder is just a simple map operation the the same map operation we're used to from you know lists or options or any other type constructor you know our map operation will be defined directly on our decoder train I'll take a function for me to be and return a decoder of type B so this is a little bit different than like defining map on a collection all right when we need to find my frontal collection we have a value or some set of values of a given type and we map the function over it we apply that function to you know with each value in the collection yielding some new collection here we're like deferring application of this function until the decode actually occurs it's like the the implementation of map one decoder says at some point in the future when someone actually calls our decode function decode with the original decoder of a get that attempted bit back or to attempted to code result back and then map over that reach inside the decode result and map our function over the decoded value and that you know this comes up all the time with when working with decoders here's a very simple use case and we'll see this one a lot today but we have a decoder of a pair of two integers we just map over it D structure the tuple into X and y and then construct our point and so how many people are familiar with like this type of encoding of functors okay good so even if you're familiar with it you know there is a little bit of a twist here in that we're using simulacrum simulacra is a macro annotation based code generator it runs at compile time and it's built on top of the macro paradise compiler plugin and basically what it does is generates a whole ton of boilerplate on top of this functor definition and it does it at compile time when the functor trait is compiled so because like functors annotated with that with the @ type class annotation we basically get things like an implicit summoning method in the companion object so we can say like give me a functor of list and as long as there's one an implicit scope will be returned to us most importantly we get like oo style extension methods so if we have some value of type F of a and we have an implicit function of F available automatically we can call all these methods in like an infix format and there's a bunch of other more advanced things that provides us but but the you know extension methods are the big one and we'll see plenty of examples of simulacra as we go through the talk today so when we look at the definition of functor we want to say that in order to have a valid instance of this functor trait any implementation must behave a certain way and we're going to constrain that behavior by a set of laws the you know the function laws we have to an identity law on a composition law and they're they're pretty straightforward to describe in text the identity law we just say that if we map the identity function over a given f of a we better get back what we started with and the composition law just says given two functions week either map first the first function then the second function you know or we can compose our two functions together and map the result over our F of a and we'll get back the same value and so what I want to look at today is how can we represent these laws of our functor class in code and when I was first talking to someone about this they said well why would I want to I mean that that first version seemed okay seems pretty straightforward and you know this is my answer to that I mean so obviously we have an automated testing perspective right we want to be able to say that anybody that provides an instance of the functor trait for their type constructor F we want to validate that their instance actually adheres to these laws and it's important that if they were to cheat if we had an instance of that trait that compiled but the you know implementation didn't here - every law we have a potential break in referential transparency so when we have a lawful functor instance we'll be able to do all sorts of things like compose functors together or you know work very algebraically with code in a you know based off of referential transparency and if our walls are broken some of our substitutions that we can do algebraically will actually end up introducing errors into our program so it's very important that we want our laws to be adhere to but we also want a way that we can represent those laws in a very evident and straightforward way and the functor laws are pretty straightforward to describe in text but as we move on there's some other laws for some of the other type classes we'll look at that are quite you know complicated so having an unambiguous and precise definition of those laws is a big benefit not only for you know us as we're writing it to make sure we don't transcribe the law and correctly from you know the some piece of literature but also for people reading about we're trying to learn about what a functor is or some type class does because it's very straightforward once it's encoded in the type system however if we want our laws to be encoded in a way that facilitates learning's facilitates understanding of what the type Clause does we can embed them inside of like a test framework so like I love Scala check and I love Scala tests on Web specs too and I just want to use those frameworks to actually test my instances but I want my lols separated you know I wanted them once removed from the actual test code so when we look at these laws we're not seeing a bunch of test machinery we can just see the real definition of the law itself so this is how I want to represent laws today and I want to start with saying that that this representation is is more or less the same representation used in the cats codebase and so it's absolutely from like the cats community like this is not in every line here is not something I came up with but here's how we're gonna do it we'll have a mirror tree so we have the functor trait defining the type class will have this functor lawls trait that's it finds all of behaviors of the abstract operations it'll have a implicit type class instance so whatever our type class under test is we'll define as an implicit Val and then we're going to use this piece of simulacrum generated magic - we'll say import functor ops on underscore and that's going to let us call any of the methods on our type class in an infix style so because of that let's look at the function identity law because of this functor opstat underscore import we're able to say given some arbitrary f of a call map on it like we know nothing about F short of the fact that F has an implicit function stencil right so normally we wouldn't be able to call a map function on some arbitrary value of type F of a but simulacrum provides us some extension methods here so we can do that and the functor identity law ends up being pretty straightforward to represent we can say that you know mapping identity function over an f of a is equal to an F of a but we're not actually using object equality and this is really really important because most well at least many of the functor instances we're gonna generate do not and cannot have like well-behaved object equality anytime we have like it like decoder for instance any time we have a func - that's in some way suspending a computation we're not going to be able to define object equality so we want some way to have like this notion of like deferred equivalence I want to return basically this fancy pair of a left-hand side in the right-hand side we call this fancy pair is equivalent and later on whoever calls this law let's say in a test framework or somewhere integrated with Scala check we can actually do the comparison and then report if the values don't match so this fancy pair is you know pretty straightforward it's just a case class by a single type and requires the the left and right to be the exact same type and then on this fancy pair we can define this is equivalent method and the is equivalent method we'll say I can compare the left hand side and the right hand side for equality I can say is LHS and RHS equal to each other according to some equivalence relationship and we can represent that equivalence relationship with another type class and and this this equivalence relationship I'm not going to show the laws for it but it's the same laws we know and love from like object equals write symmetry reflexivity and transitivity but here with simulacra we can define it pretty straightforwardly we're using another feature of simulacrum the Aufbau notation which basically generates like an infix alias so now we can say things like one triple equals one every framework in addition to defining their own either type also defines the triple equals operation right okay so let's move on to another transform what is the you know we saw map on decoder what do we get if we try to flatten off decoders we know what we get if we try to flatten math like an option or a list but what would it mean to try to flood off a decoder what does that give us so let's first just define the flat my signature will define it as a method on the decoder trait it'll take a function from a to decoder of B and return a decoder of B so the signature is pretty straightforward and we heard earlier in one of the previous talks about how like monads are really for modeling dependencies between values right and that's exactly what use it for with decoders we say anytime we've got some field who or some bit pattern that the way in which we decode that bit pattern depends on a previous value in the in the bit string we're going to need to flat map or at least some some form of a monadic operation in order to access the decoded value so in this example here we have like this unsigned integer field that's four bits and when we decode that four bit value we get the value to decoded and now with that value two we're going to limit the amount of structure limit the number of bits that the next decoder can see of the remainder to be just 16 bits and that's using like this fixed size bytes Combinator the fixed fixed size bytes Combinator just limits that remainder and then takes that many bits and feeds it into whatever codec we give it we're giving it this utf-8 thing so basically we end up decoding the next 16 bits as a utf-8 string we get the string okay out and then we end up with you know everything post that that two bytes out is the remainder okay so flatmap the important part is the fact that we get this dependency relationship I do want to think I look at the way flattened up is implemented you know the general notion here we're gonna return a new decoder of type B and we're first gonna decode with our original decoder BAE that's going to give us you know we're gonna use a for comprehension and the generator here each generator is returning an attempt so basically the first error is fail fast and we'll exit with that error but assuming nothing fails we'll get all the way through this generator sequence rank so anyway the the first thing we decode is with the original decoder that gives us an a result and remembering a result gives us both a value and a remainder so then we take the the a result value and apply our function that gives us a decoder back of type B and then with that decoder of type B we can decode the remainder from the initial decode operation yielding the B result I'm so at least pictorially it looks like that as we pass bits through this operation and if we abstract over this notion of flat mapping and add this pure definition we end up with the definition of a Mona type class I sort of promised myself I would never put a monad definition on the slide so I apologize but but you know there is a couple things here that are interesting one is that we're going to model the relationship between monad and functor through inheritance and you know there are certainly other ways to model the relationship between modes and functors we heard earlier today that like every monad gives rise to a functor and we see it here on the slide the way we do that is implementing math in terms of flatten up and pure and in fact you know if we if our Moana definitions of pure and flatmap adhere to our Monad laws but we'll see in a second then necessarily this map operation as implemented this way will adhere to the functor laws through some equality proofs but you know there certainly other ways to model these dependencies to model the fact that every Moana gives rise to a functor that don't depend on inheritance as of right now I would think I would say that the functional programming community in Scala you know if I could if I could dare to speak for the community I would say the community has kind of coalesced on this type of pattern because it works best with implicit resolution but that's not to say that like investigating other techniques isn't a useful exercise or that someone will invent something tomorrow that that proves to be a more useful way to represent this type cross relationship this is this is the we're gonna see a lot more lols for type classes these are the Monad laws as implemented in this framework and we're also going to use inheritance here to model the relationship between emotive walls in the functor laws and you know so we have three laws we have an associate ivities all and then two identity laws a left and right identity this is the last set of laws that we're going to look at and even this much detail the rest of the walls we pull up I'm going to move through really quickly because their definitions themselves aren't really the important point I'm more talking about the structure of the way we're relating these things together but you know you can see like they're all defined in a pretty straightforward way our flat map associativity given an F of a and then two functions innate F of B and a B to F of C we came through flat map each function or we can rearrange the parenthesis a bit and either way we have to get the same result so given this mouna definition how could we'd write a monad instance for our decoder type constructor we've already implemented flat map right that's how we started so we can of course just delegate to the flat map method on the decoder trait for that particular but the pure operation is kind of interesting the pure operation were just given a value of type a and we need to turn that into a decoder that decodes you know values of type a so how can we do that and it is something pretty straightforward although it's you know maybe not obvious when you go to sit down and work this out the general idea is that the decoder that we returned will always return success and it will always ignore the incoming bit pattern and just return it completely as its remainder and then for the value would always just return whatever value was given to it so you know if that makes sense as to why that's a valid monad great if it doesn't don't worry about it I you know to validate that this is really a monad it's probably best to run this implementation through like Scala check and run it through our laws and validate that like this implementation of pure adheres to all the walls when paired with the implication of flat map we wrote a few minutes ago and you know and in fact it does so this this is the canonical monad decoder another thing we can do with these type classes though assuming that we have in implementations of them of the abstract operations that are lawful is that we can write these derived methods so you know again we still flatten earlier today but I have some FF obey I can flatten it into an F of a but just by flat mapping the identity function over it and like this is cool I use this all the time with like options and lists you know I I can't say I run into this with binary decoding all right I could give you some contrived example where I have a decoder of a decoder of a but it's just not a pattern I run into very frequently now if I did great I know that I have a monad for decoder so I know that automatically I can a flatten a decoder decoder of a into a single one but it's just not a particularly motivating example for me so let's look at a different derived operations on decoders here's a monadic version of an if statement or an if expression right so normal if expression we'd say like if some guard that's of type boolean then evaluate some expression of type a else evaluate some expression of type a and our monadic version of that is basically just going to stick a type constructor on each of those three positions so rather than saying like if a boolean then al say we're gonna say if some F of boolean then an F of a else an F of a and you know it's really trivial to implement this in terms of flat map we'll just flat map over our F of boolean and then just you know implement it using a regular if-then-else so what does that have anything to do with working with binary I'll take let's take a look at this example here we have two decoders the first decodes a single bit from a bit vector you know if it's a zero bit it returns false and if it's a one bit it returns true we also have another decoder that decodes an 8-bit unsigned integer and if we use this bull decoder as the guard to our monadic if methan and then in the true position we use our u + 8 but we map over the result of u + 8 and we map this sum constructor and then in the false branch we'll just use our pure method we just wrote on the decoder monad and return none then what we actually get back is a decoder of you know a decoder that can decode an optional integer where the first bit determines whether or not the subsequent bits are processed or not so if the first bit is 0 then we immediately return a none and give the entire remainder to the caller and if the first bits 1 you know we decode the next 8 bits and because we have this lawful monad we can work with these things algebraically right we can just put values just put a sign like name aliases two sub expressions so we can take this definition we just wrote and just pull out and generalize it to now be a very useful Combinator that we can use all through our library so here we just pulled out like the bull and the UN eight decoders into parameters and now we have this very nice Combinator called optional which now can just be fed to individual decoders and it gives you back a decoder of option okay so this is like a very common design pattern we see when like designing the library where we're inspired by some monadic operation or some operation from a type class and we find end up finding some very practical implication of it or use case for it in the domain that we're working with him let's take a look at a flat map again though so specifically I want to look at this threading aspect not threading in the sense of like concurrency but threading in the sense of the fact that we like to start with this input bit vector we get this result back and we feed like some remainder which is another bit vector into the next thing it feels like we're weaving bit vectors throughout this flat map call and if we look really closely at the type signature here of our method we can perform some progressive bits of abstraction and say like first let's replace let's inline our definition of our decode result tuple or a case class so we're inside the code result is really just a named tuples let's just forget about the name for a moment and inline a tuple definition the next thing I want to do is forget about the name decode let's just erase that we're gonna lift this method into a function and just say you know we'll look at the code as a function from bit vector to an attempt of durnais the next thing I want to do is generalize the name I want to Elias bit vector to just the letter s so I've done is replaced bit vector with us and finally I want to replace the name attempt with the letter F and what I'm left with is this signature s to F of s a and here's where you need a bit of a leap but you can basically say that you know there's this something familiar here about this type signature and basically it ends up being the state T monad transformer and I'm not going to get into like a whole big definition of the state monad transformer but it literally lets us sequence comp functions of this exact signature or if we want to handle various trampolining scenarios it's a slightly more complicated signature but nonetheless we can sequence functions with the signature using state T so in this case like we wouldn't have to re-implement flat map for decoder we could just look at a decoder a sort of a specialized state T monad transformer a state T Mona transformer where we fix the parameters to the type classic with certain things so we're gonna fix the type constructor F to the attempt type constructor and we're gonna fix the state type two-bit vector so what does that tell us well it's like we've discovered something about the heart of a decoder that a decoder really is this domain-specific fail-fast state monad that's all it really is right and like that's like a really kind of deep meaning that this isn't like some arbitrary coincidence we found but like decoder really is that and so I say you know domain-specific right we fixed the type fail fast we break out on the first error we encounter and the and I say state monad because we get this sequencing behavior where we can compose or flatmap together multiple of these decoders to yield a larger decoder so that's cool but why do we care right there's like an intellectual curiosity that's sort of neat but why was why would this help us build a better library and one reason is because the state monad if anyone is familiar with it has a bunch of really useful constructors that lets you work sort of like imperative lis inside of a monadic context so we like this get constructor that lets us like reach in and pull out whatever the current remainder is right whatever that current bit vector is and look at it we can replace it with a different remainder and we can modify it and so with you know if we have this these get set and modify constructors in the decoder companion object we can write code like this now I'm not going to go through the all the details of this but this is more of a semi close to production version of a codec that deals with bit patterns that are delimited by ASCII quotes so it's a bit vector that starts with an ASCII or you know let's say a hex pattern of 0 X 22 and then there's some number of bits until there's another full bite on a byte boundary that's equal to 0 X 22 and then in between whatever bit like two rows in between gets decoded with a specific codec and so if we didn't have these state monad constructors you know we could just fall back and write decode in like an imperative style but because we have them we can actually compute the entire decoding logic in a single for comprehension I'm sorry able to like reach in and then replace the remainder and so let's move on to our next type class how many people are familiar with applicative functors okay good lots of people so cool you know I say here applicative functors are weaker than monads and stronger than functors I say that because there are many more data types that we could write valid lawful applicative instances for then we could write like lawful moanin instances for the the Monad laws are much stronger than our applicative laws or another way to put that is that an applicative is a generalization of a monad right that if we look at a monad and take away some of the required structure that that's required by the laws we end up with something that's a little more general we have this applicative functor so you know the applicator function longer definition will define the to abstract operations pure an app and apps gonna look just like map except our second argument rather than just being a function from A to B it's going to be a function form A to B that's inside our F type constructor and then you know we're gonna make applicative extend functor will define map in terms of pure an app and then similarly we can redefine monad now to extend applicative instead of extending functor and we can define app in terms of pure well map and flatmap you know one of the things that has always bugged me about applicatives is that i kind of have a hard time wrapping my head around this second argument like certainly I've seen examples where like I just magically have like this F of A to B in some context but I can tell you I've never run into a case in s codec where I have like a decoder of a function for me to be I can certainly contrive one but I find it a little irregular and there's a bunch of laws for applicative functors I'm I promise we won't look at these but just their names we have an identity law composition homomorphism at an interchange law these are complicated you know these look a lot nicer and like a point freestyle written in Haskell but when we write it all out in Scala you know they get complicated and so I and I find this particularly irregular like I really I think there's some missing beauty here too applicative functors so I want to look at them from a different angle I want to look at something called lacks monoidal functors and I'm not gonna like talk about like why we call them lacks my little functors all elack's my nodal functor is is a type class that extends functor and defines two operations pure and Zipp pure is going to have the exact same signature as before and zip is pretty straightforward we have an F of a and an F of B and we're just going to put them together and get back an F of a B now unlike applicative functors here we have three abstract operations with applicative functions we had two with my nodal functors we cannot write math in terms of pure and zip so there's something interesting about that you know applicator punchers go ahead - let's look at the lols for laxman total functors well there's a certain beauty here I think there's at least some type of relationship of these my noodle walls to our Monad laws we have a left and right identity law and we have an associative attea so these feel much more straightforward and if we actually like work through what these laws were doing I personally find these much more satisfying or at least easier to understand and the implicative functor laws and in fact like if we start tracing through like why is this thing called a lacks modal functor and like what's its relationship to it like the Montoya type class we would see that like these actually show of a strong correspondence to the modeling laws which are also going to be represented with two identities and an associate ivities well and so one neat thing with this representation is that every lacks manola functor gives rise to an applicative functor right so if we have a lawful monoidal we can convert it to an applicative and vice versa right if we have a lawful applicative we can convert it to a my knodel so we know with decoders now in s codec we have lawful monoidal right I mean we know that because we start with a lawful monette instance from the MOE dad and we can convert that to an applicative just by you know type description and then we can call this to monoidal method to now get a lawful monoidal instance for decoders so again like what's the point well this ends up being the primary operation for decoders and we're gonna see an analog to it in a few minutes for codex that is the primary operation in all the library and you know people probably heard like before when doing text parsing or like looking at you know any type of parsing Combinator library that like you know partials or placated functors write in the same way like decoders are applicative functors but i think this ends up being a lot easier to motivate from an example point of view i have like two decoders in this case i like two 8-bit unsigned integers i can just zip them together now i've got like that same tuple type we had earlier and I could just map over that to construct a point so we've filled in like the question marks from earlier where we just somehow magically had a decoder of a pair of integers now we have to have a way to construct those decoders of pairs managers without writing it manually I would be remiss in not mentioning that you know we didn't look at any of the derived operations on applicatives and that was on purpose because they're really complicated right like I find that app method to be somewhat mind-bending to work with at times and but anyway if you have one person go through and define all the derived operations they end up being very straightforward to use so the same example can be you know implemented with an implicit of just via the map to operation but that's relying on someone actually implementing map two for you right okay so let's look at encoders encoders remember remember they encode a value of a to an attempted bit vector and the first thing I want to do with them is try to map over them and we can't map directly like we can't map a function from A to B and it's the reason why is tied up in like the fact that the you know type parameter here's contravariant there's a really interesting kind of deep lesson there you know it's some relationship or correspondence between contravariance and and the ability to map or contra map but we can implement this transform operation contra map that takes a function that goes in the reverse direction right so instead of a function from A to B an encoder has a contra bat method that takes a function from B to a and so like when you think about that abstractly like how given some some F of a and a function from B to a how could I ever get back an F of B like I find that to be kind of a strange concept but in the concrete its ends up being straightforward if we look at the definition here of contra map we're just saying that this return to encoder when it goes to encode a value of type B its first just going to convert that B back to an a using this function that was given to us and now that we have an a we can just encode with the original encoder that we started with right and you know in fact the the example is the same exact example as before we have an encoder of a tuple and we want to turn it into an encoder of a point we have to give it this inverse function you know the function from point back to a tuple like functors we can map over we can abstract over this ability to contra map and lift it into a type class so this is the contravariant version of the covariant functor that we looked at a minute ago the identity and composition laws basically look you know identical except that we've replaced every occurrence of map with an occurrence of contra map and we replaced the functions that are being passed to each of the laws well into the composition law with similar functions just with the arrow reversed instead of A to B we have a B to a instead of a B to C we have a C to B and there's lots of neat contravariant functors so like our equivalence relationship we looked at earlier as a contravariant functor you know like Scala math ordering if you've ever used like ordering to sort a list or something that has a contra contravariant functor and in fact like the method exists on ordering it's just not called contra map I think it's called on or something like that and like spires partial order we could define a contra variant functor for even function one is a contravariant functor whose implementation is just a you know it's just function composition which is kind of a neat trick we can fix the output type and then contour map over the input parameter okay so finally if we put all these things together we end up with a codec and a codec really is just you know the merging of an encoder and decoder into a single type you know I'll warn you like that this part of the talk is where we get into some stuff that's like not from literature it's stuff that we've kind of found by looking at the way these things work in s codec and one of the comments I got when I first started talking about these type classes we're going to look at is that like oh I'll just you know separate a codec into an encoder and a decoder and then you've got all the literature support you need it's like yeah but that's not the point right the point is like if I don't want to separate them if I come in from a design goal I want an encoder and decoder to always be paired how far can we take that how far can we keep that binding between those two concepts and still yet get this type class support so the equivalent of mapping we already saw when we had codecs remember we X mapped right and we when we X map when we first started the talk we had that like pit data structure and we said in order to convert an integer to a pit we're going to provide both directions like a full lie similar fizzell between an integer and a pit and it's you know pretty trivial to implement we'll just take two functions A to B and B to a we'll use the inverse function and encode we'll use the forward Direction function and decode and so just like we you know with functors and contravariant functors we can abstract over this ability and we end up with this invariant type class instance so here we have this notion of invariant functors sometimes in literature they're called exponential function tout I was I jumped the gun a little but these are in literature it's the next set that aren't in literature but but anyway invariant functors we can define the walls in a very straightforward manner as well they're basically the same walls as functors and contravariant functors we just now have twice the number of function parameters you know in every place we had a map before we don't have an X math we pass both like the forward direction and the inverse okay so we end up with like this lattice if I wanted to sound like a P geek and if I wanted to sound like an O person I'd say like a class diagram right but I have this like this relationship now from like Ivan variant functors we can actually show that invariant functors or like covariant and contravariant functors each give rise to invariant functors that just ignore the type or the the function argument they don't need you know so a functor gives rise to an invariant functor that just ignores the contravariant parameter and we got this interesting kind of relationship between applicative ism and my noida less we talked about before so this seems promising when we looked at decoders we were able to find a lot of power in this notion of applicatives and my noddles is there something interesting we can do with codecs and their zip logic and so here like I don't call it zip we call it pair with but the notion of pair width is basically that we're going to take two independent codecs remember so a codec we're going to remember how to encode things and we're going to zip them together into a codec of a tuple the encode logic is really straightforward it's just you know it's sort of like an applicative encode sort of we're going to encode each of the two values and the tuples independently will encode the first element of the tuple with the original code Okabe will decode the second element of the to a pole with the codec of b and then we just concatenate those bit vectors together assuming that they both passed right that they both succeeded and then decoding is the you know the literal flat map that we were using earlier it just takes the bit vector first decodes out an A then decodes back out of B and then returns the tuple so if we look at just the type signature of this function we have something that looks very much like our zip operation from the my nodal type class and if we were to abstract over the ability to zip these things together what we end up with is this and so this is a name that I sort of made up you know the notion of an invariant monoidal but basically rather than pairing our pure and zip operation with a map function like a my nodal functor does we're gonna pair our pure and zip operation with our snap function and you know to encode that we're just gonna say pure and zip extend from invariant functor rather than regular functor the covariant one the lols end up being very straightforward again we're not gonna look at the details but it's a left and right identity even associativity law so there's some nice symmetry here and we can even go a little bit further and pull out a type class that sits above my noida functors and invariant my nodal functors and just pull out pure and zip now we can only do this if we can define a set of laws that constrain the behaviors of pure and zip if I can't define laws for appearance's if then this is just like ad hoc polymorphism and it's sort of useless right so how could we define laws for this zip well there is a left identity and a right identity law and there's an associate to any law but the framework that we put together today can't quite express them right because we end up with these weird shapes like if we were to look at left identity we'd end up with on the left-hand side of our equals or our pairing operation we get this like f of some tuple unit a and on the right hand side we get like an F of a and now we want to say like is there some ways some morphism or some some some equivalence relationship let's say between these two values such that we can say that they're semantically equal and we are our type type class testing law testing framework didn't quite capture the ability to do that but we certainly could extend it to do so and this ends up being a perfectly legitimate type class to exist so this is kind of interesting because this zip type class actually has laws which you know not has there have been attempts to write zip type classes before without laws and you know this is a kind of interesting result ok so for the last topic I want to look at how we can flatmap now that's sort of the last piece when we start working with code X we saw that we needed a flat map to handle this dependency relationship where we want to say like some fields later or depending on an earlier field so how can we go about flat mapping if we have code X now we know we can't write a monad instance we you know we know we can't read omona because we weren't even able to write a regular map function and so if we don't have a monad like what can we get instead and so basically this signature we can come up with by like just kind of looking at the types of things we're doing with flatmap like when we looked back at this previous example here we said okay well we were reading a size field and then using that size field to figure out how many more bytes to read into the next field and so just by studying that we can say that like well in that particular example when we're decoding we're going to use the decoded value to figure out how to decode what comes next but when we're encoding the value that's written in that first field is actually computed from what comes after write that that number two was was the size of the string that came after and so we can write this method called consume which in addition to the ada codec B is going to take a parameter B to a and in you know we'll end up returning a codec of B and here's how we might use that to implement the same example we implemented with flatmap one decoder you know the forward Direction is the same as we saw before with flat map we're going to you know decode the size then use fixed sized bytes to limit how much the utf-8 codec sees in the reverse direction we're just going to take the string that's handed to us and compute the number of bytes needed to store this string and like I kind of waved my hands here at the number is four if you have to compute the number of bytes to store a you know a string and you might as well just encode the string so um you know if we use ASCII though that problem goes away right we know we can just count the number of characters in the string and this pattern shows up a lot I don't have time to go through this example in detail but the canonical example of consume is a pattern that shows up in binary protocols where you've got like a byte that sits in front of everything and it's got a bunch of bit flags in it and if a flag is 0 it corresponds to an optional field not existing in the you know subsequent remainder and if the flag is 1 in the field does exist and so if we put all of these bit fields together and then we have all the optional fields you know all the ones that the bits are set to high occurring in order and it turns out that that type of pattern is you know relatively trivial to to implement if have this consume operation so like this this code here like I said it's a little more complicated than I want to get into right now but nonetheless it handles that case and it does not duplicate any information in like the domain model the the values or the types that are being returned from the codec so like nowhere here do we have a case that is possible to represent in Scala but is not possible represent in binary you know there's a complete one-to-one correspondence between our type and our binary here you know if we looked at this a little bit differently or came with this from a little bit different use case we end up with this thing called flat zip and so a flat tip does is says that like I can't compute this inverse operation or at least it'd be very difficult for me to compute this inverse this B to a so instead we're not going to require that we'll just we'll just ask for the same thing that flat knife asks for a function from a to codec of B but something's got to give right if we don't have the inverse then I can't give you back a codec of B instead you get back a codec of a tuple a B and you know it ends up being that you can implement flat flat zip in terms of consume or vice versa you know whichever one you pick to be abstract you can implement the other one in terms of but this comes up all the time in binary code X as well and in fact one of the first examples I showed where we had like the MPEG header format and the MPEG header format used like that flat prepend operation flat prepend is actually just another version of flat zip that handles some slightly different structure so anyway it turns out you can abstract over the ability to consume and flat zip the problem with the names consuming flat support they're very specific to the use cases that they came from in s codec and you know if we were to say like we've got this thing called an invariant monad and it's got an operation called consume like that names just a little too evocative of a use case right so here I renamed them to X flat map an X plat map product you know they don't they don't roll off the tongue but nonetheless we can abstract this operation this ability to effectively do depending and calculations on a type constructor that is an invariant functor and even this one even this type class has laws represented as left and right identity and an associative 'ti law so wrapping up we ended up looking at all of these type classes we put them in this sort of hierarchy and so I kind of you know have called this right hand side here at least when I write about these as like these invariant shadows it's like this set of like mirrored type classes that they're mirroring these covariant type classes from the world that we normally work in in an invariant functor world and so anyway the last points I had just wrapping up is that what I think is particularly interesting here is you know not like the definition of lats if we're not the the notion that we got to work with some cool sounding type classes but rather that like practical library design can be informed by working in the concrete and the abstract like we started by working very concretely with like binary and bits like its it says low-level as it gets ran into some problems talk about how do we transform them and we can shift gears and work in the abstract and use that as motivation to like get past the hurdle we're at and eventually gets like a new hurdle and move back to the concrete and you know see how far we can get and I think there's something very powerful about that technique you know the other thing I wanted to mention is that these functional structures are are legitimately useful right like you know again as codec is used for for bits and bytes and for you know building very fast binary conversions for you know messaging with all sorts of different systems and yet like all of these functional programming structures appear throughout the library even though they're not exposed as like surface syntax so anyway that's all I had I do want to thank everybody that reviewed these slides and if you're interested in any of the details there's a bunch of links here both projects as well as various reading any questions yeah so the question was like that you know if there were no examples in the literature if I thought about publishing it you know it's funny I was I was reviewing these type classes with Paul T Asano and I you know I said like does this thing exist I mean it is I just you know inventing something here and he said the same thing I took that feedback and published blog posts publishing in a journal or something would be interesting but I haven't given a lot of thought so yeah I think it's very interesting any other questions sure sure all right thanks everybody for coming