How can i understand this Traversable implementation for lists

Question

I'm having trouble to understand the following example from the NICTA course:

instance Traversable List where
    traverse ::
        Applicative f =>
        (a -> f b)
        -> List a
        -> f (List b)
    traverse f =
        foldRight (\a b -> (:.) <$> f a <*> b) (pure Nil)

In what follows, I will replace List with [], so we have:

instance Traversable [] where
    traverse ::
        Applicative f =>
        (a -> f b)
        -> [a]
        -> f ([b])
    traverse f =
        foldRight (\a b -> (:) <$> f a <*> b) []

In particular, what's wrong with the following derivation of the type of (<*>)?

(:)    :: a -> [a] -> [a]
(<$>)   :: a -> b -> F a -> F b,   F for Functor

(therefore...)

(:) <$>  :: F a -> F ([a] -> [a])
f      :: a -> A b :: ((->) a) (A b),    A for Applicative

(therefore...)

(:) <$> f :: ((->) a) ([a] -> [a])
(:) <$> f a  :: [a] -> [a]
(<*>) :: A (a -> b) -> A a -> A b

Answer 1

what's wrong with the following derivation?

The problem is with this passage:

(:) <$> f :: ((->) a) ([a] -> [a])

Function application always has precedence over any operator, and so (:) <$> f a is not ((:) <$> f) a, as in your derivation, but (:) <$> (f a). The rest follows smoothly (you may want to try finishing it yourself before reading the solution below):

(:) <$>     :: F a -> F ([a] -> [a]) -- The third line of your derivation.
f           :: a -> A b
f a         :: A b
(:) <$> f a :: A ([b] -> [b])

(<*>)             :: A (a -> b) -> A a -> A b
(:) <$> f a       :: A ([b] -> [b])
(:) <$> f a <*>   :: A [b] -> A [b]
b                 :: A [b]
(:) <$> f a <*> b :: A [b]