Solution 1

Functional Programming SS14
Solution - Exercise Sheet 1
Prof.aa
Dr. J. Giesl
F. Frohn
Exercise 1 (Function types):
(1 + 2 = 3 points)
a) Give examples of Haskell function declarations with the following types and briey explain their semantics:
[Int] -> Int -> Int
i)
[[Int]] -> [Int]
ii)
b)
foldl has the type (Bool -> Int -> Bool) -> Bool -> [Int] -> Bool and that f
Bool -> Int -> Bool. Let g be dened by g y xs = foldl f (foldl y True xs) xs.
type of g?
Suppose that
has the type
What is the
Solution:
a)
i)
count :: [Int] -> Int -> Int
count [] _ = 0
count (x:xs) y | x == y = 1 + count xs y
| otherwise = count xs y
Here,
ii)
count xs y
The type of
g
is
flatten
appears in the input list.
concatenates the elements of the input list.
(Bool -> Int -> Bool) -> [Int] -> Bool.
Exercise 2 (Lists):
a)
y
flatten :: [[Int]] -> [Int]
flatten [] = []
flatten (x:xs) = x ++ flatten xs
The function
b)
counts how often the element
(1.5 + 3 = 4.5 points)
Indicate for which of the following equations there exist pairwise dierent values of
x, y, and z, such that
the equation holds.
Give example values of
i)
ii)
iii)
x, y,
and
z
or explain why such an assignment is not possible.
[x]
=
(x:y) ++ z
(x:z):[y]
=
[x ++ y]
[x] ++ [[y]] ++ z
=
x:[y]:z
The operator ++ concatenates two lists. For example:
[1, 2, 3] ++ [2, 3] = [1, 2, 3, 2, 3].
b)
Consider the following patterns
p1)
(x:xs):xss
p2)
x:y:xs
and the following terms:
t1)
[1,2,3]
t2)
[[],[],[1,2,3]]
t3)
[[1]]
For each pair of a pattern and a term, indicate whether the pattern matches the term. If so, provide the
appropriate matching substitution. Otherwise, explain why the pattern does not match the term.
1
Functional Programming SS14
Solution - Exercise Sheet 1
Solution:
a)
i)
[x]
The equality holds for
=
(x:y) ++ z
y=z=[], but there are
no pairwise dierent values for
y
and
z
that satisfy the
equality.
ii)
(x:z):[y]
Let x be of
also of type
=
[x ++ y]
[a]. Then (x:z) is of type [[a]] and (x:z):[y]
[[[a]]] and y is of type [[a]]. But then, [x ++ y] is
type
Alternative solution:
is of type
[[[a]]].
Thus,
[y]
is
not well-typed.
(x:z):[y] has length two, but [x ++ y] has length one.
Thus, the equality does
not hold.
iii)
[x] ++ [[y]] ++ z
The equality holds for
b)
=
x:[y]:z
x=[], y=1, and z=[[]],
for example.
•
Pattern p1 does not match t1, because p1 only matches lists of lists.
•
Pattern p2 matches t1:
•
Pattern p1 does not match t2, since the rst element of p1 is a non-empty list, but the rst element
x=1, y=2, xs=[3].
of t2 is an empty list.
•
Pattern p2 matches t2:
x=[], y=[], xs=[[1,2,3]].
•
Pattern p1 matches t3:
x=1, xs=[], xxs=[].
•
Pattern p2 does not match t3, since p2 only matches lists with at least two elements.
Exercise 3 (Programming):
(2 + 2 + 2 + 3 = 9 points)
Note that you may use constructors like
a)
Write a
[]
and
:
in all of the following subexercises.
Haskell function that checks whether a given integer is even.
isEven :: Int -> Bool
For example,
isEven 0
and
isEven (-2)
should yield
True
and
You may not use any predened functions except comparisons,
b)
Write a
isEven 3
not, -,
and
should result in
False.
+.
Haskell function that counts the number of even elements of a list of integers.
countEven :: [ Int ] -> Int
For example,
countEven [3,-2,3,0] == 2
You should use the function
+.
c)
Write a
isEven
and
countEven [] == 0.
from part a), but you may not use any predened functions except
Haskell function that checks whether all elements of one list are also contained in another list:
containsAll :: [ Int ] -> [ Int ] -> Bool
For examples,
False.
containsAll [0,-1] [9,0,3,-1] yields True, but containsAll [4,3,4] [5,3,4] yields
You may not use any predened functions except
delete
deletes the rst occurrence of an element from a list, e.g.,
module, add the line import
d)
Write a
Data.List
Data.List. This function
delete 4 [4,3,4] == [3,4]. To use this
from the module
at the beginning of your solution.
Haskell function that computes the prex-sum of a list of integers:
prefixsum :: [ Int ] -> [ Int ]
2
Functional Programming SS14
Solution - Exercise Sheet 1
The
n-the
element of the resulting list should contain the sum of the rst
For example,
n
elements of the input list.
prefixsum [5,1,6,1] = [5,6,12,13].
You may not use any predened functions except
+.
Solution:
import Data . List
-- a )
isEven :: Int -> Bool
isEven 0 = True
isEven x | x > 0 = not ( isEven (x -1))
| otherwise = not ( isEven ( x +1))
-- b )
countEven :: [ Int ] -> Int
countEven [] = 0
countEven ( x : xs ) | isEven x = 1 + countEven xs
| otherwise = countEven xs
-- c )
containsAll
containsAll
containsAll
containsAll
:: [ Int ] -> [ Int ] -> Bool
[] _ = True
_ [] = False
xs ( y : ys ) = containsAll ( delete y xs ) ys
-- d )
prefixsum :: [ Int ] -> [ Int ]
prefixsum xs = prefixsum ' xs 0 where
prefixsum ' [] y = []
prefixsum ' ( x : xs ) y = ( x + y ) : prefixsum ' xs ( x + y )
Exercise 4 (Inx Operators):
Dene a Haskell function +|+ in inx notation with the type declaration
(+|+) ::
(3.5 points)
[Int] -> [Int] -> [Int]
such that the following holds for arbitrary lists:
•
The function call
xs +|+ ys
xs and ys. The order of
xs ++ ys, but the resulting list contains
expression [1,2,3,2,8] +|+ [0,1,7,0,3]
evaluates to the duplicate-free concatenation of
the elements in the resulting list corresponds to the elements in
only the rst occurrence of each element. For example, the
evaluates to
[1,2,3,8,0,7].
• xs +|+ ys +|+ zs
• xs +|+ ys ++ zs
is the same as
is the same as
xs +|+ (ys +|+ zs),
and
(xs +|+ ys) ++ zs.
elem and ++. The function elem checks whether an item is
elem 2 [1,2,3,2,8] == True and elem 4 [1,2,3,2,8] == False). You may, of
course, use constructors like : and [].
Note that the binding priority of ++ is 5.
You may not use any predened functions except
contained in a list (e.g.,
3
Functional Programming SS14
Solution - Exercise Sheet 1
Solution:
(+|+) :: [Int] -> [Int] ->
x +|+ y = removeDups (x ++
removeDups [] _ = []
removeDups (x:xs) ys |
|
[Int]
y) [] where
x elem ys = removeDups xs ys
otherwise = x : removeDups xs (x:ys)
4

Download Report