Haskell: понимание QuickCheck с функцией высшего порядка

У меня есть функция foo:

foo :: [a] -> (a -> b) -> [b]
foo [] f = []
foo (x:xs) f = foo xs f

И следующие два свойства, которым он должен удовлетворять:

prop_1 :: [Int] -> Bool
prop_1 xs = foo xs id == xs 

prop_2 :: [Int] -> (Int -> Int) -> (Int -> Int) -> Bool
prop_2 xs f g = foo (foo xs f) g == foo xs (g . f)

Когда я попытался протестировать функцию с помощью quickCheck, я получил следующую ошибку:

 Ambiguous type variable 't0' arising from a use of '=='
      prevents the constraint '(Eq t0)' from being solved.
      Probable fix: use a type annotation to specify what 't0' should be.
      These potential instances exist:
        instance (Eq a, Eq b) => Eq (Either a b)
          -- Defined in 'Data.Either'
        instance Eq GeneralCategory -- Defined in 'GHC.Unicode'
        instance Eq Ordering -- Defined in 'ghc-prim-0.5.0.0:GHC.Classes'
        ...plus 24 others
        ...plus 107 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
      In the expression: foo (foo xs f) g == foo xs (g . f)
      In an equation for 'prop_2':
          prop_2 xs f g = foo (foo xs f) g == foo xs (g . f)
Failed, modules loaded: none.

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


functional-programming haskell quickcheck property-based-testing
person ceno980    schedule 28.06.2019    source источник
comment
Вы написали prop_2 в оболочке? Вы использовали :{ и :} для записи и подписи, и функции в одном блоке?   -  person Willem Van Onsem    schedule 28.06.2019
comment
Нет, у меня было prop_2 в файле с prop_1 и foo.   -  person ceno980    schedule 28.06.2019
comment
Похоже, что Haskell не может понять тип foo xs (g . f), так что это обычно означает, что сигнатуры типов не говорят, что здесь [Int].   -  person Willem Van Onsem    schedule 28.06.2019
comment
Можете ли вы поделиться компилируемым примером для воспроизведения проблемы?   -  person Li-yao Xia    schedule 28.06.2019
comment
Я попытался скомпилировать и запустить ваши свойства. Я не смог воспроизвести ваше сообщение об ошибке, но обнаружил две другие проблемы: во-первых, ваша функция foo эквивалентна const [], поэтому ваше первое свойство всегда будет давать сбой. Во-вторых, prop_2 не может быть запущен quickCheck, потому что нет экземпляра Show (Int -> Int) (это требуется для quickCheck, чтобы он мог печатать примеры счетчиков)   -  person sara    schedule 28.06.2019
comment
@sara: вторая проблема была рассмотрена в предыдущем вопросе: stackoverflow.com/questions/56805030/   -  person Willem Van Onsem    schedule 28.06.2019

Ответы (1)


arrow_upward
1
arrow_downward

Я смог продублировать ваше сообщение об ошибке с помощью следующей программы. Обратите внимание, что подпись для foo закомментирована:

import Test.QuickCheck
import Text.Show.Functions

-- foo :: [a] -> (a -> b) -> [b]
foo [] f = []
foo (x:xs) f = foo xs f

prop_1 :: [Int] -> Bool
prop_1 xs = foo xs id == xs

prop_2 :: [Int] -> (Int -> Int) -> (Int -> Int) -> Bool
prop_2 xs f g = foo (foo xs f) g == foo xs (g . f)

main = do
  quickCheck prop_1
  quickCheck prop_2

Если я верну подпись foo, проверка типов пройдет нормально. Тесты, конечно, терпят неудачу, поскольку foo не делает того, что вы от него хотите.

Проблема в том, что версия foo, которая у вас здесь, имеет предполагаемую подпись:

foo :: [a] -> b -> [c]

поэтому в prop_2 тип элементов списка для самых верхних вызовов foo не может быть выведен для разрешения правильной операции (==).

Если вы замените foo правильной версией:

foo :: [a] -> (a -> b) -> [b]
foo [] f = []
foo (x:xs) f = f x : foo xs f

затем тесты пройдены, и вы можете снова закомментировать подпись, потому что можно определить правильный тип.

person K. A. Buhr    schedule 28.06.2019