@leo's

A bit late, but here you get the solutions from week three.

Usage of List

Multiply all numbers from 1 to 100 by using a prelude function (and no recursion)

foldr (*) 1 [1..100]

Sum all odd numbers bellow 50. Use a prelude function and the haskell list in a clever way.

sum [1,3..49]

Generate the string "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" (remember a string in haskell is just a list of chars)

['a'..'z'] ++ ['a'..'z']

List functions

sum :: (Num a) => [a] -> a
sum [] = 0
sum (x:xs) = x + (sum xs)

merge :: [a] -> [a] -> [a]    -- merge two list (in haskell (++))
merge [] ys = ys
merge (x:xs) ys = x : (merge xs ys)

nthElement :: [a] -> Int -> a -- give the n-th element of a list (in haskell (!!))
nthElement (x:xs) 0 = x       -- errors ignored
nthElement (x:xs) n+1 = nthElement xs n

List comprehension

Find all numbers bellow 1000 that are devidable by 3 or 5 with a list comprehension. 

[x | x <- [1..999], (mod x 3)==0 || (mod x 5)==0]

A Proof for the end

You can also do recursiv proofs over lists. Given the following programm:

map f [] = []                    (m.1)
map f (x:xs) = f x : map f xs    (m.2)
times2 x = 2*x                   (ti)
twice [] = []                    (tw.1)
twice (x:xs) = (2* x):(twice xs) (tw.2)

Prove "FORALL xs::[int]. twice xs = map times2 xs" with recursion.

FORALL xs::[int]. twice xs = map times2 xs
Let P(xs) = twice xs = map times2 xs. 
Show FORALL xs::[int]. P(xs) holds by induction over xs

Base case: P([])
twice [] = []               (tw.1)
         = map times2 []    (m1.rev)

Step case: Show FORALL x::int, xs::[int]. P(xs) => P(x:xs) (IH = P(xs))
Twice (x:xs) = (2 * x):(twice xs)         (tw.2)
             = (times2 x):(twice xs)      (ti.rev)
             = (times2 x):(map times2 xs) (IH)
             = map times2 (x:xs)          (tw.2.rev)

Here is the solution for the second week extra excercise. Download it form: leo.freeflux.net/files/fmfp/CA%20Solution.pdf

The "Listtatzelwurm" or "Listmonster" you might already know from the tutorial. It's from the site "learn you a haskell for greater good", if you need more help about list, the chapter with the Listmonster might be a help for you.

Let me give you some extra exercises for the current chapter. The solution will be online in around a week.

Usage of List

Multiply all numbers from 1 to 100 by using a prelude function (and no recursion)

Sum all odd numbers bellow 50. Use a prelude function and the haskell list in a clever way.

Generate the string "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz" (remember a string in haskell is just a ... of ...)

List functions

TA's usually just let you implement prelude functions to train list functions. So then, implement this functions recursiv:

sum :: (Num a) => [a] -> a
merge :: [a] -> [a] -> [a]    -- merge two list (in haskell (++))
nthElement :: [a] -> Int -> a -- give the n-th element of a list (in haskell (!!))

List comprehension

You already talked about list comprehension in the lecture. If you want to repeat it a bit, read the first chapter here http://www.haskell.org/haskellwiki/List_comprehension. Then find all numbers bellow 1000 that are devidable by 3 or 5 with a list comprehension. (When you sum this up you have already solved the first problem of project euler.)

A Proof for the end

You can also do recursiv proofs over lists. Given the following programm:

map f [] = []                    (m.1)
map f (x:xs) = f x : map f xs    (m.2)
times2 x = 2*x                   (ti)
twice [] = []                    (tw.1)
twice (x:xs) = (2* x):(twice xs) (tw.2)

Prove "FORALL xs::[int]. twice xs = map times2 xs" with recursion.

I just want to write down the proof that we did as an example in the last exercise session as you might want to use it as a reference for the current exercise sheet.

If we have the following haskell programm:

sum 0 = 0              --sum.1

sum n = n+sum (n-1)  --sum.2

And you want to prove forall n element of Nat. sum n = n*(n+1)/2 then we write the following proof:

Lemma: forall n element of Nat. sum n = n*(n+1)/2
Proof: We show forall n element of Nat. sum n = n*(n+1)/2 by induction. Let P(n) = sum n = n*(n+1)/2.

Base Case: Show P(0).

sum 0
= 0 -- sum.1
= 0*(0+1)/2 –- arith

Step Case: Let n element of Nat be arbitrary and assume that P(n) holds. Show P(n+1).

sum (n+1)
= (n+1) + sum ((n+1)-1) -- sum.2
= (n+1) + sum (n) -- arith
= (n+1) + n*(n+1)/2 -- P(n)
= 2*(n+1)/2 + n*(n+1)/2 --arith
= (n+2)*(n+1)/2 --arith
= (n+1)*((n+1)+1)/2 --arith

qed.

(The italic text of the proof might be used as a template for all recursiv proofs.)