sbv-10.2: SMT Based Verification: Symbolic Haskell theorem prover using SMT solving.

Copyright | (c) Levent Erkok
License | BSD3
Maintainer | erkokl@gmail.com
Stability | experimental
Safe Haskell | Safe-Inferred
Language | Haskell2010

Documentation.SBV.Examples.ProofTools.Sum

Contents

- System state

Description

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.

Synopsis

- data S a = S {
  - s :: a
  - i :: a
  - n :: a
  }
- sumCorrect :: IO (InductionResult (S Integer))

# System state

data S a Source #

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

Instances details

Foldable S Source # |

Instance details

Defined in Documentation.SBV.Examples.ProofTools.Sum

Methods

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

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

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

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

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

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

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

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

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

toList :: S a -> [a] Source #

null :: S a -> Bool Source #

length :: S a -> Int Source #

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

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

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

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

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

Traversable S Source # |
Instance details Defined in Documentation.SBV.Examples.ProofTools.Sum Methods traverse :: Applicative f => (a -> f b) -> S a -> f (S b) Source # sequenceA :: Applicative f => S (f a) -> f (S a) Source # mapM :: Monad m => (a -> m b) -> S a -> m (S b) Source # sequence :: Monad m => S (m a) -> m (S a) Source #
Functor S Source # |
Instance details Defined in Documentation.SBV.Examples.ProofTools.Sum Methods fmap :: (a -> b) -> S a -> S b Source # (<$) :: a -> S b -> S a Source #
Fresh IO (S SInteger) Source # | `Fresh` instance for our state
Instance details Defined in Documentation.SBV.Examples.ProofTools.Sum Methods fresh :: QueryT IO (S SInteger) Source #
Generic (S a) Source # |
Instance details Defined in Documentation.SBV.Examples.ProofTools.Sum Associated Types type Rep (S a) :: Type -> Type Source # Methods from :: S a -> Rep (S a) x Source # to :: Rep (S a) x -> S a Source #
Show a => Show (S a) Source # |
Instance details Defined in Documentation.SBV.Examples.ProofTools.Sum Methods showsPrec :: Int -> S a -> ShowS Source # show :: S a -> String Source # showList :: [S a] -> ShowS Source #
Mergeable a => Mergeable (S a) Source # |
Instance details Defined in Documentation.SBV.Examples.ProofTools.Sum Methods symbolicMerge :: Bool -> SBool -> S a -> S a -> S a Source # select :: (Ord b, SymVal b, Num b) => [S a] -> S a -> SBV b -> S a Source #
type Rep (S a) Source # |

Instance details

Defined in Documentation.SBV.Examples.ProofTools.Sum

type Rep (S a) = D1 ('MetaData "S" "Documentation.SBV.Examples.ProofTools.Sum" "sbv-10.2-H7C8tpOUfNc9yHFfX3krPk" 'False) (C1 ('MetaCons "S" 'PrefixI 'True) (S1 ('MetaSel ('Just "s") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: (S1 ('MetaSel ('Just "i") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Just "n") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a))))

sumCorrect :: IO (InductionResult (S Integer)) Source #

Encoding partial correctness of the sum algorithm. We have:

    >>> sumCorrect
    Q.E.D.