实现`traverse`和`sequenceA` [英] Implementing `traverse` and `sequenceA`

问题描述

我试图自己实现遍历和 sequenceA ：

这里是我对 sequenceA 的实现遍历'：

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

然而， m停留在执行 sequenceA 。

However, I'm stuck on implementing sequenceA.

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

我为 b （错误...） - 我不知道如何在给定这些类型的情况下创建 b 。

I used a placeholder for b (error "...") - I'm not sure how to create a b given these types.

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

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

Also, I used the helper function to get this code to type-check. But, again, that's simply an error call. Please give me a hint on how to generically implement sequenceA.

推荐答案

鉴于：
$ b

Given:

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 = _

孔的理想使用！我们给所有的参数命名（不需要无点关注并且让我们的生活变得困难），并且在定义应该存在的地方插入一个洞。这产生了：

An ideal use of holes! We give a name to all our parameters (no need to go pointfree and make our lives difficult just quite yet) and stick a hole where a definition should be. This yields:

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

我们现在转向一个返回类似于 f（ta）。幸运的是，遍历'并且现在我们可以改进我们的漏洞：

We now cast around for a function that returns something like f (t a). As luck would have it, traverse' does and now we can refine our hole to:

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 。即插即用：

That first one looks messy, but we know something that fits the t a0 for the second one, which is our tfa. Plug and chug:

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 。所以我们的最终答案是：

Well, we know of a function with that signature, and that's id. So our final answer is:

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

现在我们可以年轻化了， wild，and pointfree（-ish）：
$ b

We can now go young, wild, and pointfree(-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

这些与Prelude中的定义匹配。〜洞〜

这篇关于实现`traverse`和`sequenceA`的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！