applicative rewrite (Haskell)

Question

When I don't grasp how an expression in Haskell works I often find it helps to decompose it into a more basic form.

Using the following definitions

sequenceA :: (Applicative f) => [f a] -> f [a]
sequenceA [] = pure []
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs

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

I rewrote sequenceA [(+3),(+2)] 3 as

(\_ -> (:)) <*> (+3) <*> ((\_ -> (:)) <*> (+2) <*> (\_-> [])) $ 3

And then turned it into (please excuse the format; I'm not sure what the convention is for splitting lines)

(\d ->(\c->(\b -> (\a -> (\_ -> (:)) a (+3) a) b (\_ -> (:)) b) c (+2) c) d (\_ -> []) d) 3

This seems right when I work through it by hand, but I can't get GHCi to accept it. What have I done wrong here? My second question is how to convert from this form into functional composition. I've tried substituing dots in various combinations, but GHCi rejects all of them....

Answer 1

Being an idle goodfornothing, I thought I would make a computer do the expansion for me. So into GHCi, I typed

let pu x = "(\\_ -> " ++ x ++ ")"
let f >*< a = "(\\g -> " ++ f ++ " g (" ++ a ++ " g))"

So now I have funny versions of pure and <*> which map strings which look like expressions to string which look like more complicated expressions. I then defined, similarly, the analogue of sequenceA, replacing functions by strings.

let sqa [] = pu "[]" ; sqa (f : fs) = (pu "(:)" >*< f) >*< sqa fs

I was then able to generate the expanded form of the example as follows

putStrLn $ sqa ["(+3)","(+2)"] ++ " 3"

which duly printed

(\g -> (\g -> (\_ -> (:)) g ((+3) g)) g ((\g -> (\g -> (\_ -> (:)) g ((+2) g)) g  ((\_ -> []) g)) g)) 3

This last, copied to the prompt, yielded

[6,5]

Comparing the output from my "metaprogram" with the attempt in the question shows a shorter initial prefix of lambdas, arising from a shallower nesting of <*> operations. Remember, it's

(pure (:) <*> (+3)) <*> ((pure (:) <*> (+2)) <*> pure [])

so the outer (:) should be only three lambdas deep. I suspect the proposed expansion may correspond to a differently bracketed version of the above, perhaps

pure (:) <*> (+3) <*> pure (:) <*> (+2) <*> pure []

Indeed, when I evaluate

putStrLn $ pu "(:)" >*< "(+3)" >*< pu "(:)" >*< "(+2)" >*< pu "[]" ++ " 3 "

I get

(\g -> (\g -> (\g -> (\g -> (\_ -> (:)) g ((+3) g)) g ((\_ -> (:)) g)) g ((+2) g)) g ((\_ -> []) g)) 3

which looks like it matches the (updated)

(\d -> (\c -> (\b -> (\a -> (\_ -> (:)) a ((+3) a)) b ((\_ -> (:)) b)) c ((+2) c)) d ((\_ -> []) d)) 3

I hope this machine-assisted investigation helps to clarify what's going on.

Answer 2

You rewrote (\_ -> (:)) <*> (+3) as \a -> (\_ -> (:)) a (+3) a, which is rewriting f <*> g as f x g x instead of f x (g x). I think you made that mistake for every <*>.

Answer 3

It might be easier to use combinators, e.g. _S and _K, symbolically, and not their definitions as lambda-expressions,

_S f g x = f x (g x)
_K x y   = x

With functions, fmap is (.) and <*> is _S, as others already mentioned. So,

sequenceA [(+3),(+2)] 3 ==
    ( ((:) <$> (+3)) <*> sequenceA [(+2)]        ) 3  ==
    _S ((:).(+3))   ( ((:) <$> (+2)) <*> pure [] ) 3  ==
    _S ((:).(+3))   ( _S ((:).(+2))   (_K [])    ) 3  ==
       ((:).(+3)) 3 ( _S ((:).(+2))   (_K [])  3 )    ==
       ((:).(+3)) 3 (    ((:).(+2)) 3 (_K [] 3)  )    ==
    (6:) ( (5:) [] ) ==
    [6,5]

So it might be easier to decompose expressions down to basic functions and combinators and stop there (i.e. not decomposing them to their lambda expressions), using their "re-write rules" in manipulating the expression to find its more comprehensible form.

If you wanted to, you could now write down for yourself a more abstract, informal re-write rule for sequenceA as

sequenceA [f,g,..., z] ==
    _S ((:).f) . _S ((:).g) . _S ..... . _S ((:).z) . _K []

and so

sequenceA [f,g,..., z] a ==
    ((:).f) a $ ((:).g) a $  ..... $ ((:).z) a $ _K [] a ==
    (f a:)    $ (g a:)    $  ..... $ (z a:)    $ []      ==
    [f a, g a, ..., z a]

and hence

sequenceA fs a == map ($ a) fs == flip (map . flip ($)) fs a

to wit,

Prelude Control.Applicative> flip (map . flip ($)) [(+3),(+2)] 3
[6,5]