Could someone explain why the following representation of (<*>) with (=<<) works:
f <*> a = (\f' -> return . f' =<< a) =<< f
Add a comment
|
2 Answers
This strikes me as a deliberately obtuse way of writing it. Whoever gave you this code is trying to mess with you. Here's the usual definition of ap, which is clean and easy to understand:
ap f a = do
f' <- f
a' <- a
return (f' a')
We can run this through the usual do desugaring transformation, replacing <- with >>=:
ap f a =
f >>= \f' ->
a >>= \a' ->
return (f' a')
Now, note that the innermost term is \a' -> return (f' a'), which can be written as return . f'.
ap f a =
f >>= \f' ->
a >>= return . f'
Then, since (=<<) = flip (>>=), we can replace >>= with =<< by exchanging the arguments:
ap f a = f >>= (\f' -> return . f' =<< a) -- reverse inner bind
ap f a = (\f' -> return . f' =<< a) =<< f -- reverse the other bind
There you go.
answered Jul 3, 2017 at 12:33
Benjamin Hodgson
44.9k18 gold badges115 silver badges168 bronze badges
2 Comments
matt
Thanks, it was the way it was asked in a problem. This does make it all much clearer.
castletheperson
Also
a >>= return . f' is equivalent to f' <$> a, so the whole thing could also be f >>= (<$> a)The use of names f and a is extremely confusing, because names are suggestive ("f" evokes "function", but isn't). Primed names can be confusing as well. Parens shouldn't be omitted while you're still learning and are unsure about the default operator precedences. Same goes for do's optional curly braces and semicolons.
The two names should have been fs and as. Changing them could be part of the expected answer. Thus you have
fs <*> as = (\f -> (return . f) =<< as) =<< fs
= fs >>= (\f ->
as >>= (return . f)) -- by definition of >>= and =<<
= fs >>= (\f ->
as >>= (\a -> (return . f) a)) -- by "eta expansion"
= fs >>= (\f ->
as >>= (\a -> return (f a))) -- by `(.)` reduction
= do { f <- fs
; a <- as
; return (f a) } -- by `do` syntax definition
because that's how the do syntax is defined. And that is the definition of ap, which <*> is supposed to be a stand-in for.
It goes without saying that this works only for a type which is not just an Applicative, but a Monad as well.
With monad comprehensions, the last one is written
= [f a | f <- fs, a <- as]
which is pretty clear in itself.
