workshop1

Question 1

What happens here?

> sentence = “Sentences can go “ ++ onAndOn
onAndOn = “on and “ ++ onAndOn

take 65 sentence

Answer 1

onAndOn recurses on itself, repeating “on and “ infintaly

sentence adds onAndOn to the end of a string

take 65 sentence takes the first 65 characters of the string

Question 2

What happens here?

> sentences = “Sentences can go on” : map (++ “ and on”) sentences

take 10 sentences

Answer 2

this is creating an infinite list that is growing by concatinating itself to a recursion of itseld

take 10 sentences will have a list of 10 strings begining with “Sentences can go on” and adding another “and on.

this works because each call into the recursion is mapping a concatination of “and on” to the result of every one that was previously processed

Question 3

Can you give your own definitions of map

Answer 3

map::(a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs

Question 4

Can you give your own definitions of take

Answer 4

take:: Int -> [a] -> [a]
take _ [] = []
take n (x:xs) = x : take (n-1) xs

Question 5

give some examples of the domain of natural numbers

Answer 5

being even, odd, prime, 3-fold, etc

Question 6

make a threefold property in haskell

Answer 6

> threefold :: Integer -> Bool

> threefold n = rem n 3 == 0

Question 7

Why does threefold express a property of integer numbers?

Answer 7

???

Question 8

What is the most general specification of a property?

Answer 8

???

Question 9

make a lazy list of natural numbers that are threefolds

Answer 9

> threefolds = filter threefold [0..]

Question 10

Can you give your own definition of filter?

Answer 10

filter::(Eq a) => (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter f (x:xs) = if f x then x : filter f xs else filter f xs

Question 11

how to say there is no largest natural number in haskell

Answer 11

> nats = [0..]query1 = all (\ n -> any (\ m -> n < m) nats) nats
or
forall = flip all
query1’ = forall nats (\ n -> exist nats (\ m -> n < m))

Question 12

how to say there is a smallest natural number

Answer 12

> nats = [0..]query2 = any (\ n -> all (\ m -> n <= m) nats) nats
or
exist = flip any
query2’ = exist nats (\ n -> forall nats (\ m -> n <= m)

Question 13

Give your own definition of all

Answer 13

myall::(a -> Bool) -> [a] -> Bool
myall _ [] = True
myall f (x:xs) = f x && all f xs

Question 14

make a quickCheck property for myall

Answer 14

this will not work:
\ p xs -> all p xs == myall p xs
QuickCheck is designed to display counterexamples, but there is no general way to display functions, and p is a function.

general conversion from lists to properties:
> list2p :: Eq a => [a] -> a -> Bool
> list2p = flip elem

prop_myall:: [Int] -> [Int] -> Bool
prop_myall = (\ ys xs -> let p = list2p ys) in all p xs == myall p xs

> quickCheck myallTest

Question 15

what general recursion pattern does foldr solve?

Answer 15

you have to specify a value for the base case,

you have to give a definition for the recursive case (x:xs) in terms of the first element of the list x and a recursive call for the tail of the list xs.

Question 16

update myall to use foldr

Answer 16

myall’ p = foldr (\ x b -> p x && b) True

Question 17

define foldr

Answer 17

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

Question 18

Definition of being a prime number with a formula of predicate logic

Answer 18

P(n):≡n∈N∧n>1∧∀d∈N(1 < d < n→¬D(d,n)).

n is prime :≡ n is a natural number and n>1 and for all natural numbers d with 1< d< n it holds that d does not divide n.

Question 19

implement primes

Answer 19

first first thing we need is the divide relation
> divide :: Integer -> Integer -> Bool
> divide n m = rem m n == 0

next the relations:
> isPrime :: Integer -> Bool
> isPrime n = n > 1 && all (\ d -> not (divide d n)) [2..n-1]

Question 20

Are you able to state the types and provide your own definitions of all

Answer 20

all::(a -> Bool) -> [a] -> Bool
all f [] = True
all f (x:xs) 
    | f x = all f xs
    | otherwise = False

Question 21

Are you able to state the types and provide your own definitions of not

Answer 21

not::Bool -> Bool
not True = False
not _ = True

Question 22

Are you able to state the types and provide your own definitions of any

Answer 22

any::(a -> Bool)  -> [a] -> Bool
any f [] = False
any f (x:xs) 
    | f x = True
    | otherwise = any f xs

Question 23

Are you able to state the types and provide your own definitions of &&

Answer 23

(&&)::Bool -> Bool -> Bool
True && True= True
_ && _ = False

Question 24

Are you able to state the types and provide your own definitions of ||

Answer 24

(||)::Bool -> Bool -> Bool
False || False = False
_ || _ = True

Question 25

slightly more efficient version of isPrime

Answer 25

> isPrime’ :: Integer -> Bool
isPrime’ n = all (\ x -> rem n x /= 0) xs
where xs = takeWhile (\ y -> y^2 <= n) [2..]

Question 26

tests only for divisibility by primes

Answer 26

> prime :: Integer -> Bool
prime n = n > 1 && all (\ x -> rem n x /= 0) xs
where xs = takeWhile (\ y -> y^2 <= n) primesprimes :: [Integer]
primes = 2 : filter prime [3..]

(has to start explicity at 2 because …?)

Question 27

sieve of Eratosthenes

Answer 27

> sieve :: [Integer] -> [Integer]
sieve (n:ns) = n : sieve (filter (\m -> rem m n /= 0) ns)eprimes = sieve [2..]

or

primes :: [Int]
primes = sieve [2..]

sieve :: [Int] -> [Int]
sieve (p:xs) = p : sieve [x | x

Question 28

find the smallest natural number that matches an arbitrary property

Answer 28

nats = [0..]

least :: (Integer -> Bool) -> Integer
least p = head (filter p nats)

least1 p = lst p 0
where lst p n = if p n then n else lst p (n+1)

Question 29

A prime pair is a pair (p,p+2)(p,p+2) with the property that both pp and p+2p+2 are primes. The first prime pair is (3,5). Implement a function for generating prime pairs, and use this to find the first 100 prime pairs.

Answer 29

> dif2 :: [Integer] -> [(Integer,Integer)]
dif2 (p:q:rs) = if p + 2 == q then (p,q) : dif2 (q:rs)
else dif2 (q:rs)primePairs = dif2 primes

Question 30

A prime triple is a triple (n,m,k)(n,m,k) such that n

Answer 30

> dif6 :: [Integer] -> [(Integer,Integer,Integer)]
dif6 (p:q:r:ss) = if p + 6 == r then (p,q,r) : dif6 (q:r:ss)
else dif6 (q:r:ss)primeTriples = dif6 primessol = take 100 primeTriples

Question 31

Implement a function nextPrime with the property that nextPrime n returns n when n is prime, and the next prime after n otherwise.

Answer 31

> nextPrime :: Integer -> Integer

> nextPrime n = if prime n then n else nextPrime (n+1)

Question 32

A Mersenne number is a natural number of the form 2^p−1 where pp is a prime number. A Mersenne prime is a Mersenne number that is itself prime. Write a function for generating Mersenne primes. How far do you get? Note: only 48 Mersenne primes are known

Answer 32

> mersenne :: [Integer]

> mersenne = [ p | p

Question 33

A Pythagorean triple is a triple of natural numbers (x,y,z) with the property that x^2+y^2=z^2. The smallest example is (3,4,5). Implement a Haskell function that generates Pythagorean triples. Are there Pythagorean triples (x,y,z) with x=y? If your answer is “Yes”, give the smallest one. If your answer is “No”, explain why this is impossible.

Answer 33

> pythTriples :: [(Integer,Integer,Integer)]
pythTriples = filter (\ (x,y,z) -> x^2 + y^2 == z^2)
[ (x,y,z) | z

Question 34

Prove by induction that it holds for all natural numbers nn that
1+2+⋯+n=(n(n+1))/2.

Answer 34

Base case: for n=0 the property holds.

Induction step.

Induction hypothesis: 1+2+⋯+n=(n(n+1))/2.

To be proved: 1+2+⋯+n+(n+1)=((n+1)(n+2))/2.

Note: ((n+1)(n+2))/2 is the result of substituting n+1 for n in (n(n+1))/2.

Proof (of the induction step):
1+2+⋯+n+(n+1)=ih
=(n(n+1))/2+(n+1)
=(n(n+1))/2+2(n+1)/2
=(n+2)(n+1)/2
=(n+1)(n+2)/2
Note: step =ih uses the induction hypothesis.

Question 35

Prove by induction that it holds for all natural numbers n that
1^2+2^2+⋯+n^2=n(n+1)(2n+1)/6.

Answer 35

To be proved:
for all n∈N:1^2+2^2+⋯+n^2=n(n+1)(2n+1)/6

Proof by induction.
Base case: for n=0 the property holds.

Induction step.

Induction hypothesis:
1^2+2^2+⋯+n^2=n(n+1)(2n+1)/6

To be proved:
1+2^2+⋯+n^2+(n+1)^2=(n+1)(n+2)(2n+3)/6

Proof:

1^2+2^2+⋯+n^2+(n+1)^2=ih
=n(n+1)(2n+1)/6+(n+1)^2
=n(n+1)(2n+1)/6+(6(n+1)^2)/6
=(2n^2+n)(n+1)/6+((6n+6)(n+1))/6
=(2n^2+7n+6)(n+1)/6
=(n+2)(2n+3)(n+1)/6
=(n+1)(n+2)(2n+3)/6

Question 36

Prove by induction that it holds for all natural numbers n that
1^3+2^3+⋯+n^3=((n(n+1))/2)^2.

Answer 36

Proof by induction.
Base case: for n=0 the property holds.

Induction step.
Induction hypothesis:
1^3+2^3+⋯+n^3=((n(n+1))/2)^2

To be proved:
1^3+2^3+⋯+n^3+(n+1)^3=((n+1)(n+2)/2)^2

Proof:
1^3+2^3+⋯+n^3+(n+1)^3=ih
=((n(n+1))/2)^2(n+1)^3
=(n^2(n+1)^2)/4+(4(n+1)^3)/4
=(n^2(n+1)^2)/4+((4n+4)(n+1)^2)/4
=((n+1)^2(n^2+4n+4))/4
=((n+1)^2(n+2)^2)/4
=((n+1)(n+2)/2)^2

Question 37

Prove by induction that if A is a finite set with |A|=n, then |P(A)|=2^n

• P(A) = powerset of A

Answer 37

The empty set has 0 members and P(∅)={∅} has 1(=2^0) member, so in the base case the assertion holds.

Suppose that
if |A|=n, then |P(A)|=2^n.
Now let A′ be such that A⊆A′ and |A′|=n+1.

Then there is exactly one object x with x∉A and A′=A∪{x}.
Now consider the subsets B′ of A′.
How many of those are there? The subsets B′ of A′ are of two kinds:
those with x∈B′ and those with x∉B′.
In fact, for any subset B of A, B⊆A′ and B∪{x}⊆A′, and B≠B∪{x}.
Thus A′ has twice as many subsets as A and we have, by induction hypothesis, that |P(A′)|=2⋅2^n=2^(n+1)

Question 38

A permutation of a list is a reordering of the members of a list. Here is a Haskell implementation:

> perms :: [a] ->[[a]]
perms [] = [[]]
perms (x:xs) = concat (map (insrt x) (perms xs)) where
insrt x [] = [[x]]
insrt x (y:ys) = (x:y:ys) : map (y:) (insrt x ys)

Find a formula (closed form) for the number of permutations of a list of n distinct objects, and prove your guess by induction.

Answer 38

There are n! permutations for a list of n distinct objects.

The empty list has a single permutation, and indeed, 0!=1 (by the convention for an empty product).

Suppose a list of n distinct objects has n! permutations.

Then there are n+1 ways to insert a new object into one of these.
Together this gives (n+1)×n! = (n+1)! permutations of a list of n+1 distinct elements.