Proving Equivalences

These are lecture notes from my Computer Science course. For learning about functional programming, in particular Haskell, I recommend Programming in Haskell.

We are asking the question How can we establish whether two functional expressions are equivalent (interchangeable)?

You can’t just test across a few results/arguments; there may be an infinite number of possible arguments.

Instead, you can use maths style proving like natural induction.

However a caveat to bear in mind; beware when doing integer division and shifting around dividers. For example this causes problems when doing integer division:

m / d + n / d  =  (m + n) / d

There is a similar law which does hold for + and /:

m / d + n = (m + n * d) / d
(+n).(/d) = (/d).(+n x d)

The second line states ‘adding n after dividing by d is the same as dividing by d after adding n and multiplying by d.

Never forget the undefined case when you are proving equivalence

This entry was posted in fun, lecture. Bookmark the permalink.