2016-05-19 47 views
5

Chcę realizować regularne aplikacyjny instancję dla list, używając mojego customly zdefiniowaną listę:aplikacyjnych instancja listy przebiega zawsze w teście prawa kompozycja z QuickCheck/Warcaby

import Control.Monad 

import Test.QuickCheck 
import Test.QuickCheck.Checkers 
import Test.QuickCheck.Classes 

data List a = 
    Nil 
    | Cons a (List a) 
    deriving (Eq, Ord, Show) 


instance Functor List where 
    fmap f (Cons x xs) = Cons (f x) (fmap f xs) 
    fmap f Nil = Nil 


instance Applicative List where 
    pure x = Cons x Nil 
    (<*>) Nil _ = Nil 
    (<*>) _ Nil = Nil 
    (<*>) (Cons f fs) xs = (+++) (fmap f xs) (fs <*> xs) 

(+++) :: List a -> List a -> List a 
(+++) (Cons x Nil) ys = Cons x ys 
(+++) (Cons x xs) ys = Cons x xs' 
    where xs' = (+++) xs ys 

instance Arbitrary a => Arbitrary (List a) where 
    arbitrary = sized go 
    where go 0 = pure Nil 
      go n = do 
      xs <- go (n - 1) 
      x <- arbitrary 
      return (Cons x xs) 

instance (Eq a) => EqProp (List a) where 
    (=-=) = eq 

main = do 
    let trigger = undefined :: List (Int, String, Int) 
    quickBatch $ applicative trigger 

Mój kod przechodzi wszelkie aplikacyjnych testy w warcaby z wyjątkiem jednej, ustawy o składzie. Żaden błąd nie występuje podczas testowania prawa kompozycji, po prostu nigdy się nie kończy.

Czy mój kod powtarza się wiecznie w jakiś sposób, którego nie jestem w stanie zobaczyć, czy też jest on bardzo powolny w testowaniu prawa kompozycyjnego?

To jest komunikat o błędzie pojawia gdybym Ctrl-C podczas wykonywania Warcaby:

applicative: 
    identity:  +++ OK, passed 500 tests. 
    composition: *** Failed! Exception: 'user interrupt' (after 66 tests): 
Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> Nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) 
Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> (Cons <function> Nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) 
Cons (-61) (Cons (-24) (Cons 56 (Cons (-10) (Cons 28 (Cons 5 (Cons (-5) (Cons 33 (Cons 18 (Cons 47 (Cons 43 (Cons 43 (Cons (-58) (Cons 35 (Cons (-52) (Cons (-52) (Cons (-41) (Cons 3 (Cons (-7) (Cons (-53) (Cons (-22) (Cons (-20) (Cons (-12) (Cons 46 (Cons (-53) (Cons 35 (Cons (-31) (Cons (-10) (Cons 43 (Cons (-16) (Cons 47 (Cons 53 (Cons 22 (Cons 8 (Cons 1 (Cons (-64) (Cons (-39) (Cons (-57) (Cons 34 (Cons (-31) (Cons 20 (Cons (-39) (Cons (-47) (Cons (-59) (Cons 15 (Cons (-42) (Cons (-31) (Cons 4 (Cons (-62) (Cons (-14) (Cons (-24) (Cons 47 (Cons 42 (Cons 61 (Cons 29 (Cons (-25) (Cons 30 (Cons (-20) (Cons 16 (Cons (-30) (Cons (-38) (Cons (-7) (Cons 16 (Cons 19 (Cons 20 Nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) 
    homomorphism: +++ OK, passed 500 tests. 
    interchange: +++ OK, passed 500 tests. 
    functor:  +++ OK, passed 500 tests. 

Jeśli jedna z funkcji jest powolna, myślę, że jest (+++), ale nie wiem jak GHC wykonuje kod wystarczająco dobrze, aby zrozumieć, dlaczego.

Aktualizacja:

Prawo skład jest:

pure (.) <*> u <*> v <*> w = u <*> (v <*> w) 

Które mogę pokazać prace z mojego kodu dla prostych przykładów:

Cons (+1) Nil <*> (Cons (*2) Nil <*> Cons 1 (Cons 2 (Cons 3 Nil))) 

i

pure (.) <*> Cons (+1) Nil <*> Cons (*2) Nil <*> Cons 1 (Cons 2 (Cons 3 Nil)) 

Both daj to samo Rezultat, dlaczego więc ustawa o kompozycji nigdy się nie kończy, wprawia mnie w zakłopotanie. Może to być problem z biblioteką checkers?

+2

Być może rozmiar list, które generujesz, jest zbyt duży? Co się stanie, jeśli otoczysz generatory przez [resize] (http://hackage.haskell.org/package/QuickCheck-2.8.2/docs/Test-QuickCheck.html#v: resize), określając mały rozmiar? – danidiaz

+3

Używanie 'List (Bool, Bool, Bool)' wykonano dla mnie w około 5 minut. – ErikR

+0

Jeśli nie ma rozwiązań, po prostu przyjmuję odpowiedź z działającą instancją aplikacyjną. –

Odpowiedz

2

Moja pierwsza myśl była taka, że ​​go otrzymywał ujemny argument i zapętlanie. Jednak podczas modyfikowania go do użycia trace i zgłaszania błędu, jeśli n < 0, okazało się, że jest o wiele prostsze: Twój kod jest naprawdę wolny.

Oto część I zmodyfikowany (go' został wykorzystany do śledzenia, ale zwarte to dla benchmarkingu):

import Debug.Trace 

(+++) :: List a -> List a -> List a 
{-# INLINE (+++) #-} 
(+++) (Cons x Nil) ys = Cons x ys 
(+++) (Cons x xs) ys = Cons x xs' 
    where xs' = (+++) xs ys 

maxListSize = 10 

instance Arbitrary a => Arbitrary (List a) where 
    arbitrary = sized go'' 
    where 
     go'' n = go' $ mod n maxListSize 
     go' n = if n < 0 then error ("bad n:" ++ show n) else trace (show n ++ " , ") $ go n 
     go 0 = pure Nil 
     go n = do 
     xs <- go' (n - 1) 
     x <- arbitrary 
     return (Cons x xs) 

Sprawdzanie ślad na jakiejś nieskończonej pętli, stwierdziliśmy, że rzeczy nigdy nie przestał postępuje, n zmniejszał się, a następnie pojawiał się z powrotem do następnego testu. Po zwolnieniu tempa wystarczyło jeden test, aby uzyskać pojedynczy test. Pamiętaj, że próbujesz uruchomić 500 z każdego testu.

Moi benchmarki nie są rygorystyczne, ale oto co mam (x jest moduł, w zakresie [1..18]):

Time Plot (x is modulus, y is seconds)

Szybkie regresji stwierdzono 5.72238 - 2.8458 x + 0.365263 x^2. Kiedy przeprowadziłem śledzenie, liczba wzrastała. Chociaż nie jestem pewien, w jaki sposób testy są uruchamiane, jeśli każdy z nich zwiększy się o n, wówczas uzyska on n aż do 500.

Formuła nie jest naprawdę uczciwa, ale załóżmy, że to przyzwoite ograniczenie. (Myślę, że tak powinno być, ponieważ algorytm to O(n^2).)

Następnie uruchomienie wszystkich testów zajęłoby około 25 godzin na moim komputerze.

P.S. Ponieważ wszystkie testy przechodzą na rozsądne granice na n i nie mogę znaleźć błędu, myślę, że twój kod jest poprawny.

+0

Twoja odpowiedź jest dobra, dziękuję. Czy trudno jest dowiedzieć się, która część mojego kodu jest wolna? Myślę, że mój kod jest bardzo prosty i nie widzę innego sposobu, aby to zrobić. Jeśli masz instancję aplikacyjną dla listy, która działa, byłbym wdzięczny, gdybyś mógł ją dodać, ponieważ nie mogłem znaleźć jej na SO. A kiedy mówisz, że mój kod to 'O (n^2)', masz na myśli 'O (| funkcje | * | elementy |)' z '(<*>) funkcje elementów' lub czy to naprawdę' O (| elementy |^2) '? –

+1

'O (| fs = funkcje | * | es = elementy |)', ponieważ 'fmap fx' to' O (| x |) ',' x +++ y' to 'O (| x |)', 'O (fs <*> xs) = O (| xs |) + O (ogon fs <*> xs)'. Grałem z kilkoma optymalizacjami, a następ- nie skracałem czas o więcej niż '50%': wstawianie 'fmap, (<*>), (+++), arbitralne'. Jeśli jesteś ciekawy dlaczego 'Applicative []' jest o wiele szybszy, spójrz na źródło 'GHC.Base' i [ta dyskusja] (http://comments.gmane.org/gmane.comp.lang.haskell. biblioteki/23298). Gdzieś w źródle jest 'Note: [List understand and inlining]', ale nie znalazłem go. –

+0

Utrzymanie tego otwarte do piątku, i daje nagrodę, jeśli nie ma jeszcze lepszych odpowiedzi. Dzięki jeszcze raz. –