haskell - 实现 `traverse` 和 `sequenceA`

Question

我正在尝试自己实现 traverse 和 sequenceA:

这是我在 sequenceA 方面的 traverse' 实现:

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse' f x = sequenceA' $ fmap f x 

但是，我坚持实现 sequenceA。

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' x = foldr (\a _ -> fmap helper a) (error "...") x

我为 b 使用了占位符(error "...") - 我不确定如何创建给定的 b这些类型。

helper :: (Functor t, Foldable t) => a -> t a
helper x = error "TODO"

另外，我使用 helper 函数来获取此代码以进行类型检查。但是，同样，这只是一个 error 调用。请给我一个关于如何通用实现 sequenceA 的提示。

Answer 1

给定:

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse' a2fb ta = sequenceA' (fmap a2fb ta)

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' tfa = _

孔的理想用途!我们给我们所有的参数命名(不需要无意义地让我们的生活变得困难)，并在定义应该存在的地方留下一个洞。这产生:

src/Main.hs:8:14: Found hole ‘_’ with type: f (t a) …

我们现在转换一个返回类似 f (t a) 的函数。幸运的是，traverse' 确实如此，现在我们可以将我们的漏洞改进为:

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' tfa = traverse _ _

src/Main.hs:8:27: Found hole ‘_’ with type: a0 -> f a …
src/Main.hs:8:29: Found hole ‘_’ with type: t a0 …

第一个看起来很乱，但我们知道适合第二个的 t a0 的东西，即我们的 tfa。即插即用:

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' tfa = traverse _ tfa

src/Main.hs:8:27: Found hole ‘_’ with type: f a -> f a …

嗯，我们知道一个具有该签名的函数，那就是 id。所以我们最终的答案是:

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse' a2fb ta = sequenceA' (fmap a2fb ta)

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' tfa = traverse id tfa

我们现在可以变得年轻、狂野和无点(-ish):

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse' a2fb = sequenceA' . fmap a2fb

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' = traverse id

Which matches the definitions in Prelude. ～洞～