Documentation.SBV.Examples.ProofTools.Sum

Example inductive proof to show partial correctness of the traditional for-loop sum algorithm:

    s = 0
    i = 0
    while i <= n:
       s += i
       i++

We prove the loop invariant and establish partial correctness that s is the sum of all numbers up to and including n upon termination.

System state

data S a

System state. We simply have two components, parameterized over the type so we can put in both concrete and symbolic values.

Constructors

S

Fields

• s :: a
• i :: a
• n :: a

Instances

Functor S

Defined in Documentation.SBV.Examples.ProofTools.Sum

Methods

fmap :: (a -> b) -> S a -> S b

(<$) :: a -> S b -> S a

Foldable S

Defined in Documentation.SBV.Examples.ProofTools.Sum

Methods

fold :: Monoid m => S m -> m

foldMap :: Monoid m => (a -> m) -> S a -> m

foldMap' :: Monoid m => (a -> m) -> S a -> m

foldr :: (a -> b -> b) -> b -> S a -> b

foldr' :: (a -> b -> b) -> b -> S a -> b

foldl :: (b -> a -> b) -> b -> S a -> b

foldl' :: (b -> a -> b) -> b -> S a -> b

foldr1 :: (a -> a -> a) -> S a -> a

foldl1 :: (a -> a -> a) -> S a -> a

toList :: S a -> [a]

null :: S a -> Bool

length :: S a -> Int

elem :: Eq a => a -> S a -> Bool

maximum :: Ord a => S a -> a

minimum :: Ord a => S a -> a

sum :: Num a => S a -> a

product :: Num a => S a -> a

Traversable S

Defined in Documentation.SBV.Examples.ProofTools.Sum

Methods

traverse :: Applicative f => (a -> f b) -> S a -> f (S b)

sequenceA :: Applicative f => S (f a) -> f (S a)

mapM :: Monad m => (a -> m b) -> S a -> m (S b)

sequence :: Monad m => S (m a) -> m (S a)

Queriable IO (S SInteger)

'Queriable instance for our state

Defined in Documentation.SBV.Examples.ProofTools.Sum

Associated Types

type QueryResult (S SInteger)

Defined in Documentation.SBV.Examples.ProofTools.Sum

type QueryResult (S SInteger) = S Integer

Methods

create :: QueryT IO (S SInteger)

project :: S SInteger -> QueryT IO (QueryResult (S SInteger))

embed :: QueryResult (S SInteger) -> QueryT IO (S SInteger)

Show a => Show (S a)

Defined in Documentation.SBV.Examples.ProofTools.Sum

Methods

showsPrec :: Int -> S a -> ShowS

show :: S a -> String

showList :: [S a] -> ShowS

type QueryResult (S SInteger)

Defined in Documentation.SBV.Examples.ProofTools.Sum

type QueryResult (S SInteger) = S Integer

sumCorrect :: IO (InductionResult (S Integer))

Encoding partial correctness of the sum algorithm. We have:

>>> sumCorrect
Q.E.D.