Haskell quickBatch: тестирование ZipList Monoid в mconcat приводит к переполнению стека

Jan 14 2021

Я создал бесхозные экземпляры для ZipList Semigroup и Monoid. Однако, когда я запускаю тесты из quickBatch на моноиде, в тесте mconcat возникает ошибка переполнения стека. Как мне исправить эту ошибку? Почему возникает такая ошибка? Это связано с тем pure mempty, что я не совсем понимаю, поскольку я получил это в основном из 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

Ответы

1 DDub Jan 18 2021 at 01:54

Да, ошибка вызвана pure mempty, но это не значит, что pure memptyэто неправильно. Давайте сначала посмотрим туда.

Очень помогает взглянуть на типы, участвующие в определении mempty = pure mempty:

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

По сути, мы собираемся использовать pureоперацию для создания ZipListобъекта out of the memptytype a. Отсюда будет полезно взглянуть на определение pureforZipList :

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

В общем, memptyfor ZipList aбудет ZipListсодержать бесконечно повторяющийся список memptyзначений базового типа a.


Вернемся к этой ошибке. При попытке запустить тест monoidчерез ZipList (Sum Int), QuickCheck собирается проверить последовательность свойств.

  • Первые два проверяют свойства левого и правого тождества. Что они делают, так это генерируют значения типа 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их вставке.

Прежде чем продолжить, очень важно отметить, что когда я говорю «для любого значения», я действительно имею в виду, что QuickCheck использует Arbitraryэкземпляр указанного типа для генерации значений этого типа. Кроме того, Arbitraryэкземпляр для ZipList aтакой же, как и Arbitraryдля, [a]но затем заключен в оболочку ZipList. Наконец, Arbitraryэкземпляр for [a]никогда не будет создавать бесконечный список (потому что это вызовет проблемы, когда вы проверяете равенство, например, переход в бесконечный цикл или переполнение стека), поэтому эти «для любых значений» типа ZipList (Sum Int)никогда не будут бесконечными либо.

В частности, это означает, что QuickCheck никогда не будет произвольно генерировать значение, mempty :: ZipList aпотому что это бесконечный список.


Так почему же первые 3 проходят, а последний не проходит из-за переполнения стека? В первых трех тестах мы никогда не пытаемся сравнить бесконечный список с бесконечным списком. Посмотрим, почему бы и нет.

  • В первых двух тестах мы рассматриваем x <> mempty == xи mempty <> x == x. В обоих случаях xэто одно из наших «произвольных» значений, которое никогда не будет бесконечным, поэтому это равенство никогда не перейдет в бесконечный цикл.
  • В третьем тесте мы формирующие два конечных ZipLists xи yи mappendИНГИ их вместе. Ничто в этом не будет бесконечным.
  • В третьем случае мы создаем список ZipLists и mconcatвносим его в список. Но что произойдет, если список пуст? Ну, mconcat [] = memptyи сворачивание пустого списка производит mempty. Это означает, что если пустой список сгенерирован как произвольный ввод (что вполне возможно), тогда тест попытается подтвердить, что бесконечный список равен другому бесконечному списку, что всегда будет приводить к переполнению стека или черной дыре.

Как это исправить? Я могу придумать два метода:

  1. Вы можете определить свою собственную версию EqPropfor, ZipListчтобы она сравнивала равенство только для некоторого конечного префикса списка. Скорее всего, это потребует создания оболочки newtype (возможно newtype MonZipList a = MonZipList (ZipList a)), создания группы экземпляров и последующего написания EqPropодного вручную. Это, вероятно, сработает, но немного неэлегантно.

  2. Вы можете написать свою собственную версию monoid, использующую другую версию четвертого теста. Например, если вы ограничите его так, чтобы в тесте использовались только непустые списки, у вас не будет никаких проблем. Для этого вам следует начать с определения monoidтестов свойств . Обратите внимание, что в настоящее время он определяет свойство «mconcat» как property mconcatPwhere

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

Используя собственный NonEmptyListкласс QuickCheck , вы можете переписать его для своих целей как:

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

Очевидно, это чуть более слабое условие, но, по крайней мере, оно не зависнет.