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

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

H O L E S

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

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

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

接下来，实例Traversable。 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 ...)

（我已经选择了类型和值的名称，以便一切都整齐排列。不要注意幕后的那个人。）现在是时候的问题了：如何创造一个 [=20= 的值] 给定其他一切。我们知道

构造Compose t u b的唯一方法是创建一个值t (u b)。
除了 (1) pure 和 (2) fmap 之外，没有办法产生 f anything 的值，而且凭直觉我们知道我们不能使用 pure 因为我们试图在这里收集 a2fb :: a -> f b 的 'side effects'。

这引导我们找到下一个解决方案。

λ> 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)

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

Traversable instance for general type composition

haskell

types

composition

H O L E S