Как я могу тестировать функции, полиморфные по сравнению с Применениями?

Я просто написал функцию (для Data.Sequence)

traverseWithIndex :: Applicative f => (Int -> a -> f b) -> Seq a -> f (Seq b)

который должен подчиняться

traverseWithIndex f = sequenceA . mapWithIndex f

К счастью, это простая механическая модификация источника mapWithIndex, поэтому я вполне уверен, что это правильно. Однако в более сложных случаях потребуется тщательное тестирование. Я пытаюсь написать свойство QuickCheck, чтобы проверить этот простой. Очевидно, я не могу попробовать это с каждым функтором Applicative! При тестировании моноидов имеет смысл протестировать со свободным моноидом (например, с конечными списками) какого-либо типа. Поэтому здесь кажется разумным протестировать с помощью свободный прикладной функтор над некоторым функтором. Есть две трудности:

Как выбрать подходящий базовый функтор? Я, по-видимому, хочу отвратительного, который не является аппликативным или доступным, или что-то еще, но с такой работой, похоже, трудно работать.
Как сравнить результаты? Они будут иметь в них функции, поэтому они не имеют экземпляра Eq.

Ответ 1

Очевидно, я не могу попробовать это с каждым функтором Applicative!

Мне напоминают эту серию блога, которую я не буду требовать, чтобы полностью понять:

Урок, который я вспоминаю из этого, состоит в том, что почти каждый прикладной функтор, который вы видите в дикой природе, оказывается композицией, продуктом или (ограниченным) копированием более простых, подобных им (не должен быть исчерпывающим):

Const
Identity
(->)

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

Ваша функция работает правильно для "атомных" аппликаций по вашему выбору;
Если ваша функция работает правильно для функторов f и g, она корректно работает для Compose f g, Product f g и Coproduct f g.

Как сравнить результаты? Они будут иметь в них функции, поэтому они не имеют экземпляра Eq.

Ну, я думаю, вам, возможно, придется взглянуть на проверку QuickCheck для функции равенства. В прошлый раз мне пришлось что-то делать по этим строкам, я пошел с библиотекой Conal checkers, в которой a EqProp class для "[t] значений значений, которые могут быть проверены на равенство, возможно, путем случайной выборки". Это должно дать вам представление уже, даже если у вас нет экземпляра Eq для функций, QuickCheck может доказать, что две функции неравны. Критически этот экземпляр существует:

instance (Show a, Arbitrary a, EqProp b) => EqProp (a -> b)

... и любой тип с экземпляром Eq имеет тривиальный экземпляр EqProp, где (=-=) = (==).

Так что, на мой взгляд, использование Coyoneda Something в качестве базового функтора и выяснение того, как соединить все маленькие функции.

Ответ 2

Здесь - частичное (?) решение. Основные аспекты, которые мы хотим проверить: 1) очевидно, что одно и то же значение вычисляется, и 2) эффекты выполняются в том же порядке. Я думаю, что следующий код достаточно понятен:

{-# LANGUAGE FlexibleInstances #-}
module Main where
import Control.Applicative
import Control.Applicative.Free
import Data.Foldable
import Data.Functor.Identity
import Test.QuickCheck
import Text.Show.Functions -- for Show instance for function types

data Fork a = F a | G a deriving (Eq, Show)

toIdentity :: Fork a -> Identity a
toIdentity (F a) = Identity a
toIdentity (G a) = Identity a

instance Functor Fork where
    fmap f (F a) = F (f a)
    fmap f (G a) = G (f a)

instance (Arbitrary a) => Arbitrary (Fork a) where
    arbitrary = elements [F,G] <*> arbitrary

instance (Arbitrary a) => Arbitrary (Ap Fork a) where
    arbitrary = oneof [Pure <$> arbitrary, 
                       Ap <$> (arbitrary :: Gen (Fork Int)) <*> arbitrary]

effectOrder :: Ap Fork a -> [Fork ()]
effectOrder (Pure _) = []
effectOrder (Ap x f) = fmap (const ()) x : effectOrder f

value :: Ap Fork a -> a
value = runIdentity . runAp toIdentity

checkApplicative :: (Eq a) => Ap Fork a -> Ap Fork a -> Bool
checkApplicative x y = effectOrder x == effectOrder y && value x == value y

succeedingExample = quickCheck (\f x -> checkApplicative 
    (traverse (f :: Int -> Ap Fork Int) (x :: [Int])) 
    (sequenceA (fmap f x)))

-- note reverse
failingExample = quickCheck (\f x -> checkApplicative 
    (traverse (f :: Int -> Ap Fork Int) (reverse x :: [Int])) 
    (sequenceA (fmap f x)))

-- instance just for example, could make a more informative one
instance Show (Ap Fork Int) where show _ = "<Ap>"

-- values match ...
betterSucceedingExample = quickCheck (\x -> 
    value (sequenceA (x :: [Ap Fork Int])) 
 == value (fmap reverse (sequenceA (reverse x))))

-- but effects don't.
betterFailingExample = quickCheck (\x -> checkApplicative 
    (sequenceA (x :: [Ap Fork Int])) 
    (fmap reverse (sequenceA (reverse x))))

Результат выглядит следующим образом:

*Main Text.Show.Functions> succeedingExample             
+++ OK, passed 100 tests.                                
*Main Text.Show.Functions> failingExample                
*** Failed! Falsifiable (after 3 tests and 2 shrinks):   
<function>                                               
[0,1]               
*Main Text.Show.Functions> betterSucceedingExample
+++ OK, passed 100 tests.
*Main Text.Show.Functions> betterFailingExample
*** Failed! Falsifiable (after 10 tests and 1 shrink):
[<Ap>,<Ap>]