可穿越和拉链.必要性和充足性

Question

每一种类型牛逼超载Traversable的带来了一个拉链牛逼.即Traversable T实例的存在是Zipper T的充分条件.

有证据证明这也是一个必要条件吗？(我想它一定是非常微不足道的,但到目前为止我还没有找到拉链的正式的一般定义.)

Answer 1

每个Traversable仿函数都是一个容器,其元素位置有限.为了在每个元素上组合计算效果,必须只有有限的许多.因此,例如,无限Stream仿函数不是可遍历的,因为没有办法提供可靠的函数Maybe.我们需要

sequence :: Stream (Maybe x) -> Maybe (Stream x)

但如果你想检查流中的所有内容是否成功,你将需要等待很长时间.

拉链对应于识别特定元素位置的能力(这进一步导致与衍生物的联系,但这是另一个故事).为了能够将元素插回其孔中,您需要一种有效的方法来确定位置上的相等性.如果你只有有限的多个位置,那一定是真的(在没有信息隐藏的情况下).因此,Traversable对于拥有Zipper来说当然足够了.

但是,没有必要.Stream有一个完全合理的拉链

type StreamContext x = ([x], Stream x)
type StreamZipper x = (StreamContext x, x)

它表示上下文是在所选元素之前的有限(ok,ok,add a bang或two)列表和在它之后的无限流.

无限的位置Stream是自然数.自然数字具有可判定的平等性,但其中有许多是无关紧要的.

tl; dr有限意味着可数,但反之亦然.