Haskell - Evaluation of (+) <$> (+3) <*> (*100) $ 5

11
votes

From the chapter on Functors in Learn You a Haskell for Great Good, Lipovača states:

"When we do (+) <$> (+3) <*> (*100), we're making a function that will use + on the results of (+3) and (*100) and return that. To demonstrate on a real example, when we did (+) <$> (+3) <*> (*100) $ 5, the 5 first got applied to (+3) and (*100), resulting in 8 and 500. Then, + gets called with 8 and 500, resulting in 508."

However, if I try to evaluate the function myself, considering this definition for Applicative on the functor ((->) r):

instance Applicative ((->) r) where  
    pure x = (\_ -> x)  
    f <*> g = \x -> f x (g x)

I read the evaluation of the above expression as:

(\x -> (3 + x) (100 * x)) $ 5

But I don't see how we can compose two partially applied binary functions as a single lambda (in fact, GHCi throws an infinite type error trying to bind this to a variable). Furthermore, to a working interpretation, if we look at the type definition for <$> we get:

(<$>) :: Functor f => (a -> b) -> f a -> f b

or more specifically we can look at its lifting as:

(<$>) :: Functor f => (a -> b) -> (f a -> f b)

Considering that our functor in this case is ((->) r), I can deduce that this is what transformation takes place on the previous evaluation (assuming that left associativity happens first, instead of the right associative application of 5):

(\x -> a + b) where a = (+ 3) and b = (* 100). This is the function that should be returned. However, am I correct in assuming that this is the final (rough) form?

(\x -> (3 + x) + (100 * x)) $ 5

...which yields 508.

I find Lipovača's description more comprehensible in terms of how the expression works, but my gut tells me isn't entirely true for the gorey details under the Haskell compiler hood. It is easier for me to think that the fmap of (+) happened first resulting in a function with two functors who are partially applied functions that take a shared input, and then we applied a value to it. We can do this because of lazy evaluation. Is this wrong?

1
haskellfunctorapplicative

1 Answers

16
votes

Firstly, note that both <$> and <*> associate to the left. There's nothing magical happening internally and we can see the transformation with essentially a series of eta expansions and beta reductions. Step-by-step, it looks like this:

(((+) <$> (+3))         <*> (*100)) $ 5        -- Add parens
((fmap (+) (+3))        <*> (*100)) $ 5        -- Prefix fmap
(((+) . (+3))           <*> (*100)) $ 5        -- fmap = (.)
((\a -> (+) ((+3) a))   <*> (*100)) $ 5        -- Definition of (.)
((\a -> (+) (a+3))      <*> (*100)) $ 5        -- Infix +
((\a b -> (+) (a+3) b)) <*> (*100)) $ 5        -- Eta expand
(\x -> (\a b -> (+) (a+3) b) x ((*100) x)) $ 5 -- Definition of (<*>)
(\x -> (\a b -> (+) (a+3) b) x (x*100)) $ 5    -- Infix *
(\a b -> (+) (a + 3) b) 5 (5*100)              -- Beta reduce
(\a b -> (a + 3) + b)   5 (5*100)              -- Infix +
(5 + 3) + (5*100)                              -- Beta reduce (twice)
508                                            -- Definitions of + and *

A bit confusingly, the fact that $ associates to the right has less to do with what's happening here than the fact that its fixity is 0. We can see this if we define a new operator:

(#) :: (a -> b) -> a -> b
f # a = f a
infixl 0 #

and in GHCi:

λ> (+) <$> (+3) <*> (*100) # 5
508