Haskell quickBatch:在mconcat上测试ZipList Monoid导致堆栈溢出 [英] Haskell quickBatch: Testing ZipList Monoid at mconcat results in stack overflow

问题描述

我为ZipList Semigroup和Monoid创建了孤立的实例.但是，当我在monoid上从quickBatch运行测试时，在mconcat测试中，出现了堆栈溢出错误.我该如何解决此错误?为什么会出现这样的错误?是由于 pure mempty 引起的，我不太了解，因为我主要是从HaskellBook第17章应用节17.8 ZipList Monoid中获得的?

i've created orphaned instances for ZipList Semigroup and Monoid. However, when I run the tests from quickBatch on monoid, at the mconcat test, there is a stack overflow error. How do I resolve this error? Why is there such an error? Is it due to pure mempty, which I do not quite understand as I got this mostly from HaskellBook Chapter 17 Applicative section 17.8 ZipList Monoid?

zl :: ZipList (Sum Int)
zl = ZipList [1,1 :: Sum Int]
instance Semigroup a 
  => Semigroup (ZipList a) where
    (<>) = liftA2 (<>)
instance (Eq a, Monoid a)
  => Monoid (ZipList a) where
    mempty = pure mempty 
    mappend = (<>)
    mconcat as = 
      foldr mappend mempty as
main :: IO ()
main = do 
  quickBatch $ monoid zl

推荐答案

是的，该错误是由于 pure mempty 引起的，但这并不意味着 pure mempty 是错误的.让我们先看看那里.

Yes, the error is due to pure mempty, but that doesn't mean pure mempty is wrong. Let's look there first.

看看定义 mempty = pure mempty 中涉及的类型很有帮助:

It helps a lot to look at the types involved in the definition mempty = pure mempty:

mempty :: ZipList a
mempty = (pure :: a -> ZipList a) (mempty :: a)

基本上，我们将使用 pure 操作从类型为 a <的 mempty 中创建一个 ZipList /code>.从这里查看

Basically, we're going to use the pure operation to create a ZipList out of the mempty of type a. It helps from here to look at the definition of pure for ZipList:

pure :: a -> ZipList a
pure x = ZipList (repeat x)

总共， ZipList a 的 mempty 将是一个 ZipList ，其中包含无限重复的 mempty 基础类型 a 的值.

In total, mempty for ZipList a is going to be a ZipList containing the infinitely repeating list of mempty values of the underlying type a.

返回到此错误.当您尝试在 ZipList(Sum Int)上运行测试 monoid 时，QuickCheck将测试一系列属性.

Back to this error you're getting. When you try to run the test monoid over ZipList (Sum Int), QuickCheck is going to test a sequence of properties.

• 前两个检查左标识和右标识属性.这些操作是生成类型为 x :: ZipList(Sum Int)的值，并验证 x<>mempty = mempty<>x = x .
• 第三个检查是否有两个值 x，y :: ZipList(Sum Int)，我们有 x mappend y = x<>y .
• 第四次检查是否对于任何值列表 x :: [ZipList(Sum Int)] ，将其折叠为 mappend 与 mconcat 对其进行编码.

• The first two check the left identity and right identity properties. What these do is generate values of type x :: ZipList (Sum Int) and verify that x <> mempty = mempty <> x = x.
• The third checks that for any two values x, y :: ZipList (Sum Int), we have that x mappend y = x <> y.
• The fourth checks that for any list of values x :: [ZipList (Sum Int)], folding these with mappend is the same as mconcating them.

在继续之前，必须特别注意的是，当我说任何值"时，我的意思是说QuickCheck正在使用所述类型的 Arbitrary 实例来生成该类型的值.此外， ZipList a 的 Arbitrary 实例与 [a] 的 Arbitrary 实例相同，但随后进行了包装在 ZipList 中.最后， [a] 的 Arbitrary 实例将永远不会生成无限列表(因为当您检查相等性时，它们会引起问题，例如进入无限循环或因此，这些对于任何值" ZipList(Sum Int)的类型也不会是无限的.

Before I continue, it's really important to note that when I say "for any value", I really mean that QuickCheck is using the Arbitrary instance of the said type to generate values of that type. Furthermore, the Arbitrary instance for ZipList a is the same as the Arbitrary instance for [a] but then wrapped in ZipList. Lastly, the Arbitrary instance for [a] will never produce an infinite list (because those will cause problems when you're checking for equality, like going into an infinite loop or overflowing the stack), so these "for any values" of type ZipList (Sum Int) will never be infinite either.

具体地说，这意味着QuickCheck将永远不会任意生成值 mempty :: ZipList a ，因为这是一个无限列表.

Specifically, this means that QuickCheck will never arbitrarily generate the value mempty :: ZipList a because this is an infinite list.

那为什么为什么前三遍却最后一遍却由于堆栈溢出而失败呢?在前三个测试中，我们永远不会尝试将无限列表与无限列表进行比较.让我们看看为什么不可以.

So why do the first 3 pass but the last one fails with a stack overflow? In the first three tests, we never end up trying to compare an infinite list to an infinite list. Let's see why not.

• 在前两个测试中，我们查看 x<>mempty == x 和 mempty<>x == x .在两种情况下， x 是我们的任意"商品之一.值，它永远不会是无限的，所以这种相等永远不会进入无限循环.
• 在第三个测试中，我们将生成两个有限的ZipLists x 和 y 和 mappend 一起.一切都将是无限的.
• 在第三种情况下，我们将生成一个ZipLists列表，并为该列表创建 mconcat .但是，如果列表为空会怎样?好吧， mconcat [] = mempty ，折叠一个空列表将生成 mempty .这意味着，如果将空列表生成为任意输入(完全有可能)，那么测试将尝试确认一个无限列表等于另一个无限列表，这将始终导致堆栈溢出或出现黑洞.

• In the first two tests, we're looking at x <> mempty == x and mempty <> x == x. In both cases, x is one of our "arbitrary" values, which will never be infinite, so this equality will never go into an infinite loop.
• In the third test, we're generating two finite ZipLists x and y and mappending them together. Nothing about this will be infinite.
• In the third case, we're generating a list of ZipLists and mconcatenating the list. But, what happens if the list is empty? Well, mconcat [] = mempty, and folding an empty list produces mempty. This means, if the empty list is generated as the arbitrary input (which is perfectly possible), then the test will try to confirm that an infinite list is equal to another infinite list, which will always result in a stack overflow or black hole.

如何解决此问题?我可以提出两种方法:

How can you fix this? I can come up with two methods:

1. 您可以为 ZipList 定义自己的 EqProp 版本，以便它仅比较列表的某些有限前缀上的相等性.这可能涉及制作一个新类型的包装器(也许 newtype MonZipList a = MonZipList(ZipList a))，派生一堆实例，然后手工编写一个 EqProp .这可能会起作用，但是有点不雅致.

1. You can define your own version of EqProp for ZipList so that it only compares equality on some finite prefix of the list. This would likely involve making a newtype wrapper (perhaps newtype MonZipList a = MonZipList (ZipList a)), deriving a bunch of instances, and then writing an EqProp one by hand. This will probably work but is a little inelegant.

您可以编写自己的 monoid 版本，该版本使用第四次测试的不同版本.例如，如果您限制它以使测试仅使用非空列表，则不会有任何问题.为此，您应该先查看 property mconcatP 其中

You can write your own version of monoid that uses a different version of the fourth test. For instance, if you restrict it so that the test only uses non-empty lists, then you won't have any problem. To do this, you should start by looking at the definition of the monoid property tests. Notice that it currently defines the "mconcat" property as property mconcatP where

mconcatP :: [a] -> Property
mconcatP as = mconcat as =-= foldr mappend mempty as

使用QuickCheck自己的 NonEmptyList 类，您可以将其重写为:

Using QuickCheck's own NonEmptyList class, you can rewrite this for your purposes as:

mconcatP :: NonEmptyList a -> Property
mconcatP (NonEmptyList as) = mconcat as =-= foldr mappend mempty as

显然，这是一个稍弱的情况，但至少它不会死机.

Obviously, this is a slightly weaker condition, but at least it's one that won't hang.

这篇关于Haskell quickBatch:在mconcat上测试ZipList Monoid导致堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！