haskell - ZipList 可以是分布式的吗？

Question

基地提供ZipList ，它只是 [] 的包装器在哪里 <*>基于 zip而不是笛卡尔积。这不是默认值，因为它与 Monad [] 不一致。例如，但有些人觉得它更直观，而且这两种行为在不同的情况下都很有用。
Edward Kmett 提供 Distributive ，Traversable 的对偶. Traversable 可以映射/推送/分发到任何 Applicative Functor；可以从任何 Functor 中提取/分解分布。 (由于我没有解包的原因，distribute 不需要外层是 Applicative。)
Length-indexed lists are Distributive ，并按照您的预期工作。具体来说，他们的 Applicative 实例基于 zip , 就像 ZipList !这表明 ZipList也可以是 Distributive ，这将是有用的。Distributive 的文档请注意任何实例必须为真的两件事:

“对于某些 (->) x，它 [必须] 与 x 同构。”

列表与偏函数 Int -> 同构.

“[它]需要有一种方法来持续压缩可能无限数量的自身副本。”

这或多或少是ZipList 存在的理由。 .

这够好吗？今天下午我花了几个小时试图写 instance Distributive ZipList where distributive = ...并且无法让它发挥作用。对于大多数仿函数 f ZipList a distribute f 有明显的含义，尽管我担心这可能只是因为我没有考虑足够多的不可遍历仿函数。

Maybe很棘手；应该 distribute Nothing是 []或 repeat Nothing ?但是distribute与 sequenceA 是双重的，以及 Traversable Maybe实例说它应该是repeat Nothing .

(->) e可能是交易破坏者。

直觉 distribute $ const (repeat x) = repeat (const x) .

我们可以将其扩展到任何保证返回无限列表的函数；它看起来有点像 (\i -> (! i) <$> f) <$> [0..] .

我们可以将其扩展到返回有限列表的函数；我们最终得到一个无限的偏函数列表。这对我来说并不明显，这是 Not Acceptable 。使用列表时，部分函数会一直出现。

但这意味着 distribute $ const [] ≅ repeat undefined ，这有点傻。

实例 Applicative ZipList包含一个重要的设计决策:length (a <*> b) == min (length a) (length b) (而不是错误或其他)。我们根本没有利用它。我可以看到我们可能会是distribute = const [] .

有没有人看到前进的道路？
如果部分函数解释是“可接受的”，我们能否以比 distribute f = (\i -> (!! i) <$> f) <$> [0..] 更简单的方式对其进行概括？ ?

Answer 1

不，它不能是分布式的。
明显的Distributive Pair 的实例看起来像这样:

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"

这是一个问题，因为列表的 (<$>)保留长度，在这里我们要求它在提供相同参数时返回两个不同长度的答案。哎呀!
作为替代方案，您可能对 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))