ZipList 可以是分布式的吗？

Question

Base 提供 ZipList，它只是 [] 的包装器，其中 <*> 基于 zip 而不是笛卡尔积。这不是默认设置，因为它与 Monad [] 实例不一致，但有些人发现它更直观，并且这两种行为在不同的上下文中都很有用。

Edward Kmett 提供 Distributive，Traversable 的对偶。 Traversable 可以 mapped/pushed/distributed 进入任何 Applicative Functor； Distributive 可以是任何 Functor 中的 pulled/factored。（由于我没有解包的原因，distribute不要求外层是Applicative。）

Length-indexed lists are Distributive，按您期望的方式工作。具体来说，他们的Applicative实例是基于zip，就像ZipList一样！这表明 ZipList 也可以是 Distributive，这很有用。

Distributive 的文档指出了任何实例都必须满足的两点：

“对于某些 x，它 [必须] 与 (->) x 同构。”
- 列表同构于部分函数Int ->。
"[它] 需要有一种方法来始终如一地压缩其自身的可能无限数量的副本。"
- 这或多或少是 ZipList 的 存在理由。

这样够好吗？今天下午我花了几个小时试图写 instance Distributive ZipList where distributive = ... 但无法让它正常工作。对于 most 函子 f ZipList a 有明显的意义 distribute f，虽然我担心这可能只是因为我没有考虑足够 non -可遍历函子。

Maybe 很棘手； distribute Nothing 应该是 [] 还是 repeat Nothing？但是 distribute 是 sequenceA 的对偶，Traversable Maybe 实例说它应该是 repeat Nothing.
(->) e 可能是交易破坏者。
- 凭直觉distribute $ const (repeat x) = repeat (const x)。
- 我们可以将其扩展到任何保证 return 无限列表的函数；它看起来有点像 (\i -> (! i) <$> f) <$> [0..].
- 我们可以将 that 扩展到函数 returning 有限列表；我们最终得到无限的 partial 函数列表。这对我来说并不明显，这是不可接受的；使用列表时，部分函数总是出现。
- 但这意味着 distribute $ const [] ≅ repeat undefined，这有点傻。
- 实例 Applicative ZipList 包含一个重要的设计决策：length (a <*> b) == min (length a) (length b)（而不是错误或其他）。我们根本没有利用它；我能看到的方式可能是 distribute = const [].

有人看到前进的方向吗？

如果部分函数解释是“可接受的”，我们能否以比 distribute f = (\i -> (!! i) <$> f) <$> [0..] 更简单的方式概括它？

Answer 1

不，不能分配。

Pair 的明显 Distributive 实例如下所示：

instance Distributive Pair where
    distribute vs = Pair (pFst <$> vs) (pSnd <$> vs)

现在让我们考虑一下列表实例。（让我们暂时忽略 ZipList 噪音，假设基本列表有 zippy 实例。）我们需要 distribute . distribute = id。假设

x = distribute (Pair "" "a")

因此法律要求：

distribute x = Pair "" "a"

我们可以用distribute的定义代替Pair，得到：

Pair (pFst <$> x) (pSnd <$> x) = Pair "" "a"

这是一个问题，因为列表的 (<$>) 保留了长度，这里我们要求它 return 在提供相同参数时提供两个不同长度的答案。哎呀！

作为替代方案，您可能对 data Stream a = Cons a (Stream a) 类型的保证无限列表感兴趣，可以 Distributive:

sHead :: Stream a -> a
sHead (Cons a _) = a

sTail :: Stream a -> Stream a
sTail (Cons _ as) = as

instance Distributive Stream where
    distribute streams = Cons (sHead <$> streams) (distribute (sTail <$> streams))

ZipList 可以是分布式的吗？

Can ZipList be Distributive?

haskell

applicative

traversable