How `sequenceA` works

Question

I'm new to Haskell and trying to understand how does this work?

sequenceA [(+3),(+2),(+1)] 3

I have started from the definition

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

And then unfolded recursion into this

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

But here i don't understand for which applicative functor operator <*> will be called, for ((->) r) or for []

(:) <$> (+1) <*> []

Can somebody go step by step and parse sequenceA [(+3),(+2),(+1)] 3 step by step? Thanks.

Answer 1

This can be seen from the type of sequenceA:

sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)

The argument's outer type has to be a Traverable, and its inner type has to be Applicative.

Now, when you give sequenceA a list of functions (Num a) => [a -> a] the list will be the Traversable, and the things inside the list should be Applicative. Therefore, it uses the applicative instance for functions.

So when you apply sequenceA to [(+3),(+2),(+1)], the following computation is built:

sequenceA [(+3),(+2),(+1)] = (:) <$> (+3) <*> sequenceA [(+2),(+1)]
sequenceA [(+2),(+1)]      = (:) <$> (+2) <*> sequenceA [(+1)]
sequenceA [(+1)]           = (:) <$> (+1) <*> sequenceA []
sequenceA []               = pure []

Let's look at the last line. pure [] takes an empty list and puts it inside some applicative structure. As we've just seen, the applicative structure in this case is ((->) r). Because of this, sequenceA [] = pure [] = const [].

Now, line 3 can be written as:

sequenceA [(+1)] = (:) <$> (+1) <*> const []

Combining functions this way with <$> and <*> results in parallel application. (+1) and const [] are both applied to the same argument, and the results are combined using (:)

Therefore sequenceA [(+1)] returns a function that takes a Num a => a type value, applies (+1) to it, and then prepends the result to an empty list, \x -> (:) ((1+) x) (const [] x) = \x -> [(+1) x].

This concept can be extended further to sequenceA [(+3), (+2), (+1)]. It results in a function that takes one argument, applies all three functions to that argument, and combines the three results with (:) collecting them in a list: \x -> [(+3) x, (+2) x, (+1) x].

Answer 2

it is using instance Applicative ((->) a).

Try this in ghci:

Prelude> :t [(+3),(+2),(+1)]
[(+3),(+2),(+1)] :: Num a => [a -> a]

Prelude> :t sequenceA
sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)

and pattern match the argument type: t = [], f = (->) a and the Applicative constraint is on f.