Ludwig-Maximilians-University Munich Institute for Computer Science Prof. Dr.
programming and modeling in Haskell, summer semester 21
semester exam
Copyright By PowCoder代写 加微信 powcoder
July 19, 2021
Organizational Notes:
1) Prepare examination tasks The tasks
must be available on the GATE online platform https://gate.ifi.lmu.de/ be worked out.
Only the solutions entered on GATE will be corrected. Other documents (such as notes on the exam book, image files, or conversions of the exam book to Word or PDF documents) will not be corrected.
2) Sign and submit the declaration of independence The examination
books of the students who submit the declaration of independence (the template can be found on Uni2work https://uni2work.ifi.lmu.de/) are corrected and graded. signed and uploaded as a PDF file to Uni2work by 11:59 p.m. on the day of the exam at the latest.
3) Voiding You
can void your exam booklet so that you do not receive a grade by completing the appropriately designated task in GATE and your decision by selecting the option “I request that my exam booklet be “cancelled”, ie not corrected and not graded .” announce accordingly.
4) Aids Aids are
not necessary, can even be a hindrance and should not be used. However, it makes sense to use a Haskell
editor and a Haskell compiler (like the Glasgow Haskell Compiler ghc).
I wish you success!
© 2021 The staff of the teaching and research unit PMS, IfI. All rights reserved. Publication and duplication, even in part, only with the permission of the author.
Programming and modeling in Haskell, semester exam, July 19, 2021
Task 1 type signatures
a) Give a Haskell function f that has the type
(a -> b -> c) -> (a -> b) -> a -> c
f :: (a -> b -> c) -> (a -> b) -> a -> c fghx =
b) Give the Haskell type signature of any first-order unary function e . Do not use any type other than integer.
c) Submit the Haskell type signature of any first order two-digit function z exclusive use of the polymorphic type p .
© 2021 The staff of the teaching and research unit PMS, IfI. All rights reserved. Publication and duplication, even in part, only with the permission of the author.
(1+1+1 points)
Programming and modeling in Haskell, semester exam, July 19, 2021
Task 2 recursion
ÿÿÿÿÿÿÿÿÿÿÿÿ
The magnitude of a vector ~x = (x1, x2, . . . , xn) is defined as the square root of the sum of the
Squares its components:
A vector should be represented in Haskell by a non-empty finite list.
magnitude :: Floating a => [a] -> a
where sumOfSquares acc
. sumOfSquares
else sumOfSquares ((
|~x| = vuutXn i=1
a) Write a Haskell function magnitude :: floating a => [a] -> a with a recursive,
but not terminally recursive helper function that returns the absolute value of a vector. Use for that of the list functions only the list constructor (:); head and tail are not allowed.
magnitude :: floating a => [a] -> a
magnitude = sumOfSquares where sumOfSquares[] = 0
sumOfSquares ( ) = + sumOfSquares
b) Formulate the above function in such a way that the vector sum is expressed end-recursively. The new Haskell function magnitude’ should otherwise behave identically to magnitude . You may for it
use the list functions (:), null, head and tail .
c) Using the list function foldr, implement a lambda expression in Haskell notation, which you call magnitude” and which behaves like magnitude and magnitude’ .
magnitude magnitude
:: Floating a => [a] -> a
© 2021 The staff of the teaching and research unit PMS, IfI. All rights reserved. Publication and duplication, even in part, only with the permission of the author.
(1+1+1 points)
Programming and modeling in Haskell, semester exam, July 19, 2021
Task 3 evaluation
a) Given the following Haskell evaluation step:
if 1 > 0 then 1+1 else 0*1 if True then 2 else 0
• Is this evaluation step correct for the application-related evaluation sequence? Yes no
• Is this evaluation step correct for the normal order of evaluation? Yes no
• Is this evaluation step correct for the delayed evaluation order? Yes no
b) Given the following Haskell definitions:
one = \x -> 1 sq = \x -> x*x
• If during an application evaluation of the expression one (sq (sq 2)) the square of 2 (i.e. sq 2) calculated twice?
• During normal evaluation of the expression one (sq (sq 2)) becomes the square of
2 (i.e. sq 2) calculated once? Yes no
• During a lazy evaluation of the expression one (sq (sq 2)) becomes the square of 2 (i.e. sq 2) not computed once?
c) Given the following Haskell definitions:
one x = \x -> 1 sq x = \x -> x*x
• If during an application evaluation of the expression sq (one (2+1)) the sum becomes 2+1 calculated exactly twice?
• During a normal evaluation of the expression sq (one (2+1)) the sum becomes 2+1 calculated exactly once?
• If during a lazy evaluation of the expression sq (one (2+1)) the sum becomes 2+1 calculated exactly once?
© 2021 The staff of the teaching and research unit PMS, IfI. All rights reserved. Publication and duplication, even in part, only with the permission of the author.
(1+1+1 points)
Programming and modeling in Haskell, semester exam, July 19, 2021
Task 4 binary trees
Given the following definition of the polymorphic data type BB: data BB a = L | K (BB a) a (BB a)
where BB stands for binary tree, L for empty tree and K for node.
a) Formulate a Haskell value w of this type BB such that the prefix depth-first-traversal of the tree results in the following list of values: [“<*>“,”<$>“,”(*)”,”[3]”,”[2]”]. The list items are re
their arity are to be understood as Haskell syntax elements, i.e. the character string “<$>” is to be understood as an application operator and thus has the arity of 2.
w = K (K (KL ”
” (KL”[2]”L)
b) Give the value list l for the infix depth-first search of the tree from the previous subtask and evaluate the expression it represents using Haskell rules.
l = [” “,” “,”[3]”,” “,” “]
Evaluation:
© 2021 The staff of the teaching and research unit PMS, IfI. All rights reserved. Publication and duplication, even in part, only with the permission of the author.
(1+2 points)
Programming and modeling in Haskell, semester exam, July 19, 2021
Task 5 polymorphism (1+1+1 points) The following definition of the polymorphic data type BB (identical to exercise 4) is given: data BB a = L | K (BB a) a (BB a)
where BB stands for binary tree, L for empty tree and K for node.
a) Realize a Haskell function with the following type signature, using the tree of type BB and applies the specified unary operator to each value of the tree. That
that is, the function show and the tree K (KL 2 L) 1 (K (KL 4 L ) 3 L) applied to fmapBB should result in the value K (KL “2” L) “1” (K (KL “4” L) “3” L) .
fmapBB :: (a -> b) -> BB a -> BB b fmapBB f L =
fmapBB f (
b) Give the necessary Haskell definitions to create a type of the type class Functor from the type BB using the function fmapBB . Only one identifier is allowed in each gap
such as BB, Functor, fmapBB , etc.
c) Complete the Haskell code snippet below, which calls the show function to the Elements of the binary tree b = K (KL 2 L) 1 (K (KL 4 L) 3 L) applies.
convert :: Functor t => t Int -> t String convert = show
showBB :: BB String
showBB = let b = K (KL 2 L) 1 (K (KL 4 L) 3 L) in b
© 2021 The staff of the teaching and research unit PMS, IfI. All rights reserved. Publication and duplication, even in part, only with the permission of the author.
Programming and modeling in Haskell, semester exam, July 19, 2021
Task 6 data types
(1+1+1 points)
data polynomial ce =
PolySentinel
whose nodes store coefficients of type c and exponents of type e . Also will
another node stored, or a sentinel (special node with no data elements) if that polynomial is already fully represented.
A polynomial of the form cn · x
+ . . . + c1 · x + c0 shall be represented by a data structure
a) Define a recursive Haskell data type polynomial with the constructors Poly and PolySentinel. Do not use any built-in data types such as list, tuple or similar for this.
deriving Eq;
b) Define a Haskell function tuplesToPoly :: [(c, e)] -> polynomial c e containing a list from tuples of type (c,e) into the data structure polynomial .
tuplesToPoly :: [(c, e)] -> Polynomial ce
tuplesToPoly[] =
tuplesToPoly (( , ):xs) = Poly ce ( )
c) Create a Haskell function
showPoly :: (Show c, Show e, Show c, Show e) => Char -> Polynomial ce -> String
which makes it possible to output a polynomial. The first parameter gives the function
the variable identifier (such as ‘x’ or ‘z’) to the data type Char . Make sure at that
the output of the polynomial contains the plus signs only between the terms of a polynomial, but not at the beginning or at the end of the polynomial.
The string returned by the function with the call parameters ‘z’ and
For example , (tuplesToPoly [(3.0,2),(2.0,1),(0.5,0)]) is “3.0*z^2 + 2.0*z^1 + 0.5*z^0”.
showPoly :: (Eq c, Eq e, Show c, Show e) => Char -> Polynomial ce -> String “”
showPoly v PolySentinel = showPoly v (Poly ce
concat [ (Poly ce rest) =
© 2021 The staff of the teaching and research unit PMS, IfI. All rights reserved. Publication and duplication, even in part, only with the permission of the author.
, “*”, [v], “^”, showPoly v
, “*”, [v], “^”,
poly cnÿ1
Programming and modeling in Haskell, semester exam, July 19, 2021
Exercise 7 Type Classes The
following type signature is given.
reverse :: (Foldable t, Applicative t, Monoid (ta)) => ta -> ta reverse ls = …
a) Complete the Haskell function reverse which takes the values in the foldable applicative functor t reverses. For example, the result of reverse [1, 2, 3] in the functor ”’list”’ is the value
[3, 2, 1].
Do not assume any functions other than those defined by the specified type classes
are defined. Note that the function works for any type t of the specified signature and not only intended to work for lists and that the function for infinite sets of values does not is defined. Only use explicit parameters.
reverse :: (Foldable t, Applicative t, Monoid (ta)) => ta -> ta
reverse ls = (\lr -> r l) ls
b) Using the additional functions (.) and flip , formulate the above
Function as a higher-order Haskell function with no explicit parameters. Also use no explicit parameters in lambda expressions.
reverse :: (Foldable t, Applicative t, Monoid (ta)) => ta -> ta
reverse = foldr (flip
c) Can the above function be implemented in the same way using foldr and foldl ? Yes no
© 2021 The staff of the teaching and research unit PMS, IfI. All rights reserved. Publication and duplication, even in part, only with the permission of the author.
(1+1+1 points)
Programming and modeling in Haskell, semester exam, July 19, 2021
Exercise 8 Monads The
following Haskell code fragment is given. data Expr = Num Double
| Add Expr Expr
| Var Char deriving Show
type Env = [(Char , double)]
evalDo :: Env -> Expr -> Maybe Double evalThu _ (num a) = return a evalDo e (Add ab) = do
a’ <- evalDo ea b' <- evalDo eb Just (a'+b')
a) Define a Haskell function getvar :: Env -> Char -> Maybe Double, which returns Nothing if the character is not found in the variable of type Env , the corresponding one
Double otherwise.
getvar :: Env -> Char -> Maybe Double getvar =
b) Extend the above code snippet with a rule that allows evaluating variables in expressions by replacing them with their corresponding numerical value. If the variable is not found in the list, Nothing is returned. For example, the expression evalDo [(‘x’, 2)] (Num 5 `Add` Var ‘x’) evaluates to Just 7.0, while
the expression evalDo [(‘x’, 2)] (Num 5 `Add` Var ‘y’) evaluates to Nothing results.
evalDo :: Env -> Expr -> Maybe Double
evalDo e ( ) = getvar c
c) Extend the code snippet above to include the possibility of finding the square root of an Aus to calculate pressure.
data Expr = Num Double
| Add Expr Expr
| Var Char deriving Show |
) = do a’ <- a
if <0 then
evalDo e (Sqrt
© 2021 The staff of the teaching and research unit PMS, IfI. All rights reserved. Publication and duplication, even in part, only with the permission of the author.
else (square )
(1+1+1 points)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com