haskell - 了解(可遍历产品)类型

Question

鉴于 fp-course 中的以下内容:

data Product f g a =
  Product (f a) (g a)

class Functor f where
  -- Pronounced, eff-map.
  (<$>) ::
    (a -> b)
    -> f a
    -> f b

class Functor f => Applicative f where
  pure ::
    a -> f a
  (<*>) ::
    f (a -> b)
    -> f a
    -> f b

我试图为 Product f g a 定义 Traversable 实例:

instance (Traversable f, Traversable g) =>
  Traversable (Product f g) where
  traverse :: 
    Applicative h =>
    (a -> h b)
    -> Product f g a
    -> h (Product f g b)  
  traverse fn (Product fa ga) = Product (traverse fn fa) (traverse fn ga)

编译器显示错误:

src/Course/Traversable.hs:106:33: error:
    • Occurs check: cannot construct the infinite type: h ~ Product h h
      Expected type: h (Product f g b)
        Actual type: Product h h (f b)

我明白我的定义怎么错了，但我不明白实际类型是Product h h (f b)。

拆分Product (traverse fn fa) (traverse fn ga)的类型，我相信是:

Product (h (f b)) (h (g b))

因为 traverse 的签名是 Applicative f => (a -> f b) -> t a -> f (t b)。

根据 Product h h (f b) 的实际类型，g 去了哪里？请解释以上实际类型。

Answer 1

是的。你有

traverse :: (a -> h b) -> f a -> h (f b)
traverse    fn            fa  :: h (f b)   -- and,

traverse :: (a -> h b) -> g a -> h (g b)
traverse    fn            ga  :: h (g b)

因此

Product (traverse fn fa)  (traverse fn ga) :: Product h h (f b)
        (h        (f b))  (h        (g b))

其中等效 f b ~ g b 即 f ~ g 已被强制执行， 因为 Product p q t 已定义作为

Product (p        t    )  (q        t    )
------------------------------------------
       p ~ h   t ~ f b    q ~ h    t ~ g b

所以简单地将 Product 应用于两个 traverse 结果并没有成功。

但是两者都有h(f b)和h(g b)类型，而h是一个Applicative，我们寻求创建类型 h (Product f g b) 与 combined 类型 在 h 内部的结果，所以如果仅我们可以

         h (f b)           h (g b)              h r              h s
        ---------------------------            ----------------------
         h (Combined  (f b)  (g b))             h (Combined   r    s)

事实上，因为两个 b 是相同的，

        ---------------------------
         h (Combined   f      g b )

所以从 foo::r -> s -> t 我们想得到 bar::h r -> h s -> h t... 如果只有such a function ...

baz :: (Applicative h) => (r -> s -> t) -> (h r -> h s -> h t)

... 所以答案是 liftA2 Product (traverse fn fa) (traverse fn ga)，将数据构造函数 Product 应用于两次遍历的内部结果“在”(“在里面”，“在...的掩护下”)应用语:

         h r       h s
           r   ->    s   ->   t
        ------------------------
         h                    t