Автоматически получаемый Предоставляемый для предикатов по записям в SBV

Question

Я нахожусь в ситуации, когда у меня есть тип данных, как

data X = X {foo :: SInteger, bar :: SInteger}

и я хочу доказать, например,

forAll_ $ \x -> foo x + bar x .== bar x + foo x

используя ssv Haskell. Это не компилируется, потому что X -> SBool не является экземпляром Provable. Я могу сделать это, например, с

instance (Provable p) => Provable (X -> p) where
  forAll_ k = forAll_ $ \foo bar -> forAll_ $ k $ X foo bar
  forAll (s : ss) k =
    forAll ["foo " ++ s, "bar " ++ s] $ \foo bar -> forAll ss $ k $ X foo bar
  forAll [] k = forAll_ k
  -- and similarly `forSome_` and `forSome`

но это утомительно и подвержено ошибкам (например, использование forSome когда forAll должен был быть использован). Есть ли способ автоматического вывода Provable для моего типа?

Answer 1

По крайней мере, это можно сделать менее подверженным ошибкам:

onX :: (((SInteger, SInteger) -> a) -> b) -> ((X -> a) -> b)
onX f g = f (g . uncurry X)

instance Provable p => Provable (X -> p) where
    forAll_  = onX forAll_
    forSome_ = onX forSome_
    forAll   = onX . forAll
    forSome  = onX . forSome

Существует также обобщаемая модель, в случае, если существующих экземпляров SBV для 7-кортежей недостаточно.

data Y = Y {a, b, c, d, e, f, g, h, i, j :: SInteger}
-- don't try to write the types of these, you will wear out your keyboard
fmap10 = fmap . fmap . fmap . fmap . fmap . fmap . fmap . fmap . fmap . fmap
onY f g = f (fmap10 g Y)

instance Provable p => Provable (Y -> p) where
    forAll_  = onY forAll_
    forSome_ = onY forSome_
    forAll   = onY . forAll
    forSome  = onY . forSome

Тем не менее, все еще утомительно.

Answer 2

Даниэль ответит "как хорошо", если вы действительно хотите использовать квантификаторы напрямую с вашими лямбда-выражениями. Однако вместо создания Provable Например, я настоятельно рекомендую определить вариант free для вашего типа:

freeX :: Symbolic X
freeX = do f <- free_
           b <- free_
           return $ X f b

Теперь вы можете использовать это так:

test = prove $ do x <- freeX
                  return $ foo x + bar x .== bar x + foo x

Это намного проще в использовании и хорошо сочетается с ограничениями. Например, если ваш тип данных имеет дополнительное ограничение, что оба компонента положительны, а первый больше второго, тогда вы можете написать freeX Таким образом:

freeX :: Symbolic X
freeX = do f <- free_
           b <- free_
           constrain $ f .> b
           constrain $ b .> 0
           return $ X f b

Обратите внимание, что это будет работать правильно в обоих prove а также sat контексты, так как free знает, как правильно вести себя в каждом конкретном случае.

Я думаю, что это намного более читабельно и проще в использовании, даже если оно заставляет вас использовать do-нотацию. Вы также можете создать версию, которая принимает имена, например:

freeX :: String -> Symbolic X
freeX nm = do f <- free $ nm ++ "_foo"
              b <- free $ nm ++ "_bar"
              constrain $ f .> b
              constrain $ b .> 0
              return $ X f b

test = prove $ do x <- freeX "x"
                  return $ foo x + bar x .== bar x * foo x

Теперь мы получаем:

*Main> test
Falsifiable. Counter-example:
  x_foo = 3 :: Integer
  x_bar = 1 :: Integer

Вы также можете сделать X "разбирается" SBV. В этом случае полный код выглядит так:

data X = X {foo :: SInteger, bar :: SInteger} deriving Show

freeX :: Symbolic X
freeX = do f <- free_
           b <- free_
           return $ X f b

instance SatModel X where
  parseCWs xs = do (x, ys) <- parseCWs xs
                   (y, zs) <- parseCWs ys
                   return $ (X (literal x) (literal y), zs)

Следующий тест демонстрирует:

test :: IO (Maybe X)
test = extractModel `fmap` (prove $ do
                x <- freeX
                return $ foo x + bar x .== bar x * foo x)

У нас есть:

*Main> test >>= print
Just (X {foo = -4 :: SInteger, bar = -5 :: SInteger})

Теперь вы можете взять свои контрпримеры и постобработать их, как пожелаете.