12

Studying functors, applicative functors and monads in Haskell, I found this definition on Wikipedia:

In functional programming, specifically Haskell, an applicative functor is a structure that is like a monad (return, fmap, join) without join, or like a functor with return.

I can't understand: it seems to me that providing return (i.e. pure) to a functor is not sufficient to obtain an applicative functor, because you need to provide ap (i.e. <*>) too, which cannot be defined in terms of fmap and return only. Did I miss something or Wikipedia's definition is not absolutely correct?

EDIT 2017-02-08: I found other useful insights on this question in this answer.

Community
  • 1
  • 1
mmlab
  • 125
  • 1
  • 7
  • You are correct, as I agree that is a terrible definition for applicative functors. Without `<*>`, that definition seems incomplete. I am racking my brain to see if you could derive `<*>` just from return/fmap, and I don't think it's possible. – hao Feb 04 '17 at 17:45
  • 1
    @haoformayor you cannot. Just [count the `f`s](http://stackoverflow.com/a/34933736/1139697): both `fmap` and `return` increase the count of `f`s in the type, whereas `<*>` keeps it constant. – Zeta Feb 04 '17 at 18:27
  • 4
    I have to say, I've *never* understood wikipedia's definition of *any* advanced mathematical concept without already having at least some degree of understanding of it to start with. I simply would never go there for this kind of learning, as I would just end up getting very confused... even after @Zeta's edits I find the article very confusing. So, it's a strong lax monoidal functor... but what does that mean? The monoidal functor article doesn't help, because it suggests that "strong" and "lax" are mutually exclusive... – Periata Breatta Feb 05 '17 at 00:31
  • 2
    @PeriataBreatta someone should rewrite that article. Without Haskell knowledge, it's useless. With Haskell knowledge, it's mostly useless :/. – Zeta Feb 05 '17 at 10:13
  • That article was suggesting a nice (but unfortunately wrong) thing: that there was a simple progression from functor to applicative and finally to monad, just by progressively adding class methods. Start with a functor with an fmap, then add a return and you get an applicative, then again add a join and you'll have a monad. That seemed nice to me, given that functor is a superclass of applicative which is in turn a superclass of monad; but it doesn't work with fmap, return and join. Maybe that could work with some other typeclass methods? – mmlab Feb 05 '17 at 15:46

2 Answers2

9

The article was not correct. Assume we have a monad m without join, or a functor with return. We can define pure immediately:

pure :: Monad m => a -> m a
pure = return

We cannot, however, define (<*>) with fmap and return only. All we have is fmap, so we would end up with m (m a) if we try to use an m (a -> b). At that point we need join or its equivalent (>>=):

(<*>) :: Monad m => m (a -> b) -> m a -> m b
f <*> x = join (fmap (flip fmap x) f)

-- or, easier to read:
-- f <*> x = do
--   f' <- f
--   x' <- x
--   return f' x'

An applicative functor is like a functor with return and ap, but no join. So yes, you were completely right, Wikipedia missed the operation of applicative (see the original paper).

By the way, if you add only pure, you get a pointed functor. The typeclassopedia provides a better overview over Applicative than the Wikipedia article, though.

Zeta
  • 103,620
  • 13
  • 194
  • 236
  • 2
    Note that I use "was not correct". I've took the courtesy to fix the article. – Zeta Feb 04 '17 at 18:21
  • @adamse Whoops, accidentally used posted `(>>=)` instead of `(<*>)`. Sorry for the inconvenience. – Zeta Feb 04 '17 at 19:02
7

You are correct, applicative functors require <*> as well as pure for a minimal definition. It's worth noting that we can get fmap from those, though:

fmap f a = pure f <*> a

Similarly we can get the applicative definition from monads:

pure = return
f' <*> a' = do
    f <- f'
    a <- a'
    return $ f a

You could look at applicatives functors a generalization of functors to multi argument functions or as combining values with context horizontally:

liftA2 f a b = f <$> a <*> b
fmap :: (a -> b) -> (f a -> f b)
liftA2 :: (a -> b -> c) -> (f a -> f b -> f c)
Taren
  • 674
  • 5
  • 11