CODEWITHSUNDEEP
haskell
bpaterni
bpaterni

Reputation: 261

How does applicative sequencing over a list of functions work?

I'm learning Haskell with the Learn You a Haskell guide, and I'm stuck on an example of applicative sequencing over a list of functions. Chapter 11: Functors, Applicative Functors and Monoids defines sequenceA to be:

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

I'm a bit confounded by this example usage of sequenceA:

> sequenceA [(+3),(+2),(+1)] 3
[6,5,4]

I've expanded the application manually as far as I could to what I believe is correct:

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

What I don't see though, is how the second argument to the original application of sequenceA, 3 gets applied to each of the partially applied functions given in the list. I would appreciate some assistance in trying to wrap my head around what goes on in the evaluation of this statement.

Upvotes: 6

Views: 1578

Answers (2)

J. Abrahamson
J. Abrahamson

Reputation: 74354

Whenever you're dealing with generic types you need to first determine what the concrete type is. In this case, we have

sequenceA :: Applicative f => [f a] -> f [a]

applied to

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

In other words, though it's a bit bizarre to see at first, f becomes a -> (properly written (->) a) and so the type of sequenceA, specialized, is

sequenceA :: Num a => [a -> a] -> a -> [a]

Which should already explain where that extra argument came from.

So how does sequenceA work? To understand, we need to understand the Applicative instance for (->) a. In particular

instance Functor ((->) a) where
  fmap f g = f . g

instance Applicative ((->) a) where
  pure a'   = \a -> a'
  ff <*> fx = \a -> (ff a) (fx a)

where we see that (<*>) takes two functions and produces a third. The argument from this third function is applied to each of the input functions (here, ff and fx) and then their results are applied to one another.

So application in the (->) a monad means that the ultimate argument a to the result is distributed to all of the compositional functions.

And this is what we see with sequenceA

sequenceA [(+3),(+2),(+1)]
==
\a -> [(a + 3), (a + 2), (a + 1)]

Upvotes: 12

Karol S
Karol S

Reputation: 9402

Using:

instance Applicative ((->) a) where
    pure = const
    (<*>) f g x = f x (g x)

we can derive:

      (:) <$> (+3) <*> (      (:) <$> (+2) <*> (     (:) <$> (+1) <*> const [] ))
 pure (:) <*> (+3) <*> ( pure (:) <*> (+2) <*> ( pure (:) <*> (+1) <*> const [] ))
const (:) <*> (+3) <*> (const (:) <*> (+2) <*> (const (:) <*> (+1) <*> const [] ))
(const (:) <*> (+3)) <*> ((const (:) <*> (+2)) <*> ((const (:) <*> (+1)) <*> const [] ))
(const (:) <*> (+3)) <*> ((const (:) <*> (+2)) <*> ((\x -> (const (:)) x (x+1)) <*> const [] ))
(const (:) <*> (+3)) <*> ((const (:) <*> (+2)) <*> ((\x -> (:) (x+1)) <*> const [] ))
(const (:) <*> (+3)) <*> ((const (:) <*> (+2)) <*> (\y -> (\x -> (:) (x+1)) y (const [] y) ))
(const (:) <*> (+3)) <*> ((const (:) <*> (+2)) <*> (\y -> (\x -> (:) (x+1)) y [] ))
(const (:) <*> (+3)) <*> ((const (:) <*> (+2)) <*> (\y -> ((y+1):) [] ))
(const (:) <*> (+3)) <*> ((const (:) <*> (+2)) <*> (\y -> [y+1] ))
(const (:) <*> (+3)) <*> (((\x -> (const (:)) x (x+2)) <*> (\y -> [y+1] ))

(const (:) <*> (+3)) <*> (\z -> ((\x -> (const (:)) x (x+2)) z ((\y -> [y+1] )z))
(const (:) <*> (+3)) <*> (\z -> (((const (:)) z (z+2))  ([z+1]))
(const (:) <*> (+3)) <*> (\z -> ((z+2):)  [z+1])
(const (:) <*> (+3)) <*> (\z -> [z+2,z+1])
(\x -> (const (:)) x (x+3)) <*> (\z -> [z+2,z+1])
(\x -> const (:) (x+3)) <*> (\z -> [z+2,z+1])
(\x -> ((x+3):)) <*> (\z -> [z+2,z+1])
\w -> (\x -> ((x+3):)) w ((\z -> [z+2,z+1]) w)
\w -> ((w+3):) [w+2,w+1]
\w -> [w+3,w+2,w+1]

I bet I messed up some parentheses

Upvotes: 2

Related Questions