一般类型组合的可遍历实例

Question

我完全坚持这是一个优秀的Haskell编程书的练习.

给定以下类型组合的新类型以及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.traverseghci抱怨的类型,我建议的解决方案看起来应该可行.我有一种模糊的感觉,它与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

HOLES

这是另一个可以通过多孔表达式解决的重要问题.

首先,我们假设我们已经定义了可折叠的实例.

?> 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 ...)

(我已经选择了类型和值名称,以便所有内容整齐排列.不要注意窗帘后面的人.)现在,小时的问题:如何让出一个f (Compose t u b)给定其他东西的价值.我们知道

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

• 没有办法产生f anything除(1)pure和(2)之外的值fmap,直觉上我们知道我们不能使用,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是Traversable所以让我们尝试遍历它.

?> 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是Traversable所以让我们尝试遍历它.

?> 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,你最终得到了解决方案.

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