Làm cách nào để kiểm tra các chức năng đa hình trên các ứng dụng?

Question

Tôi đã chỉ written a function (ví Data.Sequence)

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

mà nên tuân theo

traverseWithIndex f = sequenceA . mapWithIndex f 

Rất may, đây là một thay đổi cơ học đơn giản về nguồn gốc của mapWithIndex, vì vậy tôi khá tự tin đó là chính xác . Tuy nhiên, trong các trường hợp phức tạp hơn, việc kiểm tra kỹ lưỡng sẽ được yêu cầu. Tôi đang cố gắng viết một thuộc tính QuickCheck để kiểm tra cái đơn giản này. Rõ ràng, tôi không thể thử nó với mỗi f2tor Applicative! Khi thử nghiệm monoids, nó có ý nghĩa tốt để thử nghiệm với monoid miễn phí hơn (tức là, danh sách hữu hạn) một số loại. Vì vậy, nó có vẻ hợp lý ở đây để kiểm tra với free applicative functor trên một số functor. Có hai khó khăn:

1. Làm cách nào để chọn một hàm cơ sở thích hợp? Tôi có lẽ muốn một cái khó chịu mà không phải là ứng dụng hoặc đi qua hoặc bất cứ điều gì, nhưng một điều như vậy có vẻ khó làm việc với.

2. Làm cách nào để so sánh kết quả? Họ sẽ có chức năng trong họ, vì vậy họ không có trường hợp Eq.

Answer 1

Rõ ràng, tôi không thể thử nó ra với tất cả các Applicative functor!

Tôi nhớ lại bài đăng blog này hàng loạt, mà tôi sẽ không yêu cầu bồi thường hoàn toàn hiểu:

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

Bài học mà tôi nhớ lại rút ra từ điều này là gần như tất cả các functor ứng dụng bạn thấy trong tự nhiên hóa ra là thành phần, sản phẩm hoặc (bị hạn chế) coproduct của những người đơn giản như thế này (không có nghĩa là để được đầy đủ):

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

Vì vậy, khi bạn không thể dùng thử với mỗi Applicative functor, có lập luận quy nạp mà bạn có thể có thể khai thác trong các thuộc tính QuickCheck để có được sự tự tin rằng chức năng của bạn hoạt động cho các gia đình functors được xác định rõ ràng. Vì vậy, ví dụ: bạn có thể thử nghiệm:

• Chức năng của bạn hoạt động chính xác cho các ứng dụng "nguyên tử" do bạn chọn;
• Nếu chức năng của bạn hoạt động chính xác cho functors f và g, hoạt động chính xác cho Compose f g, Product f g và Coproduct f g.

Làm cách nào để so sánh kết quả?Họ sẽ có chức năng trong họ, vì vậy họ không có trường hợp Eq.

Vâng, tôi nghĩ bạn có thể phải xem xét kiểm tra QuickCheck về bình đẳng chức năng. Lần trước tôi phải làm điều gì đó dọc theo những dòng tôi đã đi với thư viện checkers của Conal, có an EqProp class cho "[t] ypes của các giá trị có thể được kiểm tra bình đẳng, có lẽ thông qua lấy mẫu ngẫu nhiên". Điều này sẽ cho bạn một ý tưởng - ngay cả khi bạn không có một cá thể Eq cho các hàm, QuickCheck có thể có khả năng chứng minh rằng hai hàm là không bằng nhau. Phê bình, trường hợp này tồn tại:

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

... và bất kỳ loại có một thể hiện Eq có một tầm thường EqProp dụ nơi (=-=) = (==).

Vì vậy, điều đó gợi ý, theo ý tôi, hãy sử dụng Coyoneda Something làm hàm cơ sở và tìm cách kết hợp tất cả các chức năng nhỏ.

Answer 2

Đây là giải pháp một phần (?). Các khía cạnh chính chúng tôi muốn kiểm tra là 1) rõ ràng là cùng một giá trị được tính toán, và 2) các hiệu ứng được thực hiện theo thứ tự như nhau. Tôi nghĩ rằng đoạn mã sau là tự giải thích đủ:

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

Kết quả trông giống như:

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