实例Haskell中的替代ZipList？ [英] instance Alternative ZipList in Haskell?
问题描述
- 没有好的实例吗？
- 那么下面提出的那个呢？
- 是否有瑕疵？
- 没用？
- 其他合理的可能性（如
Bool可以是两种方式的monoid），因此它们都不应该是 实例
我搜索了实例替代ZipList（用引号先找到代码）教程，讲座笔记，但没有实际的实例。
Matt Fenwick说，如果A是ZipList A，它将只是一个monoid。 请看这里。无论元素类型如何，列表都是单向链接。
AndrewC对同一问题的其他答案讨论了Alternative实例的外观。他说
Zip有两个明智的选择
[1,3,4]< |> Zip [10,20,30,40]：
Zip [1， 3,4]，因为它首先与Maybe一致
Zip [10,20,30,40]因为它是最长的 - 与Zip一致被丢弃
其中Zip基本上是ZipList。
我认为答案应该是 Zip [1,3,4,40] 。让我们来看一个实例：
instance A alternative Zip其中
empty = Zip []
Zip xs< |> Zip ys = Zip（go xs ys）其中
go [] ys = ys
go（x：xs）ys = x：go xs（drop 1 ys）
只有 Zip a 我们可以在不知道类型参数的情况下生成 a 是 Zip [] :: Zip a ，所以空。如果空列表是monoid的中性元素，我们可能会试图使用列表级联。但是，由于 drop 1 ， go 不是（++） $ C>。每当我们使用第一个参数列表中的一个条目时，我们就放弃其中一个。因此，我们有一种叠加：左边的参数列表隐藏了右边的一个（或全部）的开始。
[1,3,4,40] [10,20,30,40] [1,3,4] [1,3,4]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | | | | | | | |
[1,3,4] | [10,20,30,40] [] | | | [1，3，4]
[10,20,30,40] [1,3,4] [1,3,4] []
ziplists背后的一个直觉是过程：有限或无限的结果流。当压缩时，我们结合流，这是由Applicative实例反映的。当到达列表的末尾时，该流不会产生更多元素。这是替代实例派上用场的地方：我们可以命名一个替代品，一旦默认流程终止，就会接管替代品。
例如我们可以写 fmap Just foo< |> pure Nothing 将ziplist中的每个元素都包装成一个只需，并继续使用 foo code> Nothing 之后。生成的ziplist是无限的，在全部（实际）值用完后恢复为默认值。这当然可以通过在 Zip 构造函数中追加一个无限列表来完成。然而，上面的代码更优雅，并且不会假设构造函数的知识，从而导致代码的重用性更高。
我们不需要对元素类型进行任何假设幺半群本身）。同时，定义并不重要（因为（< |>）= const 会是）。它通过对第一个参数进行模式匹配来使用列表结构。
定义< |> 上面给出的是关联的，而空列表实际上是空的元素。我们有
Zip []< xs = fs * Zip [] = Zip []
（fs< |> gs）* xs = fs * xs< |> gs * xs
fs * （xs< |> | ys）= fs * xs< |> fs * ys
所以你可以要求的所有规则都满足了（列表连接并不是这样）。
这个实例和Maybe的一致：Choice偏向左边，但当左边的参数不能产生一个值时，正确的参数会接管。功能
zipToMaybe :: Zip a - >也许
zipToMaybe（Zip []）= Nothing
zipToMaybe（Zip（x：_））=只要x
maybeToZip ::也许a - > Zip a
maybeToZip Nothing = Zip []
maybeToZip（Just x）= Zip（repeat x）
$ （意味着 psi x< |> psi y = psi（x< y>）并且<$ c $ psi x * psi y = psi（x * y））。
编辑：对于一些 / 多个方法I 'd guess
某些（Zip z）= Zip（地图重复z）
许多（Zip z）= Zip （map repeat z ++ repeat []）
Tags / Indeces
有趣。一个不完全不相关的想法：ZipLists可以看作是普通列表，其元素由列表中的（增加）位置索引标记。压缩应用通过对等索引元素进行配对来加入两个列表。
试想一下列表中的元素标记为（非递减） Ord 值。 Zippery 应用程序会配对标记相同的元素，抛弃所有不匹配（它有其用处一>）; zippery alternative 可以对标签值执行顺序保留左偏好 union （常规列表中的替代方法也是一种联合）。
这完全符合您对索引列表（又名ZipLists）的建议。
所以是的，这是有道理的。流
值列表的一种解释是非确定性，这与列表的monad实例一致，但ZipLists可以是解释为按顺序组合的同步数值流。
通过这种流解释，您不会考虑整个列表，因此选择最长的流显然是作弊行为，并且正确地解释了从第一个ZipList到定义< |> 中的第二个，就像第一次完成时那样，就像你在实例中说的那样。
将两个列表压缩在一起并不仅仅是因为类型签名，而是对 当您将两个列表压缩在一起时，结果是两者中的最小值长度。这是因为这是可能的最长列表，符合类型签名而不使用⊥。这是一个错误，认为这是选择两种长度中较短的一种 - 这是最长的。 同样 ZipList comes with a Functor and an Applicative instance (Control.Applicative) but why not Alternative? I searched for "instance Alternative ZipList" (with the quotes to find code first) and only found the library, some tutorials, lecture notes yet no actual instance. Matt Fenwick said ZipList A will only be a monoid if A is. See here. Lists are monoids though, regardless of the element type. This other answer by AndrewC to the same question discusses how an Alternative instance might look like. He says There are two sensible choices for Zip
where Zip is basically ZipList.
I think the answer should be The only One intuition behind ziplists is processes: A finite or infinite stream of results. When zipping, we combine streams, which is reflected by the Applicative instance. When the end of the list is reached, the stream doesn't produce further elements. This is where the Alternative instance comes in handy: We can name a replacement, taking over as soon as the default process terminates. For example we could write We don't need any assumption on the element type (like being a monoid itself). At the same time the definition is not trivial (as The definition of so all the laws you could ask for are satisfied (which is not true for list concatenation). This instance is consistent with the one for Maybe: Choice is biased to the left, yet when the left argument is unable to produce a value, the right argument takes over. The functions are morphisms of alternatives (meaning Edit: For the
Interesting. A not completely unrelated thought: ZipLists can be seen as ordinary lists with elements tagged by their (increasing) position index in the list. Zipping application joins two lists by pairing equally-indexed elements. Imagine lists with elements tagged by (non-decreasing) This fully agrees with what you propose for indexed lists (aka ZipLists). So yes, it makes sense. One interpretation of a list of values is non-determinacy, which is consistent with the monad instance for lists, but ZipLists can be interpreted as synchronous streams of values which are combined in sequence. With this stream interpretation it's you don't think in terms of the whole list, so choosing the longest stream is clearly cheating, and the correct interpretation of failing over from the first ZipList to the second in the definition Zipping two lists together doesn't do this simply because of the type signature, but it's the correct interpretation of When you zip two lists together, the result is the minimum of the two lengths. This is because that's the longest possible list that meets the type signature without using ⊥. It's a mistake to think of this as picking the shorter of the two lengths - it's the longest possible. Similarly 这篇关于实例Haskell中的替代ZipList？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！< |> 。
最长可能列表
< |> 应该生成最长的列表，并且它应该更喜欢左侧列表。显然，它应该采取整个左侧列表，并采取正确的列表左停留保持同步/ zippiness。
Bool can be a monoid in two ways) and therefore neither should be the instance
[1,3,4] <|> Zip [10,20,30,40]:
Zip [1,3,4] because it's first - consistent with MaybeZip [10,20,30,40] because it's longest - consistent with Zip [] being discardedZip [1,3,4,40]. Let's see an instance:instance Aternative Zip where
empty = Zip []
Zip xs <|> Zip ys = Zip (go xs ys) where
go [] ys = ys
go (x:xs) ys = x : go xs (drop 1 ys)
Zip a we can produce without knowing the type argument a is Zip [] :: Zip a, so there is little choice for empty. If the empty list is the neutral element of the monoid, we might be tempted to use list concatenation. However, go is not (++) because of the drop 1. Every time we use one entry of the first argument list, we drop one of the second. Thus we have a kind of overlay: The left argument list hides the beginning of the right one (or all of it).[ 1, 3, 4,40] [10,20,30,40] [ 1, 3, 4] [ 1, 3, 4]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | | | | | | | |
[ 1, 3, 4] | [10,20,30,40] []| | | [ 1, 3, 4]
[10,20,30,40] [ 1, 3, 4] [ 1, 3, 4] []
fmap Just foo <|> pure Nothing to wrap every element of the ziplist foo into a Just and continue with Nothing afterwards. The resulting ziplist is infinite, reverting to a default value after all (real) values have been used up. This could of course be done by hand, by appending an infinite list inside the Zip constructor. Yet the above is more elegant and does not assume knowledge of constructors, leading to higher code reusability.(<|>) = const would be). It makes use of the list structure by pattern matching on the first argument.<|> given above is associative and the empty list really is the empty element. We have Zip [] <*> xs = fs <*> Zip [] = Zip []
(fs <|> gs) <*> xs = fs <*> xs <|> gs <*> xs
fs <*> (xs <|> ys) = fs <*> xs <|> fs <*> ys
zipToMaybe :: Zip a -> Maybe a
zipToMaybe (Zip []) = Nothing
zipToMaybe (Zip (x:_)) = Just x
maybeToZip :: Maybe a -> Zip a
maybeToZip Nothing = Zip []
maybeToZip (Just x) = Zip (repeat x)
psi x <|> psi y = psi (x <|> y) and psi x <*> psi y = psi (x <*> y)). some/many methods I'd guesssome (Zip z) = Zip (map repeat z)
many (Zip z) = Zip (map repeat z ++ repeat [])
Tags / Indeces
Ord values. Zippery application would pair-up equally-tagged elements, throwing away all mismatches (it has its uses); zippery alternative could perform order-preserving left-preferring union on tag values (alternative on regular lists is also kind of a union).Streams
<|> would be to do so on the fly as the first finishes, as you say in your instance.<|>.Longest Possible List
<|> should generate the longest possible list, and it should prefer the left list. Clearly it should take the whole of the left list and take up the right list where the left left off to preserve synchronisation/zippiness.
