<*> for lists implemented as do notation - isn't this "cheating"?

Question

According to 'Learn you a Haskell', the implementation of <*> for lists is:

fs <*> xs = [f x | f <- fs, x <- xs]

Am I mistaken, or is this sugared monadic code based on >>= ?

As far as I understand, it should be possible to implement <*> only using fmap, as it is the case with applicative Maybe.

How could <*> for lists be implemented only using fmap? (and possibly without concat-ing things?)

BTW, a few pages later I see the same issue with regards to the implementation of <*> for applicative IO.

Answer 1

No, this is not sugared monadic code based on >>=. If it were, the definition of >>= in the Monad [] instance would be circular.

instance Monad []  where
    {-# INLINE (>>=) #-}
    xs >>= f             = [y | x <- xs, y <- f x]
    ...

The list comprehensions are syntactic sugar for let, if, and concatMap. From the Haskell Report:

[  e | b,          Q ] = if  b     then [ e | Q ] else []
[  e | let decls,  Q ] = let decls in   [ e | Q ]
[  e | p <- l,     Q ] = let ok p  =    [ e | Q ]
                             ok _  =    []
                         in concatMap ok l

The Monad [] instance is easy to define in terms of concatMap, but concatMap was defined in GHC.List (and is now possibly defined in Data.Foldable). Neither GHC.List nor Data.Foldable is imported into GHC.Base, so defining the Monad instance for lists in GHC.Base in terms of concatMap is impossible:

instance Monad [] where
    (>>=) = flip concatMap -- concatMap isn't imported

Defining these instances in terms of list comprehension gets around needing to import the module containing concatMap to reuse it defining >>=.

In GHC there are two implementations of list comprehensions. One rewrites them in terms of the GHC.Base build and foldr similar to the Data.Foldable concatMap. The other implementation generates recursive functions in place of concatMap as described by Wadler.

Answer 2

There are lots of cases where the Applicative instance is satisfied by monadic functions, I've seen

instance Applicative MyMonadThatIsAlreadyDefined where
    pure = return
    (<*>) = ap

Also, <*> can't be written using only fmap, at least not in general. That's the point of <*>. Try writing <*> in terms of just fmap, I'll be very surprised if you manage it (in such a way that is well behaved and follows the applicative laws). Remember that the chain is

Functor > Applicative > Monad

Where > can be thought of as superset. This is saying that the set of all functors contains the set of all applicatives, which contains the set of all monads. If you have a monad, then you have all the tools needed to use it as an applicative and as a functor. There are types that are functorial but not applicative, and types that are applicative by not monadic. I see no problem in defining the applicative instance in this manner.