haskell - 我如何理解列表的 Traversable 实现

Question

我无法理解NICTA 课程中的以下示例：

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)

在下文中，我将替换List为[]，因此我们有：

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

特别是，以下类型的推导有什么问题(<*>)？

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

（所以...）

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

（所以...）

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

Answer 1

以下推导有什么问题？

问题在于这段话：

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

函数应用程序始终优先于任何运算符，因此(:) <$> f a不是((:) <$> f) a，如您的推导，而是(:) <$> (f a)。其余的顺利进行（您可能想在阅读下面的解决方案之前自己尝试完成它）：

(:) <$>     :: 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]