Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

FACULTY OF ARTS AND SCIENCE

SCHOOL OF COMPUTING

CISC 360 001 – Prof. Jana Dunfield

April 20, 2021

Question 3 (8 points)

Consider the same Haskell data definition of red-black trees storing strings:

data Rbt = Red Rbt String Rbt

| Black Rbt String Rbt

| Empty

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 (Black Empty "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 (Black Empty "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.

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

(2 + y)

as

(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 7 (8 points)

data Rbt = Red Rbt String Rbt

              | Black Rbt String Rbt

              | Empty

              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

returns

Black Empty "a" Empty

so

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

                                                         else

                                                            twirl right left

twirl (Red left s right)      _                = Black (twirl left right) s right

twirl _                            _                = Empty

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).