A look into how Haskell's Applicative's work. We'll dissect it, along with how it works with the 'sequence' operator.
I’ve recently been devouring Learn You a Haskell for Great Good. I’ve been meaning to do it for ages, but a recent post by Debasish Ghosh pushed me to go through it cover to cover… I’m almost there :) I was wrestling over the complexities of applying the sequence function to a list of functions. More succinctly, I was confused on the mechanics of how this worked:
ghci> sequence [(> 4), (< 10), odd] 7
[True, True, True]
To figure it out, all you have to do is reduce it, and then reduce it, and then reduce it some more. Let’s do that. First, sequence is defined as (I’m using the definition of sequenceA from LYAH, as opposed to the definition of sequence from the Haskell API):
sequence :: (Applicative f) => [f a] -> f [a]
sequence = foldr (liftA2 (:)) (pure [])
And the definition of the Applicative Functor instance for functions is:
instance :: Functor ((->) r) where
pure x = (\_ -> x)
f <*> g = (\x -> f x (g x))
Now, let’s expand (note, I’m not going into nauseating detail here, and assume you’ve gone part of the way thus far):
sequence [(> 4), (< 10), odd]
-- becomes
foldr (liftA2 (:)) (pure []) [(> 4), (< 10), odd]
-- which becomes, due to the definition of liftA2
((:) . (> 4)) <*> (((:) . (< 10)) <*> (((:) . odd) <*> (pure [])))
Ok, so we’ve expanded the foldr and now we can expand the <*> and the pure []:
(\x -> ((:) . (> 4)) x (
\x -> ((:) . (< 10)) x (
\x -> ((:) . odd) x ((\_ -> []) x)) x) x)
Ok, that’s a bit rough to read… the key to it is noting how the 'x' gets propagated. Let’s take another look:
When we pass in the 7 it gets propagated to all of the little x’s, and all of those little x’s get passed to their composed functions, and each of those results in a new element on the list:
(\x -> ((:) . odd) x ((\_ -> []) x)) 7
-- reduces to
((:) . odd) 7 (\_ -> []) 7)
-- which reduces to
(: True [])
-- which becomes
[True]
-- Now, we use that to reduce the next level up
((:) . (< 10) 7) [True]
-- which becomes
(: True [True])
-- which becomes
[True, True]
-- And now our last level
((:) . (> 4) 7) [True, True]
-- which becomes
(: True [True, True])
-- which becomes
[True, True, True]
Ah, that’s better… now that I ‘get it’, I can move on. Cheers!