Discrete Mathematics for Computer Scientists -- Assignment 5

Discrete Mathematics for Computer Scientists -- Assignment 5 - Structural Induction

DIT980, HT 2017

Assignment Week 5 - Structural Induction

Assignments

(1.) Look at the following Haskell code:

  -- computes the sum of all numbers in the list
  sum :: [Integer] -> Integer
  sum []     = 0
  sum (x:xs) = x + sum xs  

  -- appends two lists
  (++) :: [Integer] -> [Integer] -> [Integer]
  []     ++ ys = ys
  (x:xs) ++ ys = x : (xs ++ ys)

Prove (by using structural induction) that the following equation holds, for all lists of integers xs and ys:

  sum (xs ++ ys) = sum xs + sum ys

Don't forget to state the I.H. in the induction step. Please also make sure you clearly state the reasons why you make the steps in your proofs.

(2.) Look at the following Haskell code:

  data Expr = Num Integer
            | Add Expr Expr
  
  -- evaluates the expression
  eval :: Expr -> Integer
  eval (Num n)   = n
  eval (Add a b) = eval a + eval b

  -- collects all numbers in the expression
  numbers :: Expr -> [Integer]
  numbers (Num n)   = [n]                 -- [n] is the same as n:[]
  numbers (Add a b) = numbers a ++ numbers b

(Note that the expression type only has two constructors: Num and Add; we have removed Mul for the sake of this assignment!)

Prove (by using structural induction) that the following equation holds, for all expressions x:

  sum (numbers x) = eval x

Don't forget to state the I.H. in the induction step. Please also make sure you clearly state the reasons why you make the steps in your proofs.

You may need a helper lemma about sum and ++. Make sure to state this lemma and prove it!

Submission

Submission of this assignment should be done electronically through the Fire system.

The submission deadline is Wednesday, October 11, at 13:00. At this time, you should have submitted a serious attempt to solve the assignment. A serious attempt is either an answer you believe to be correct, or a partial answer plus a detailed explanation of what you have tried to come up with a full answer. An empty document is not a serious attempt.

After submitting, you have until October 23 (midnight) to submit a completely correct version.

You can submit your answers in any of the following formats:

A simple text file, ending in .txt. You can make text files in any text editor, and then upload it to the Fire system.
(When using a text file, you may sometimes need to "invent" notation. Please be clear about what your notation means. A list of suggested notation for text files is provided by us. You may also use Unicode.)
A picture you have made in a painting program, ending in .gif, .jpg, or .png. You can use for example MS Paint, or Google Docs to make a picture, and upload it to the Fire system.
A PDF-file, ending in .pdf. You can make PDF files by for example using OpenOffice, LibreOffice, Microsoft Word, or Google Docs, and choosing export as PDF. Then, upload the PDF-file to the Fire system.
A scanned in document, ending in .pdf or .jpg. You can write your answer on a piece of paper, and use a scanner to scan it in and convert to a PDF-file. Or you can use your mobile phone to take pictures of the papers, and upload these to the Fire system.

If you submit multiple files, please name and/or number them such that the order in which we should read them is obvious. You can also write a text file, and have it refer to pictures that you upload separately.