Haskell quickBatch: тестирование ZipList Monoid в mconcat приводит к переполнению стека
Я создал бесхозные экземпляры для 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
Ответы
Да, ошибка вызвана pure mempty
, но это не значит, что pure mempty
это неправильно. Давайте сначала посмотрим туда.
Очень помогает взглянуть на типы, участвующие в определении mempty = pure mempty
:
mempty :: ZipList a
mempty = (pure :: a -> ZipList a) (mempty :: a)
По сути, мы собираемся использовать pure
операцию для создания ZipList
объекта out of the mempty
type a
. Отсюда будет полезно взглянуть на определение pureforZipList :
pure :: a -> ZipList a
pure x = ZipList (repeat x)
В общем, mempty
for 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
mappendy = 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
. Это означает, что если пустой список сгенерирован как произвольный ввод (что вполне возможно), тогда тест попытается подтвердить, что бесконечный список равен другому бесконечному списку, что всегда будет приводить к переполнению стека или черной дыре.
Как это исправить? Я могу придумать два метода:
Вы можете определить свою собственную версию
EqProp
for,ZipList
чтобы она сравнивала равенство только для некоторого конечного префикса списка. Скорее всего, это потребует создания оболочки newtype (возможноnewtype MonZipList a = MonZipList (ZipList a)
), создания группы экземпляров и последующего написанияEqProp
одного вручную. Это, вероятно, сработает, но немного неэлегантно.Вы можете написать свою собственную версию
monoid
, использующую другую версию четвертого теста. Например, если вы ограничите его так, чтобы в тесте использовались только непустые списки, у вас не будет никаких проблем. Для этого вам следует начать с определения monoidтестов свойств . Обратите внимание, что в настоящее время он определяет свойство «mconcat» какproperty mconcatP
where
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
Очевидно, это чуть более слабое условие, но, по крайней мере, оно не зависнет.