/*
CISC 360, Fall 2021
Sample questions for Quiz 4
*/
/* Q1
In this question, implement a Prolog predicate
before(X, Y, Zs)
that is true iff (1) X and Y are elements of Zs, and (2) X appears to the left of Y in Zs. For example,
before(3, 1, [1, 2, 3])
should be false (because 3 does not appear to the left of 1), and
before(99, 98, [100, 99, 98, 97])
and
before(99, 98, [100, 99, 98, 99])
should both be true (because in both lists, 99 appears to the left of 98;
it does not matter whether 99 also appears to the right of 98).
You may use the built-in predicate member(A, Bs),
which is true iff A is an element of the list Bs.
For example, member(5, [7, 5, 7]) is true.
*/
/* Q2
This question asks you to translate Prolog clauses into logical formulas.
Translate each of the Prolog clauses 1–4 into a corresponding logical formula. Hint: Copy and paste the Prolog clauses into your answer, then edit them.
You may copy and paste these symbols: ∀ ∃ ∧ → or type: all exists and ->
1. vacuous(empty).
2. dup(T, K, node(K, T, T)).
3. above(X, Y) :- flat(X, Z), above(Z, Y).
4. similar(node(K, L, R), node(K, L2, R2)) :- similar(L2, L), similar(R2, R).
*/
/* Q3
There could also be a question asking you to translate queries,
similar to Quiz 3.
*/
/* Q4
Write a Prolog relation two_power that corresponds to the Haskell function two_power, defined as follows:
{-
two_power acc n (where n >= 0)
Return acc * (2 ^ n), where 2 ^ n is 2 raised to the nth power.
For example, two_power 8 1 == 16 because 8 * (2 ^ 1) = 8 * 2 = 16.
-}
two_power :: Integer -> Integer -> Integer
two_power acc 0 = acc
two_power acc n = two_power (2 * acc) (n – 1)
Translate two_power to a Prolog relation taking 3 arguments, such that
two_power(Acc, N, Result) iff two_power(Acc, N) returns Result
is true in Prolog in Haskell.
For example, the query ?- two_power(5, 0, Result). should give the answer Result = 5,
because 5 * (2 ^ 0) = 5 * 1 = 5.
You may use ONLY these arithmetic operators:
= is * – + =< < > >= =:= =\=
Don’t use the built-in operator ** or other arithmetic library functions.
*/
/* Q5
This question uses the same kinds of trees as the last question of Assignment 4.
A tree is either a leaf with an integer key, or a node with an integer key and two children.
For example, node(1, leaf(2), leaf(3)) is the tree
1
/ \
2 3
The following Prolog code is supposed to find paths from the root to a leaf that “zigzag”:
they go left, then right, left, right, etc.—or they go right, then left, etc.
A “left zigzag” path starts by going to the left child, then (if the left child is not a leaf) goes to the right child, and so on.
A “right zigzag” path starts by going to the right child, then (if the right child is not a leaf) goes to the left child, and so on.
The predicate zigzag(T, Z) should be true iff Z is either a left or right zigzag path from the root of T to a leaf.
The predicate leftzz(T, Z) should be true iff Z is a left zigzag path from the root of T to a leaf.
The predicate rightzz(T, Z) should be true iff Z is a right zigzag path from the root of T to a leaf.
For example: leftzz(node(1, leaf(2), leaf(3)), [1, 2]) should be true,
and therefore zigzag(node(1, leaf(2), leaf(3)), [1, 2]) should be true.
However, zigzag(node(5, node(6, leaf(7), leaf(8)), leaf(3)), [5, 6, 7]) should not be true, because [5, 6, 7] goes from 5 to the left child (6), and then again to 6’s left child (7). That is a path, but it goes left twice in a row, so it is not a zigzag path.
Some more examples:
*5* *5* *5*
left/ \ left/ \ / \right
*6* 3 *6* 3 6 *3*
left/ \ / \right / \
*7* 8 7 *8* 7 8
[5, 6, 7] [5, 6, 8] [5, 3]
not a zigzag path: zigzag path: zigzag path:
goes left twice left to 6, right to 3
then right to 8
For example, this query should find the second ([5, 6, 8]) and third ([5, 3]) paths above:
?- zigzag(node(5, node(6, leaf(7), leaf(8)), leaf(3)), Result).
Result = [5, 6, 8] % type ; % first result: using leftzz (then rightzz)
Result = [5, 3]. % second result: using rightzz
Here is our code:
zigzag( T, Z) :- leftzz(T, Z), !. % line 1
zigzag( T, Z) :- rightzz(T, Z), !. % line 2
leftzz( leaf(K), [J]). % line 3
leftzz( node(K, L, _), Path) :- rightzz(L, Path). % line 4
rightzz( leaf(K), [K]). % line 5
rightzz( node(K, L, _), [K | Path]) :- leftzz(R, Path). % line 6
This code contains at least one bug. Find the bugs.
For each bug, (1) show how to fix it (copy the buggy line from the code above into your answer, and edit it to fix the bug), and (2) explain why your change fixes the bug.
Hint: At least one of the bugs involves the “cut” feature of Prolog.
*/
zigzag( T, Z) :- leftzz(T, Z), !. % line 1
zigzag( T, Z) :- rightzz(T, Z), !. % line 2
leftzz( leaf(K), [J]). % line 3
leftzz( node(K, L, _), Path) :- rightzz(L, Path). % line 4
rightzz( leaf(K), [K]). % line 5
rightzz( node(K, L, _), [K | Path]) :- leftzz(R, Path). % line 6
/*
Hints for efficiency in the actual quiz:
Before you start the quiz, create files q2.pl, q3.pl, q4.pl, q5.pl, q6.pl.
When you get to a question where some code is given (either starter code,
or code you’re supposed to find bugs in), copy the code into a file.
In the last question on this practice quiz, this will give singleton
variable warnings, at least one of which points you towards one of the bugs.
You can also try the example, which does not give the correct output:
?- zigzag(node(5, node(6, leaf(7), leaf(8)), leaf(3)), Result).
Result = [6, _1620]
As long as this example keeps giving the wrong output, you know there is at
least one bug left in the code.
(The converse is not true: if the example works, there might still be bugs.)
For “blank page” questions where no code is given, start writing your code in
the appropriate .pl file. Try to test your code as you go.
For a “translate formulas to Prolog” question, the meaning of the formulas
won’t be explained, so you can’t test your code, but you can check that Prolog
loads it without syntax errors. (Singleton variable warnings are okay here.)
*/