CISC 360 W2021
Question 1 (0.1 points) served a function similar to a cover page. There was only one possible answer.
Copyright By PowCoder代写 加微信 powcoder
Question 2 (4 points)
Consider the following Haskell data definition of red-black
trees storing strings:
data Rbt = Red Rbt String Rbt
| String Rbt
deriving (Show, Eq)
Write a Haskell expression corresponding to the following tree:
Red “a” Empty
Empty “czb” Red
Empty “” Empty
Black (Red Empty “czb” (Red Empty “” Empty)) “a” Empty
Question 3 (8 points)
Consider the same Haskell data definition of red-black trees storing strings:
data Rbt = Red Rbt String Rbt
| String Rbt
deriving (Show, Eq)
A red-black tree satisfies the “colour invariant” if, for every Red node in the tree, the
left and right children of the Red node are either Black or Empty. Write a Haskell
function cinv that returns True if the given tree satisfies the colour invariant,
and False otherwise. For example:
cinv ( “name” Empty) == True
(there are no Red nodes so the colour invariant holds)
cinv (Red Empty “x” Empty) == True
(both children of the Red node are Empty)
cinv (Red (Red Empty “x” Empty) “y” Empty) == False
(the left child of the root Red node is Red,
which violates the invariant)
cinv (Red ( “x” Empty) “y” Empty) == True
(both children of the Red node are either Black or Empty)
Your function should have type
cinv :: Rbt -> Bool
If you need a helper function, write a comment explaining what it does.
yuanqiliang
Question 4 (10 points)
This is a stepping question based on a function adjust, defined below.
When using function application, give the substitution. For example:
adjust ((\q -> q + 10), [])
⇒ [] by fun. app.
with substitution (\q -> q + 10) for u and [] for zs
adjust :: ((t -> t), [t]) -> [t]
adjust (u, x : y : zs) = (u y) : x : adjust (u, zs)
adjust (u, zs) = []
Complete the stepping below, doing as many steps as possible, but no more.
adjust ((\w -> w), [(\a -> a + 2), (\b -> 10), (\c -> c)])
Question 5 (8 points)
This question uses a Haskell datatype Exp of mathematical expressions, allowing constants
(Const), variables (Var), addition (Add), and negation (Negate).
For example,
(Add (Const 1) (Const 3))
represents the mathematical expression 1 + 3. (Const 1) represents 1, and (Const 3)
represents 3, so
(Add (Const 1) (Const 3))
represents 1 + 3. Similarly, we can represent the mathematical expression
(Add (Const 2) (Var “y”))
data Exp = Const Integer
| Var String
| Add Exp Exp
| Negate Exp
deriving (Show, Eq)
The function ‘inline’ is supposed to replace constant subexpressions with their values. For
example, in
(Add (Var “x”) (Add (Const 2) (Const 3)))
the Exp (Add (Const 2) (Const 3)) represents (2 + 3), which is 5, so we want to get
(Add (Var “x”) (Const 5))
So inline (Add (Var “x”) (Add (Const 2) (Const 3))) should return (Add (Var “x”) (Const 5)).
The (Var “x”) should be left alone, because we don’t know what it is.
Also, inline (Negate (Const 2)) should return Const (-2), because the negation of 2 is -2.
However, there are several bugs in the code. Find the bugs, explain what they are,
and explain how to fix them.
Give the complete corrected code at the end of your answer.
Question 5 (8 points) (continued)
inline :: Exp -> Exp
inline (Const m) = Const m
inline (Add e1 e2) = case (inline e1, inline e2) of
(Const m1, Const m2) -> m1 + m2
(e1′, e2′) -> Add e1 e2
inline (Negate e) = case (inline e) of
Const m -> Const (-m)
Question 6 (4 points)
Translate the logical formulas below to Prolog clauses.
1. ∀U ∀V (equiv(U, V) → equiv(U, U))
2. ∀A ∀B ∀D1 ∀D2 ∀Z (engrey(black(Z, A, B), D1) ∧ engrey(red(Z, B, A), D2) →
mapped(D2, D1))
Question 7 (8 points)
data Rbt = Red Rbt String Rbt
| String Rbt
deriving (Show, Eq)
Translate the 2-argument Haskell function ‘twirl’ to a 3-argument Prolog
predicate ‘twirl’. For example,
twirl (Red Empty “a” Empty) Empty
twirl( red(empty, “a”, empty), empty, black(empty, “a”, empty))
should be true.
twirl :: Rbt -> Rbt -> Rbt
twirl Empty _ = Empty
twirl (Black left s1 right) (Red _ s2 _) = if s1 == s2 then
twirl right right
twirl right left
twirl (Red left s right) _ = Black (twirl left right) s right
twirl _ _ = Empty
Question 8 (8 points)
The following extends a small part of Assignment 5 to generate a “proof term” that
represents which rules were used.
This allows Prolog to tell us not only “yes, this is true” but why it is true.
The small part includes only atomic propositions (v(a), v(b), v(c), etc.) and conjunctions
(‘and’), with only two rules: UseAssumption and AND-Left.
In place of the 2-argument predicate prove(Ctx, Formula), we will use a 3-
argument predicate
derive(Ctx, Formula, Proof)
The proofs (“proof terms”) are as follows:
use(Q) UseAssumption using assumption Q
and_left(P1, P2, Proof) and_left splitting and(P1, P2) in the context, continuing with Proof
For example, the query
?- derive([v(a), v(b), v(c)], v(b), Proof).
corresponds to the 204 sequent “a, b, c ⊢ b” and produces one “proof term”:
Proof = use(v(b))
“Use the assumption v(b)”
?- derive([and(v(a), v(b)), v(b)], v(b), Proof).
corresponds to the 204 sequent “a ∧ b, b ⊢ b”, and should produce at least two
Proof = use(v(b))
“Use assumption v(b)”
Proof = and_left(v(a), v(b), use(v(b)))
“Working backwards,
use and_left to decompose and(v(a), v(b)),
then use the assumption v(b)”
As usual, your job is to find as many bugs in my code as you can, explain what the
bugs are, and explain how to fix them.
Hint: One bug is that for the above query ?- derive([and(v(a), v(b)),
v(b)], v(b), Proof), my code only produces the first Proof: use(v(b)).
Question 8 (8 points) (continued)
% UseAssumption rule
derive( Ctx, Q, use(Q)) :-
member(Q, Ctx),
% AND-Left rule
derive( Ctx, Q, and_left(P1, P2, Proof)) :-
append( Ctx1, [and(P1, P2) | Ctx2], Ctx),
append( Ctx1, [P1 | [P2 | Ctx2]], CtxP12),
derive( CtxP1P2, Q, Proof).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com