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.
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.
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].
For anyone who has trouble accepting that an argument to sequenceA [(+1)] just magically applies itself to BOTH (+1) and const [], this is for you. It was the only sticking point for me after realizing that pure [] = const [].
sequenceA [(+1)] = (:) <$> (+1) <*> const []
Using lambdas (so we can explicitly show and move things around when we start treating function application like a functor and an applicative):
sequenceA [(+1)] = \b c -> ( (:) b c ) <$> ( \a -> (+1) a ) <*> ( \a -> const [] a )
Both (<$>) and (<*>) are infixl 4. Which means we read and evaluate from left to right, i.e. we start with (<$>).
Where (<$>) :: Functor f => (a -> b) -> f a -> f b.
The effect of <$> is to pluck (+1) out of it's wrapper ((->) r), OR \a -> from our lambda code, and apply it to \b c -> ( (:) b c ) where it will take the place of b, then re-apply the wrapper (that's the \a that appears after the equals sign on the line below):
sequenceA [(+1)] = \a c -> ( (:) ((+1) a) c ) <*> ( \a -> const [] a )
Notice that (:) is still waiting for an argument c, and (+1) is still waiting for an a. Now, we get to the applicative part.
Remember that: (<*>) :: f (a -> b) -> f a -> f b. Our f here is the function application \a ->.
Both sides now have the same wrapper, namely \a ->. I'm keeping the a's in there to remind us where the a's will be applied later, so it does become a little pseudo-y here. The function application will be connected back up in just a jiffy. Both functions depend on the same a, precisely because they had the same function application wrapper i.e. an applicative. Without their \a -> wrappers (thanks to <*>), it goes like this:
( \c -> ( (:) ((+1) a) c ) ) (const [] a)
= ( (:) ((+1) a) (const [] a) ) -- Ignore those a's, they're placeholders.
Now, the very last thing that <*> does is to pop this result back into it's wrapper \a ->:
sequenceA [(+1)] = \a -> ( (:) ((+1) a) (const [] a) )
Sugaring this up a little bit gives:
sequenceA [(+1)] = \a -> (+1) a : const [] a
See! It makes perfect sense that an argument to sequenceA [(+1)] goes to both (+1) and const. Applying a 2, for instance, gives:
sequenceA [(+1)] 2 = (+1) 2 : const [] 2
Remember that const a b :: a -> b -> a, and therefore just ignores it's input:
sequenceA [(+1)] 2 = 3 : []
OR, more sweetly:
sequenceA [(+1)] 2 = [3]
