遍历数据

Question

我听说这个结构被宽泛地描述为"数据中表示的遍历,应用于某些结构,而不需要应用程序"

它可以定义为:

data X a b r =
    | Done r
    | Step a (X a b (b -> r))

单词描述如下:

• 该类型X a b r描述了结构的形状
• 其中包含类型的东西 a
• 每个人都有a机会生产出类型的东西b
• 如果你为每个人这样做a,
• 你得到的东西类型r.

因此,列表的"遍历" [a]具有类型X a b [b],因为如果您可以将每个a列表转换为a,b那么您将得到一个[b].

我的问题是:这个叫做什么？是否有关于它的更多信息的参考？

---

用法示例:

instance Functor (X a b) where
  fmap f (Done r) = f r
  fmap f (Step a next) = Step a (fmap (f .) next)

f :: [a] -> X a b [b]
f [] = Done []
f (a:as) = Step a (fmap (flip (:)) as)

g :: Applicative f => (a -> f b) -> X a b r -> f r
g f (Done r) = pure r
g f (Step a next) = g f next <*> f a

更普遍:

instance Applicative (X a b) where
  pure x = Done x
  Done f <*> y = fmap (\y -> f y) y
  Step a next <*> y = Step a (fmap flip next <*> y)

t :: Traversable t => t a -> X a b (t b)
t = traverse (\a -> Step a (Done id))

而且,假设我没有犯任何错误,我们应该发现:

flip g . t == traverse

---

编辑:我已经考虑过这个了.有一些不具备的东西traversal:a traversal可以将计算分成不是"一次一个"的东西,例如遍历二元树,可以"并行"遍历左右两半. "这是一个我认为具有同样效果的结构:

data Y a b r =
  | Done r
  | One a (b -> r)
  | forall s t. Split (Y a b s) (Y a b t) (s -> t -> r)

(语法略显模糊,因为我不记得它,也不想把它写成gadt)

f1 :: X a b r -> Y a b r
f1 (Done x) = Done x
f1 (Step a next) = Split (One a id) (f1 next) (flip ($))

f2 :: Y a b r -> X a b r
f2 (Done x) = Done x
f2 (One a f) = Step a (Done f)
f2 (Split x y f) = f <$> f2 x <*> f2 y