Created
December 27, 2017 02:23
-
-
Save cscalfani/c755f837bd0723c7cbcbb93460bbe360 to your computer and use it in GitHub Desktop.
Revisions
-
cscalfani created this gist
Dec 27, 2017 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,207 @@ # Discovering Applicative Functors in Haskell When first learning Applicatives, they always seemed an oddball thing to me. At first, Functors made sense and Monads sort of made sense, but Applicatives felt shoehorned in between the two. That is until I was reading Programming In Haskell by Graham Hutton, Second Edition (section 12.2) on Applicatives. His explanation takes a bit of a leap and is presented in an odd order, but I think I can reorder the information in such a way that we can feel as if we are discovering Applicative Functors (or Applicatives for short) ourselves. ## Start with Functor Let's remind ourselves of the Functor class definition: ```hs class Functor f where fmap :: (a -> b) -> f a -> f b ``` In order to "discover" Applicatives, we must put `fmap` in the proper context. ## Properties of `fmap` `fmap` takes an ordinary function of 1 paramter and applies it to a structure, i.e. a `Functor`, e.g. a `List`. Two points are important here: 1. Normal function 2. One parameter And when complete, `fmap` gives us a new `Functor`, e.g. a new `List`. One important point here: 1. Result is the exact same `Functor` Now what happens when we want to change some of these properties? ### What if the Result was NOT a Functor or a different Functor? These sorts of mappings are interesting in their own right but don't really move us toward Applicative Functors, so for this exercise, we will ignore them. ### What if the function was NOT normal? What does it mean to be a ***normal*** function? Well, it's just your everyday, run-of-the-mill, function. What does a function that's not normal look like? Here are some: ```hs g :: [a -> b] h :: Maybe (a -> b) ``` The functions are normal but exist in a container, aka a `Functor`. The `g` function exists in the List Functor and `h` function in the Maybe Functor. At least for now, we can consider a ***non-normal*** function as one that is contained in a Functor. #### More than 1 parameter? Looking at the type of `fmap`: ```hs fmap :: (a -> b) -> f a -> f b ``` We can imagine that our function is of type, `a -> b -> c` meaning that we need a different sort of `fmap`, viz. `fmap2`: ```hs fmap2 :: (a -> b -> c) -> f a -> f b -> f c fmap2 g x = ??? ``` Turns out that the definition isn't obvious. Let's start with regular old `fmap` and take our `g` with 2 parameters and see what happens when we combine the two in ***ghci***: ```hs λ> :t fmap g fmap g :: (Functor f) => f b -> f (b -> c) ``` Notice that after applying `g`, we still need 1 more parameter. No surprises here. But the real problem is that once our function has been ***partially applied*** to `fmap`, it's now inside of a Functor. Originally our function was just a ***normal*** function. But now it's not. This is getting hard in the abstract so let's create some concrete examples to help us think. ```hs λ> let g x y = x + y λ> :t g g :: Num a => a -> a -> a λ> :t fmap g [1,2] fmap g [1,2] :: Num a => [a -> a] ``` Okay, so our function is inside the `List` `Functor`. We need a function like `fmap` except it takes a `value` instead of a `function` and applies it to a list of `functions` instead of a list of `values`. Let's call this `rmap` because it sort of the reverse of what `map` does with lists: ```hs λ> :{ rmap _ [] = [] rmap v (f : fs) = f v : rmap v fs :} λ> :t rmap rmap :: t -> [t -> a] -> [a] λ> :t rmap [3,4] $ fmap g [1,2] rmap [3,4] $ fmap g [1,2] :: (Num [a], Num a) => [[a]] ``` Not surprising that `[[a]]` is in the `List` `Functor` twice, once for each mapping. Once from the `fmap` and once from the `rmap`. It's clear that we need something other than `fmap`, but what? #### Something else Let's write the type signature for this magical function that will get us out of this mess. We need something that can deal with functions inside of `Functors`: ```hs somethingElse :: f (a -> b) -> f a -> f b ``` `fmap` is fine for the first parameter but all subsequent parameters will need this function which looks like `fmap` except the function is ***inside*** of the `Functor`. We should make a class for this and formalize it and give it a good name (or at least a better name than `somethingElse`). ## Applicative Let's define `Applicative Functor` or `Applicative` for short: ```hs class Functor f => Applicative a where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b ``` Here, `pure` wraps something in the `Applicative`. We can use this to take a ***normal*** function and make it ***non-normal***. It's sort of like, what we've been calling ***normal*** is called ***pure*** in the context of `Applicatives'. We are saying that the function we pass is `pure` and needs to be wrapped to use as part of the `Applicative`. The operator `<*>` is our magical function that acts like `fmap` also known as `<$>`, except it can handle the function being in the `Functor`. ### Using our new toy Now we can return to our previous example: ```hs λ> let g x y = x + y λ> :t g g :: Num a => a -> a -> a ``` Now we can use it very easily with `<$>`, `<*>` and optionally `pure`: ```hs λ> g <$> [3,4] <*> [10,20] [13,23,14,24] λ> pure g <*> [3,4] <*> [10,20] [13,23,14,24] ``` What's nice about this, compared to the failed `rmap` approach we tried earlier, is that the order of parameters follows the convention of left to right. With `rmap` it did not. ## Other uses Mapping with multiple parameters is great and all, but you can use Applicatives in lots of other scenarios. One that pops to mind from the Haskell Programming from first principles by Christopher Allen and Julie Moronuki is record construction with validating parameters. I've greatly abbreviated their example: ```hs λ> :{ validateLength :: Int -> String -> Maybe String validateLength maxLen s = if (length s) > maxLen then Nothing else Just s mkName :: String -> Maybe String mkName name = validateLength 25 name data Person = Person {name :: String, age :: Int} deriving (Show) :} λ> Person <$> mkName "Joe" <*> pure 20 Just (Person {name = "Joe", age = 20}) λ> pure Person <*> mkName "Joe" <*> pure 20 Just (Person {name = "Joe", age = 20}) ``` Here you construct a `Maybe Person`. A `Just Person` if the parameters are valid or `Nothing` if not. ## Common Pattern The fact that `Applicatives` arose from the limitations of `fmap` with functions of multiple parameters makes the following patterns unsurprising. First parameter uses `<$>` then subsequent parameters use `<*>`. ```hs funcOfOneParam <$> p1 funcOfTwoParams <$> p1 <*> p2 pure funcOfTwoParams <*> p1 <*> p2 funcOfThreeParams <$> p1 <*> p2 <*> p3 pure funcOfThreeParams <*> p1 <*> p2 <*> p3 -- etc. ``` ## Conclusion Hopefull, this has made `Applicatives` seem a lot less magical, odd or unimportant. Historically, they came after `Functors` and `Monads` and one can now see why. You can do a lot with Functor by itself and it's only when you start dealing with functions of multiple parameters that you start to encounter the need for `Applicatives`. When I first saw that Applicatives took functions that were inside Functors, I thought "why would anyone put a function in a Functor". I could think of the rare case where a function is inside a Maybe, but it seems such an edge case that it seemed to hardly warrent a whole new thing. But after seeing this perspective, I realized that it's more of a by-product of using `fmap` with functions of multiple parameters. In our above examples, both `g` and `Person` were functions of multiple parameters.