Extending understanding of Applicative from liftA2 to liftA3-CodePudding

I am trying to get a hold over understanding Applicative functors currently. And my understanding is falling short somewhere but I cannot pinpoint where. Source from where I am trying to build an understanding CIS 194 UPenn - Homework 10

I am working with a custom data type and its Applicative instance which are as follows :

-- A parser for a value of type a is a function which takes a String
-- represnting the input to be parsed, and succeeds or fails; if it
-- succeeds, it returns the parsed value along with the remainder of
-- the input.
newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

instance Functor Parser where
  fmap :: (a -> b) -> Parser a -> Parser b
  fmap fn parserA = Parser (fmap (first fn) . parseAFunc)
    where parseAFunc = runParser parserA

appliedFunc p1 p2 str = case runParser p1 str of
    Nothing        -> Nothing
    Just (f, str2) -> case runParser p2 str2 of
        Nothing        -> Nothing
        Just (x, str3) -> Just (f x, str3)

instance Applicative Parser where
  pure a = Parser (\s -> Just (a, s))
  p1 <*> p2 = Parser (appliedFunc p1 p2)  

-- For example, 'satisfy' takes a predicate on Char, and constructs a
-- parser which succeeds only if it sees a Char that satisfies the
-- predicate (which it then returns).  If it encounters a Char that
-- does not satisfy the predicate (or an empty input), it fails.
satisfy :: (Char -> Bool) -> Parser Char
satisfy p = Parser f
  where
    f [] = Nothing    -- fail on the empty input
    f (x:xs)          -- check if x satisfies the predicate
                        -- if so, return x along with the remainder
                        -- of the input (that is, xs)
        | p x       = Just (x, xs)
        | otherwise = Nothing  -- otherwise, fail

-- Using satisfy, we can define the parser 'char c' which expects to
-- see exactly the character c, and fails otherwise.
char :: Char -> Parser Char
char c = satisfy (== c)

-- Below is a parser for positive Ints which parses
-- the prefix of contiguous digits in a given String
-- as an Int 
posUse :: Parser Int
posUse = Parser f
  where
    f xs
      | null ns   = Nothing
      | otherwise = Just (read ns, rest)
      where (ns, rest) = span isDigit xs

-- Below function takes a function and a pair and returns a pair 
-- with the function applied to the first element of pair
first :: (a -> b) -> (a, c) -> (b, c)
first fn (x, y) = (fn x, y)

Using all the above setup, I am trying to construct some more complicated Parsers using simple Parsers defined above. So fmap has type fmap :: Functor f => (a -> b) -> f a -> f b. And as per my understanding currently, Applicative allows us to extend fmap to functions that take n-ary functions and n Functor parameters and return the resultant functor.

fmap can be defined in terms of pure and <*> as :

fmap1 :: Applicative f => (a -> b) -> f a -> f b
fmap1 f x = pure f <*> x

I understand why the above will work given that the implementations of pure and <*> are appropriate since the types nicely line up.

Extending this to fmap2 aka liftA2 :

fmap2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
fmap2 f x y = pure f <*> x <*> y

My understanding of why the above works is as follows : pure g will have type f (a -> b -> c) And so therefore pure g <*> x will have type f (b -> c) since functions are curried. Then this type combined with the type type of y (f b) using <*> will finally give us the type of the result which is f c which is what we needed the type fmap2 to be.

This understanding did not break down when I tried to construct a Parser out of 2 simple Parsers as follows :

-- This Parser expects to see the characters ’a’ and ’b’ and returns them
-- as a pair.
abParser = liftA2 (\c1 c2 -> (c2 c1)) (char 'a') (char 'b')

The above works as expected.

But when I try to make the parser intPair which reads two integer values separated by a space and returns the integer values in a list using liftA3 my understanding of lift is not working since I expect the following to work but the linter complains :

intPair :: Parser [Int]
intPair = liftA3 (\x y z -> [z x]) posUse (char ' ') posUse

The above does not compile as the last argument needs to have the type Parser (Int -> a) (according to type inference) but I have passed posUse which has the type Parser Int.

TL;DR : Sorry for the long description. If anyone does not want to go through it all (expecially the custom data type and its Applicative and Functor instance) -- please let me know if my understanding of why fmap2 aka liftA2 works is correct and how does that understanding extend to liftA3 ? The definition of liftA3 seems to be something different than just an extension of the definition of liftA2 using <*> and pure.

Edit 1 : As stated above, the below line was being complained about by the linter

intPair :: Parser [Int]
intPair = liftA3 (\x y z -> [z x]) posUse (char ' ') posUse

The linter expected the type for the last argument to be Parser (Int -> a). But after I defined an explicit function instead of passing a lambda, it worked as I expected to work.

fnn :: Int -> Char -> Int -> [Int]
fnn arg1 arg2 arg3 = [arg1, arg3]
intPair = liftA3 fnn posUse (char ' ') posUse

It works as I expected.

CodePudding user response：

Yes, your understanding of liftA2 is correct, and liftA3 is just more of the same. I can't guess why it looks different to you, but inlining the definition of liftA2 into the definition of liftA3 may help.

liftA2 :: Applicative f => (a -> b -> c) 
                        -> f a -> f b -> f c
liftA2 f x y = pure f <*> x <*> y

liftA3 :: Applicative f => (a -> b -> c -> d) 
                        -> f a -> f b -> f c -> f d
liftA3 f a b c = liftA2 f a b <*> c

I took these definitions from https://hackage.haskell.org/package/base-4.17.0.0/docs/src/GHC.Base.html, and rearranged the definition of liftA2 a little to make it more explicit - it matches your fmap2 exactly.

Now, note that liftA3 includes a call to liftA2 f a b. We know how liftA2 f a b is defined, and because of purity, we can always inline definitions to yield semantically identical terms. So let's do that:

liftA3 f a b c = (pure f <*> a <*> b) <*> c

The parentheses are redundant, but I put them in while substituting just in case. Now if we remove them, we see there is no new idea here:

liftA3 f a b c = pure f <*> a <*> b <*> c

We lift the function, yielding f (a -> b -> c -> d), then apply that to a with <*> to get an f (b -> c -> d), and so on, all the way to an f d at the end.

CodePudding user response：

You've just made a silly mistake when converting from a named function to an anonymous one. Contrast:

fnn arg1 arg2 arg3 = [arg1, arg3] -- your working code
fnn = \x y z -> [z x]             -- your broken code
fnn = \x y z -> [z, x]            -- type-correct code
fnn = \x y z -> [x, z]            -- more correct translation of your working code