Generowanie list o określonej długości za pomocą QuickCheck Haskella

Question

-- 3 (find k"th element of a list) 
element_at xs x = xs !! x 
prop_3a xs x = (x < length xs && x >= 0) ==> element_at xs (x::Int) == (xs !! x::Int) 

Kiedy prop_3a przechodzi przez QuickCheck, to się poddaje, ponieważ nie generuje wystarczająco długich list.

Jak napisać generator, który wygeneruje listy o długości dłuższej niż losowa liczba całkowita?

Answer 1

Co powiesz na pójście w drugą stronę? Najpierw pozwalamy QuickCheck wybrać listę, a następnie ograniczamy to, które indeksy dopuszczamy. To działa i nie wyrzuca żadnych przypadków testowych.

prop_3a (NonEmpty xs) = forAll (choose (0, length xs - 1)) $ \i -> 
    element_at xs i == (xs !! i :: Int) 

Tutaj używam forAll do korzystania z konkretnego generatora dla indeksów, w tym przypadku z wykorzystaniem choose który odbierze element z określonego zakresu, a także używać the NonEmptyList type aby upewnić się, że nie staramy się indeksu do pustej listy.

Answer 2

to działa:

import Test.QuickCheck 

element_at  :: [a] -> Int -> a 
element_at xs i = xs !! i 

prop_3a  :: [Int] -> Int -> Property 
prop_3a xs i = (i >= 0) ==> (length xs > i) ==> element_at xs i == xs !! i 

Jednak problem polega na tym, że dużo wartości próbki są odrzucane. Można użyć rzeczy takich jak Positive, aby pomóc w zapewnieniu, że indeks jest ważny.

Jeśli chcesz być bardziej złożonym, możesz użyć większej liczby wrapperów typu newware, aby spróbować wygenerować wartości o wystarczającej długości (ewentualnie używając sized lub wygeneruj listę i indeks razem: wygeneruj listę, a następnie wygeneruj indeks na podstawie po długości listy).

Answer 3

Odpowiedź hammar jest całkowicie wystarczająca dla problemu. Ale aby odpowiedzieć na dokładne pytanie, nie mogłem nic na to poradzić. Użyjmy forAll.

prop_bang x = x >= 0 ==> forAll (listLongerThan x) $ \xs -> 
    element_at xs x == xs !! x 

Teraz potrzebujemy funkcji, listLongerThan :: Int -> Gen [Int]. Zajmuje długość x i generuje generator, który będzie tworzył listy o długości większej niż x.

listLongerThan :: Int -> Gen [Int] 
listLongerThan x = replicateM (x+1) arbitrary 

To raczej prosta: po prostu skorzystać z instancji Monad z Gen. Jeśli uruchomisz quickCheck prop_bang, zauważysz, że zaczyna to trwać dość długo, ponieważ rozpoczyna testowanie absurdalnie długich list. Ograniczmy długość listy, aby była nieco szybsza. Ponadto teraz tylko listLongerThan generuje listę o długości dokładnie x+1; Załóżmy, że mieszają się nieco, ponownie wykorzystując instancji monada gen

prop_bang = 
    forAll smallNumber $ \x -> 
    forAll (listLongerThan x) $ \xs -> 
    element_at xs x == xs !! x 

smallNumber :: Gen Int 
smallNumber = fmap ((`mod` 100) . abs) arbitrary 

listLongerThan :: Int -> Gen [Int] 
listLongerThan x = do 
    y <- fmap (+1) smallNumber -- y > 0 
    replicateM (x+y) arbitrary 

Można użyć sample smallNumber lub sample (listLongerThan 3) w ghci aby upewnić się, że jest generowanie prawidłowego rzeczy.