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

Question

Я только written a function (для Data.Sequence)

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

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

traverseWithIndex f = sequenceA . mapWithIndex f 

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

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

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

Answer 1

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

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

• http://comonad.com/reader/2012/abstracting-with-applicatives/
• http://comonad.com/reader/2013/algebras-of-applicatives/

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

1. Const
2. Identity
3. (->)

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

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

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

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

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

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

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

Answer 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>]