More fun with applicative functors

Question

Earlier, I asked about the translation of monadic code to use only an instance of the application functionality of Parsec. Unfortunately, I had several answers that answered a question that I literally asked, but really didn’t understand very well. So let me try this again ...

To summarize my knowledge, an applied functor is something more limited than a monad. In the less-than-more tradition, restricting what code can do increases the possibilities for crazy code manipulation. Despite this, many people seem to think that using the applicative instead of the monad is an excellent solution where possible.

The Applicative class is defined in Control.Applicative , whose Haddock list helps with class methods and utility functions to separate class instances of classes between them, making it difficult to quickly see the entire screen at once. But the corresponding type signatures

 pure :: x -> fx <*> :: f (x -> y) -> fx -> fy *> :: fx -> fy -> fy <* :: fx -> fy -> fx <$> :: (x -> y) -> fx -> fy <$ :: x -> fy -> fx 

Great point, right?

Well, Functor already gives us fmap , which is basically <$> . Ie, Given a function from x to y , we can match fx to a fy . Applicative adds two new elements. One of them is pure , which is roughly the same type as return (and several other operators in category theory classes). The other is <*> , which gives us the opportunity to take a container of functions and a container of inputs and create a container with outputs.

Using the above operators, we can very carefully do something like

 foo <$> abc <*> def <*> ghi 

This allows us to take an N-ary function and pass its arguments from N functors in a way that can be easily generalized to any N.

---

I already understand that. There are two main things that I still do not understand.

First, the functions *> , <* and <$ . Of their types <* = const , *> = flip const and <$ may be something like this. Presumably, this does not describe what these functions actually perform. (??!)

Secondly, when writing the Parsec parser, each parsed object usually looks something like this:

 entity = do var1 <- parser1 var2 <- parser2 var3 <- parser3 ... return $ foo var1 var2 var3... 

Since the applicative functor does not allow us to associate intermediate results with variables in this way, I am puzzled by how to collect them at the final stage. I could not fully think through the idea to figure out how to do this.

Answer 1

The functions <* and *> very simple: they work just like >> . <* will work the same as << , except << does not exist. Basically, given a *> b , you first “do” a , then “do” b and return the result b . For a <* b you still “do” a , then “do” b , but you return the result of a . (Of course, for the corresponding values ​​"do").

The <$ function is just fmap const . So a <$ b is equal to fmap (const a) b . You simply throw away the result of the "action" and instead return a constant value. The Control.Monad void function of type Functor f => fa -> f () can be written as () <$ .

These three functions are not fundamental to the definition of an applicative functor. ( <$ , in fact, works for any functor.) This again is similar to >> for monads. I believe that they are in the class to simplify their optimization for specific instances.

When you use applicative functors, you do not “extract” the value from the functor. In the monad, this is what >>= does, and what foo <- ... desugars to. Instead, you pass wrapped values ​​to the function directly using <$> and <*> . Therefore, you can rewrite your example as:

 foo <$> parser1 <*> parser2 <*> parser3 ... 

If you want to use intermediate variables, you can simply use the let statement:

 let var1 = parser1 var2 = parser2 var3 = parser3 in foo <$> var1 <*> var2 <*> var3 

As you correctly understood, pure is just another name for return . So, to make the overall structure more obvious, we can rewrite it like this:

 pure foo <*> parser1 <*> parser2 <*> parser3 

Hope this clarifies the situation.

Now notice a little. People recommend using applicative functor functions for parsing. However, you should only use them if they make more sense! For complex things, the monad version (especially with do-notation) may actually be clearer. The reason people recommend this is because

 foo <$> parser1 <*> parser2 <*> parser3 

is shorter and more readable than

 do var1 <- parser1 var2 <- parser2 var3 <- parser3 return $ foo var1 var2 var3 

Essentially, f <$> a <*> b <*> c is essentially similar to an application with canceled functions. You can imagine that <*> is a replacement for a space (for example, a functional application) in the same way that fmap is a replacement for a function application. It should also give you an intuitive idea of ​​why we use <$> - it's like a shot version of $ .

Answer 2

I can make a few comments here, hopefully helpful. This reflects my understanding, which in itself may be wrong.

pure unusually named. Usually functions are called a reference to what they produce, but in pure x it is x , which is pure. pure x gives an applicative functor that carries pure x . Of course, "tolerates" is approximate. Example: pure 1 :: ZipList Int is a ZipList that carries a pure Int , 1 value.

<*> , *> and <* are not functions, but methods (this answers your first problem). f in its types is not general (for example, for functions), but specific, as indicated by a specific instance. That's why they are really not just $ , flip const and const . The specialized type f indicates the semantics of the combination. In the usual applicative programming style, combination means application. But with functors there is an additional dimension represented by the type “carrier” f . In fx there is "content", x , but there is also "context", f .

The "applicative functors" style is designed to provide programming of the "applicative style" with effects. Effects are represented by functors, carriers, context providers; "applicative" referring to the normal applicative style of functional use. Writing just fx to signify an application was once a revolutionary idea. There is no need for additional syntax, no operators (funcall fx) , no CALL , none of these additional things - the combination was not an application ... Not so, with effects, it would seem that again there was a need for a special syntax when programming with effects. The slaughtered beast reappeared.

So, Applicative Programming with Effects came about to make the combination an average simple application again - in a special (possibly effective) context, if they really were in that context. Thus, for a :: f (t -> r) and b :: ft (almost equal), the combination a <*> b has the application of the transferred content (or types t -> r and t ), in the given context (type f )

The main difference from monads: monads are non-linear . AT

 do x <- a y <- b z <- c return (x,y,z) 

return has access to all the variables above. Functions nested:

 a >>= (\x -> b >>= (\y -> c >>= (\z -> .... ))) 

This can be made flat by making the calculation steps returned repackaged, composite data (this concerns your second problem):

 a >>= (\x -> b >>= (\y-> return (x,y))) >>= (\(x,y) -> c >>= (\z-> return (x,y,z))) >>= (\(x,y,z) -> ..... ) 

and this is essentially an applicative style. Therefore, when your combinations create data that covers all the information needed for further combinations, and there is no need for “external variables”, you can use this combination style.

But if your monadic chain has branches depending on the values ​​of such "external" variables (that is, the results of the previous stages of the monadic calculation), you cannot make a linear chain from it. This is essentially monadic.

---

by way of illustration, the first example in this article shows how a “monadic” function

 sequence :: [IO a] → IO [a] sequence [ ] = return [ ] sequence (c : cs) = do x ← c xs ← sequence cs return (x : xs) 

can really be encoded in this "flat, linear" style like

 sequen :: (Applicative f) => [fa] -> f [a] sequen [] = pure [] sequen (c : cs) = pure (:) <*> c <*> sequen cs 

There is no use here for the ability of the monad to enter into previous results.

---

A great pair note is a combination without an app. This shows that the essence of what applicative functors add to simple functors is the ability to combine. Then the application is reached by the good old fmap . This suggests combinatorial functions as the best possible name.

Answer 3

You can view functors, applicators and monads as follows: they all carry a kind of “effect” and “value”. (Note that the terms “effect” and “value” are only approximations — in fact, there should not be any side effects or meanings — for example, in Identity or Const .)

• With Functor you can change the possible values ​​inside using fmap , but you cannot do anything with the effects inside.

• With Applicative you can create a value without any effect with pure , and you can use sequence effects and combine your values ​​internally. But the effects and values ​​are separate: with sequencing effects, the effect cannot depend on the value of the previous one. This is reflected in <* , <*> and *> : they influence the sequence and combine their values, but you cannot in any way study the values ​​inside.

  You can define Applicative with this alternative set of functions:

   fmap :: (a -> b) -> (fa -> fb) pureUnit :: f () pair :: fa -> fb -> f (a, b) -- or even with a more suggestive type (fa, fb) -> f (a, b) 

  (where pureUnit has no effect) and define pure and <*> from them (and vice versa). Here is a pair sequences of two effects and remembers the values ​​of both of them. This definition expresses the fact that Applicative is a monoidal functor.

  Now consider an arbitrary (final) expression consisting of pair , fmap , pureUnit and some primitive applicative values. We have a few rules that we can use:

   fmap f . fmap g ==> fmap (f . g) pair (fmap fx) y ==> fmap (\(a,b) -> (fa, b)) (pair xy) pair x (fmap fy) ==> -- similar pair pureUnit y ==> fmap (\b -> ((), b)) y pair x pureUnit ==> -- similar pair (pair xy) z ==> pair x (pair yz) 

  Using these rules, we can change the order of pair s, push fmap out and exclude pureUnit s, so in the end, such an expression can be converted

   fmap pureFunction (x1 `pair` x2 `pair` ... `pair` xn) 

  or

   fmap pureFunction pureUnit 

  So, we can first collect all the effects together using pair , and then change the resulting value inside, using a pure function.

• With Monad effect may depend on the value of the previous monadic value. This makes them so powerful.

Answer 4

The answers that have already been given are excellent, but there is one small (ish) point that I would like to describe explicitly, and it relates to <* , <$ and *> .

One example was

 do var1 <- parser1 var2 <- parser2 var3 <- parser3 return $ foo var1 var2 var3 

which can also be written as foo <$> parser1 <*> parser2 <*> parser3 .

Suppose the value of var2 does not matter for foo - for example. these are just dividing spaces. Then it also makes no sense to have foo accept this space just to ignore it. In this case, foo should have two parameters, not three. Using do notation, you can write this as:

 do var1 <- parser1 parser2 var3 <- parser3 return $ foo var1 var3 

If you want to write this using only <$> and <*> , it should be something like one of these equivalent expressions:

 (\x _ z -> foo xz) <$> parser1 <*> parser2 <*> parser3 (\x _ -> foo x) <$> parser1 <*> parser2 <*> parser3 (\x -> const (foo x)) <$> parser1 <*> parser2 <*> parser3 (const . foo) <$> parser1 <*> parser2 <*> parser3 

But it is difficult to do with a lot of arguments!

However, you can also write foo <$> parser1 <* parser2 <*> parser3 . You can call foo semantic function that gets the result of parser1 and parser3 , while ignoring the result of parser2 . Missing > indicates ignoring.

If you want to ignore the result of parser1 , but use the other two results, you can write foo <$ parser1 <*> parser2 <*> parser3 , using <$ instead of <$> .

I never used a lot of use for *> , I would usually write id <$ p1 <*> p2 for a parser that ignores the result of p1 and simply parses with p2 ; you can write this as p1 *> p2 , but it increases the cognitive load for code readers.

I understood this way of thinking only for parsers, but later it was generalized to Applicative s; but I think this notation comes from the uuparsing library ; at least I used it in Utrecht 10 years ago.

Answer 5

I would like to add / rewrite a couple of things to very useful existing answers:

Applications are "static." In pure f <*> a <*> b , b is independent of a , and therefore can be analyzed statically . This is what I tried to show in my answer to your previous question (but, I think, I failed - sorry) - that, since there was really no consistent dependence by parsers, monads did not need.

The key difference that monads bring to the table is (>>=) :: Monad m => ma -> (a -> mb) -> ma , or, alternatively, join :: Monad m => m (ma) . Note that whenever you have x <- y inside the do notation, you use >>= . They say that monads allow you to use the value "inside" the monad to create a new monad "dynamically." This cannot be done with the applicator. Examples:

 -- parse two in a row of the same character char >>= \c1 -> char >>= \c2 -> guard (c1 == c2) >> return c1 -- parse a digit followed by a number of chars equal to that digit -- assuming: 1) `digit`s value is an Int, -- 2) there a `manyN` combinator -- examples: "3abcdef" -> Just {rest: "def", chars: "abc"} -- "14abcdef" -> Nothing digit >>= \d -> manyN d char -- note how the value from the first parser is pumped into -- creating the second parser -- creating 'half' of a cartesian product [1 .. 10] >>= \x -> [1 .. x] >>= \y -> return (x, y) 

Finally, Attributes enable function cancellation, as @WillNess indicated. To try to understand what the “intermediate” results look like, you can look at the parallels between the normal and the canceled application functions. Assuming add2 = (+) :: Int -> Int -> Int :

 -- normal function application add2 :: Int -> Int -> Int add2 3 :: Int -> Int (add2 3) 4 :: Int -- lifted function application pure add2 :: [] (Int -> Int -> Int) pure add2 <*> pure 3 :: [] (Int -> Int) pure add2 <*> pure 3 <*> pure 4 :: [] Int -- more useful example [(+1), (*2)] [(+1), (*2)] <*> [1 .. 5] [(+1), (*2)] <*> [1 .. 5] <*> [3 .. 8] 

Unfortunately, you cannot reliably print the result of pure add2 <*> pure 3 for the same reason that you cannot add2 ... disappointment. You can also look at Identity and its typeclass instances to get an application descriptor.