我完全坚持这是一本出色的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
最佳答案
霍勒斯
这是另一个可以通过有洞的表达式解决的好问题。
首先，假设我们已经定义了所有可折叠实例。
λ> 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和(2)pure之外，没有其他方法可以生成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是可遍历的，因此让我们尝试遍历它。λ> 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)
关于haskell - 通用类型组合的可遍历实例，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36986859/