haskell - 通用类型组合的可遍历实例

Question

我完全被困在这是一个来自优秀Haskell Programming的练习。书。

给定以下类型组合的新类型以及 Functor 和 Applicative 的实例，编写一个 Traversable (Compose f g) 的实例。

newtype Compose f g a =
  Compose { getCompose :: f (g a) }
  deriving (Eq, Show)

instance (Functor f, Functor g) => Functor (Compose f g) where
  fmap f (Compose fga) = Compose $ (fmap . fmap) f fga

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
  pure = Compose <$> pure . pure
  Compose f <*> Compose x =
    Compose $ ((<*>) <$> f) <*> x

根据 traverse.traverse 的类型，我提出的解决方案看起来应该可行，但 ghci 提示。我有一种模糊的感觉，这与 Compose 构造函数中的重新包装有关:

instance (Traversable f, Traversable g) => Traversable (Compose f g) where
  traverse f1 (Compose fga) = (traverse.traverse) f1 fga

给出类型错误:

composing_types.hs:69:31:
    Couldn't match type ‘b’ with ‘g b’
      ‘b’ is a rigid type variable bound by
          the type signature for
            traverse :: Applicative f1 =>
                        (a -> f1 b) -> Compose f g a -> f1 (Compose f g b)
          at composing_types.hs:69:3
    Expected type: f1 (Compose f g b)
      Actual type: f1 (Compose f g (g b))
    Relevant bindings include
      fga :: f (g a) (bound at composing_types.hs:69:24)
      f1 :: a -> f1 b (bound at composing_types.hs:69:12)
      traverse :: (a -> f1 b) -> Compose f g a -> f1 (Compose f g b)
        (bound at composing_types.hs:69:3)
    In the expression: (traverse . traverse) f1 fga
    In an equation for ‘traverse’:
        traverse f1 (Compose fga) = (traverse . traverse) f1 fga

composing_types.hs:69:54:
    Couldn't match type ‘f’ with ‘Compose f g’
      ‘f’ is a rigid type variable bound by
          the instance declaration at composing_types.hs:68:10
    Expected type: Compose f g (g a)
      Actual type: f (g a)
    Relevant bindings include
      fga :: f (g a) (bound at composing_types.hs:69:24)
      traverse :: (a -> f1 b) -> Compose f g a -> f1 (Compose f g b)
        (bound at composing_types.hs:69:3)
    In the second argument of ‘traverse . traverse’, namely ‘fga’
    In the expression: (traverse . traverse) f1 fga

Answer 1

洞

这是另一个可以用洞表达式解决的好问题。

首先，假设我们已经定义了所有 Foldable 实例。

λ> instance (Foldable f, Foldable g) => Foldable (Compose f g) where
     foldr = undefined

接下来，实例可遍历。 Compose 参数上的模式匹配，因为您知道必须这样做，但否则一切都会陷入困境。

λ> instance (Traversable t, Traversable u) => Traversable (Compose t u) where
     traverse a2fb (Compose tua) = _ tua

GHC 将有助于指出错误 -

<interactive>:...:...
  Found hole ‘_’ with type: f (Compose t u b)

——除了范围内所有变量的类型之外。

Relevant bindings include
  tua :: t (u a) (bound at ...)
  a2fb :: a -> f b (bound at ...)
  traverse :: (a -> f b) -> Compose t u a -> f (Compose t u b)
    (bound at ...)

(我已经选择了类型和值名称，以便一切都排列整齐。不要注意幕后的人。)现在的问题是:如何构造 f 的值(Compose t u b) 考虑到其他一切。我们知道

• 构造 Compose t u b 的唯一方法是创建值 t (u b)。

• 除了 (1) pure 和 (2) fmap 之外，无法生成 f everything 的值，直觉上我们知道我们不能使用 pure 因为我们试图在这里收集 a2fb::a -> f b 的“副作用”。

这引导我们寻找解决方案的下一个尝试。

λ> instance (Traversable t, Traversable u) => Traversable (Compose t u) where
     traverse a2fb (Compose tua) =
       fmap Compose (_ tua)

<interactive>:...
  Found hole ‘_’ with type: t (u a) -> f (t (u b))

最后我们有了一个t。我们知道 t 是可遍历的，所以让我们尝试遍历它。

λ> instance (Traversable t, Traversable u) => Traversable (Compose t u) where
     traverse a2fb (Compose tua) =
       fmap Compose ((\tua -> traverse _ tua) tua)

<interactive>:56:138:
  Found hole ‘_’ with type: u a -> f (u b)

同样的交易。我们知道 u 是可遍历的，所以让我们尝试遍历它。

λ> instance (Traversable t, Traversable u) => Traversable (Compose t u) where
     traverse a2fb (Compose tua) =
       fmap Compose ((\tua -> traverse (\ua -> traverse _ ua) tua) tua)

<interactive>:57:155:
  Found hole ‘_’ with type: a -> f b

我们的a2fb的一个金凤花洞。

λ> instance (Traversable t, Traversable u) => Traversable (Compose t u) where
     traverse a2fb (Compose tua) =
       fmap Compose ((\tua -> traverse (\ua -> traverse a2fb ua) tua) tua)

Eta-reduce 删除 lambda，最终得到 the solution .

λ> instance (Traversable t, Traversable u) => Traversable (Compose t u) where
     traverse a2fb (Compose tua) =
       fmap Compose (traverse (traverse a2fb) tua)