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.
You can submit your answers in any of the following formats:
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.
