Discrete Mathematics for Computer Scientists -- Assignment 6 - Structural InductionDIT980, HT 2015
Home | Schedule | Assignments | Exercises | Exam | AboutFire | Forum | TimeEdit | Links | 2014
Assignment Week 6 - Structural Induction

Please submit using the Fire system

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 14, 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 26 (midnight) to submit a completely correct version.