Come posso testare le funzioni polimorfiche su Applicativi?

Question

ho appena written a function (per Data.Sequence)

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

che dovrebbe obbedire

traverseWithIndex f = sequenceA . mapWithIndex f 

Per fortuna, questo è una modifica meccanica semplice della fonte di mapWithIndex, quindi sono abbastanza sicuro che sia corretta . Tuttavia, in casi più complessi sarebbero necessari test approfonditi. Sto cercando di scrivere una proprietà QuickCheck per testare questo semplice. Ovviamente, non posso provarlo con ogni funcion Applicative! Quando si testano i monoidi, ha senso testare con il monoide libero su (cioè gli elenchi finiti di) un certo tipo. Quindi sembra ragionevole testare con lo free applicative functor su qualche functor. Esistono due difficoltà:

1. Come scegliere un funtore di base appropriato? Presumibilmente voglio uno cattivo che non sia applicativo o attraversabile o altro, ma una cosa del genere sembra difficile da lavorare.

2. Come si confrontano i risultati? Avranno funzioni in loro, quindi non hanno l'istanza Eq.

Answer 1

Ovviamente, non posso provare con ogni Applicative funtore!

mi sono ricordato di questa serie di blog post, che non voglio pretendere di comprendere appieno:

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

La lezione che io ricordi attingendo questo è che quasi tutti i funtori applicativi che vedi in natura si rivelano essere la composizione, il prodotto o il coprodotto (limitato) di quelli più semplici come questi (non intesi per essere esaustivi):

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

Così, mentre non si può provare con ogni Applicative funtore, ci sono argomentazioni induttive che si può essere in grado di sfruttare in proprietà QuickCheck a acquisisci sicurezza che la tua funzione funzioni per famiglie di funtori di grandi dimensioni induttivamente definite. Ad esempio, puoi provare:

• La tua funzione funziona correttamente per gli applicativi "atomici" di tua scelta;
• Se la funzione funziona correttamente per i funtori f e g, funziona correttamente per Compose f g, Product f g e Coproduct f g.

Come si confrontano i risultati?Avranno funzioni in loro, quindi non hanno l'istanza Eq.

Bene, penso che potrebbe essere necessario esaminare il test QuickCheck dell'uguaglianza delle funzioni. L'ultima volta che ho dovuto fare qualcosa in questo senso sono andato con la libreria checkers di Conal, che ha an EqProp class per "[t] tipi di valori che possono essere testati per l'uguaglianza, magari attraverso il campionamento casuale." Questo dovrebbe darti un'idea, anche se non hai un'istanza Eq per le funzioni, QuickCheck potrebbe essere in grado di dimostrare che due funzioni non sono uguali. Criticamente, questo caso esiste:

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

... e qualsiasi tipo che dispone di un'istanza Eq ha un banale EqProp caso dove (=-=) = (==).

Quindi, a mio avviso, suggerisco di utilizzare Coyoneda Something come funtore di base e di capire come collegare tutte le piccole funzioni.

Answer 2

Ecco una soluzione parziale (?). Gli aspetti principali che vogliamo verificare sono 1) ovviamente lo stesso valore è calcolato, e 2) gli effetti sono eseguiti nello stesso ordine. Credo che il seguente codice si spiega da sé sufficiente:

{-# 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)))) 

L'output è simile:

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