During this activity, students should be able to:
This activity helps students develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.
This activity can be developed individually or in pairs.
Solve the following set of relational programming exercises using Clojure and the core.logic
library (Clojure’s implementation of MiniKanren). Place all your functions and unit tests in a file called problemset6.clj
.
require
instructions at the top of your source file:
(require '[clojure.test :refer [deftest is run-tests]]) (require '[clojure.core.logic :as logic]) (require '[clojure.core.logic.fd :as fd])
(removeo x lst result)
: This logic function succeeds if it’s able to remove the first occurrence of x
from lst
giving result
. Unit tests:
(deftest test-removeo (is (= [[:b :c :d :e]] (logic/run 1 [q] (removeo :a [:a :b :c :d :e] q)))) (is (= [[:a :b :d :e]] (logic/run 1 [q] (removeo :c [:a :b :c :d :e] q)))) (is (= [:d] (logic/run 1 [q] (removeo q [:a :b :c :d :e] [:a :b :c :e])))) (is (= [] (logic/run 1 [q] (removeo :x [:a :b :c :d :e] q)))) (is (= [[:x :a :b :c :d :e] [:a :x :b :c :d :e] [:a :b :x :c :d :e] [:a :b :c :x :d :e] [:a :b :c :d :x :e] [:a :b :c :d :e :x]] (logic/run 6 [q] (removeo :x q [:a :b :c :d :e])))) (is (= [[:a [:b :c :d :e]] [:b [:a :c :d :e]] [:c [:a :b :d :e]] [:d [:a :b :c :e]] [:e [:a :b :c :d]]] (logic/run* [q1 q2] (removeo q1 [:a :b :c :d :e] q2)))))
(palindromeo lst)
: This logic function succeeds if lst
is a palindrome list (it reads the same from left to right than from right to left). Unit tests:
(deftest test-palindromeo (is (= [:yes] (logic/run 1 [q] (palindromeo []) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (palindromeo [:a]) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (palindromeo [:a :b :c :b :a]) (logic/== q :yes)))) (is (= [] (logic/run 1 [q] (palindromeo [:a :b :c :d]) (logic/== q :yes)))) (is (= '[[] [_0] [_0 _0] [_0 _1 _0] [_0 _1 _1 _0] [_0 _1 _2 _1 _0] [_0 _1 _2 _2 _1 _0]] (logic/run 7 [q] (palindromeo q)))))
(rotateo lst result)
: This logic function succeeds when lst
is rotated left one position giving result
. In other words, the first element of lst
becomes the last element of result
. Unit tests:
(deftest test-rotateo (is (= [:yes] (logic/run 1 [q] (rotateo [:a :b :c :d :e] [:b :c :d :e :a]) (logic/== q :yes)))) (is (= [] (logic/run 1 [q] (rotateo [:a :b :c :d :e] [:a :b :c :d :e]) (logic/== q :yes)))) (is (= [] (logic/run 1 [q] (rotateo [] q)))) (is (= [[:a]] (logic/run 1 [q] (rotateo [:a] q)))) (is (= [[:b :c :d :e :a]] (logic/run 1 [q] (rotateo [:a :b :c :d :e] q)))) (is (= [[:e :a :b :c :d]] (logic/run 1 [q] (rotateo q [:a :b :c :d :e])))) (is (= '[[[_0] [_0]] [[_0 _1] [_1 _0]] [[_0 _1 _2] [_1 _2 _0]] [[_0 _1 _2 _3] [_1 _2 _3 _0]] [[_0 _1 _2 _3 _4] [_1 _2 _3 _4 _0]] [[_0 _1 _2 _3 _4 _5] [_1 _2 _3 _4 _5 _0]] [[_0 _1 _2 _3 _4 _5 _6] [_1 _2 _3 _4 _5 _6 _0]]] (logic/run 7 [q1 q2] (rotateo q1 q2)))))
(evensizeo lst)
and (oddsizeo lst)
: These two logic functions should be defined in a mutually recursive fashion. That is, each one should be defined in terms of the other one. These functions succeed if the number of elements in lst
is even or odd, respectively.
Tip: Remember to use the declare
macro to indicate that a certain function can be called before it’s actually defined. This is necessary whenever you define mutually recursive functions.
Unit tests:
(deftest test-evensizeo-oddsizeo (is (= [:yes] (logic/run 1 [q] (evensizeo []) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (oddsizeo [:x]) (logic/== q :yes)))) (is (= [] (logic/run 1 [q] (evensizeo [:x]) (logic/== q :yes)))) (is (= [] (logic/run 1 [q] (oddsizeo []) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (evensizeo [:a :b :c :d :e :f]) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (oddsizeo [:a :b :c :d :e]) (logic/== q :yes)))) (is (= '[[] [_0 _1] [_0 _1 _2 _3] [_0 _1 _2 _3 _4 _5] [_0 _1 _2 _3 _4 _5 _6 _7]] (logic/run 5 [q] (evensizeo q)))) (is (= '[[_0] [_0 _1 _2] [_0 _1 _2 _3 _4] [_0 _1 _2 _3 _4 _5 _6] [_0 _1 _2 _3 _4 _5 _6 _7 _8]] (logic/run 5 [q] (oddsizeo q)))))
(splito lst a b)
: This logic function succeeds when splitting lst
gives a
and b
. The first, third, fifth, etc. elements of lst
go to a
, while the second, fourth, sixth, etc. elements go to b
. Unit tests:
(deftest test-splito (is (= [:yes] (logic/run 1 [q] (splito [] [] []) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (splito [:a] [:a] []) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (splito [:a :b] [:a] [:b]) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (splito [:a :b :c :d :e :f] [:a :c :e] [:b :d :f]) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (splito [:a :b :c :d :e :f :g] [:a :c :e :g] [:b :d :f]) (logic/== q :yes)))) (is (= [[[:a :c :e] [:b :d :f]]] (logic/run 1 [q1 q2] (splito [:a :b :c :d :e :f] q1 q2)))) (is (= [[:a :b :c :d :e :f :g]] (logic/run 1 [q] (splito q [:a :c :e :g] [:b :d :f])))) (is (= '[[[] [] []] [[_0] [_0] []] [[_0 _1] [_0] [_1]] [[_0 _1 _2] [_0 _2] [_1]] [[_0 _1 _2 _3] [_0 _2] [_1 _3]] [[_0 _1 _2 _3 _4] [_0 _2 _4] [_1 _3]] [[_0 _1 _2 _3 _4 _5] [_0 _2 _4] [_1 _3 _5]]] (logic/run 7 [q1 q2 q3] (splito q1 q2 q3)))))
(equalo lst)
: This logic function succeeds if all the elements contained in lst
unify to the same value, otherwise fails. The function should always succeed if lst
is empty or has only one element. Unit tests:
(deftest test-equalo (is (= [:yes] (logic/run 1 [q] (equalo []) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (equalo [:x]) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (equalo [:x :x]) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (equalo [:x :x :x :x :x]) (logic/== q :yes)))) (is (= [:x] (logic/run 1 [q] (equalo [:x :x q :x])))) (is (= '[_0] (logic/run 1 [q] (equalo [q q q q q q])))) (is (= '([_0 _0 _0 _0 _0]) (logic/run 1 [q1 q2 q3 q4 q5] (equalo [q1 q2 q3 q4 q5])))) (is (= [] (logic/run 1 [q] (equalo [:x :y]) (logic/== q :yes)))) (is (= [] (logic/run 1 [q1 q2] (equalo [q1 q1 q2 q1 q1]) (logic/!= q1 q2)))) (is (= '([] [_0] [_0 _0] [_0 _0 _0] [_0 _0 _0 _0] [_0 _0 _0 _0 _0] [_0 _0 _0 _0 _0 _0]) (logic/run 7 [q] (equalo q)))))
(counto lst result)
: This logic function unifies result
with the number of elements contained in lst
. Unit tests:
(deftest test-counto (is (= [0] (logic/run 1 [q] (fd/in q (fd/interval 0 10)) (counto [] q)))) (is (= [1] (logic/run 1 [q] (fd/in q (fd/interval 0 10)) (counto [:a] q)))) (is (= [2] (logic/run 1 [q] (fd/in q (fd/interval 0 10)) (counto [:a :b] q)))) (is (= [3] (logic/run 1 [q] (fd/in q (fd/interval 0 10)) (counto [:a :b :c] q)))) (is (= [10] (logic/run 1 [q] (fd/in q (fd/interval 0 10)) (counto (repeat 10 :x) q)))) (is (= '([_0]) (logic/run 1 [q] (fd/in q (fd/interval 0 10)) (counto q 1)))) (is (= '([_0 _1 _2 _3 _4]) (logic/run 1 [q] (fd/in q (fd/interval 0 10)) (counto q 5)))) (is (= '([[] 0] [(_0) 1] [(_0 _1) 2] [(_0 _1 _2) 3] [(_0 _1 _2 _3) 4] [(_0 _1 _2 _3 _4) 5] [(_0 _1 _2 _3 _4 _5) 6]) (logic/run 7 [q1 q2] (fd/in q1 q2 (fd/interval 0 10)) (counto q1 q2)))))
(facto n result)
: This logic function succeeds if the factorial of n
is equal to result
. Mathematically, the factorial of an integer number n
greater or equal to zero can be defined recursively as follows:
Unit tests:
(deftest test-facto (is (= [1] (logic/run 1 [q] (facto 0 q)))) (is (= [1] (logic/run 1 [q] (facto 1 q)))) (is (= [720] (logic/run 1 [q] (facto 6 q)))) (is (= [2432902008176640000] (logic/run 1 [q] (facto 20 q)))) (is (= [0 1] (logic/run 2 [q] (facto q 1)))) (is (= [5] (logic/run 1 [q] (facto q 120)))) (is (= [10] (logic/run 1 [q] (facto q 3628800)))) (is (= [:yes] (logic/run 1 [q] (facto 4 24) (logic/== q :yes)))) (is (= [:yes] (logic/run 1 [q] (facto 15 1307674368000) (logic/== q :yes)))) (is (= [[0 1] [1 1] [2 2] [3 6] [4 24] [5 120] [6 720] [7 5040] [8 40320] [9 362880]] (logic/run 10 [n r] (facto n r)))))
(powo base exp result)
: This logic function succeeds if base
raised to the power exp
is equal to result
.
Tip: If you use fresh
variables in your function, make sure to define their finite domains (using an interval between 0 and 100) like this:
(logic/fresh [temp] (fd/in temp (fd/interval 0 100)) ...)
Unit tests:
(deftest test-powo (is (= [:yes] (logic/run 1 [q] (powo 3 2 9) (logic/== q :yes)))) (is (= [32] (logic/run 1 [q] (powo 2 5 q)))) (is (= [5] (logic/run 1 [q] (powo q 2 25)))) (is (= [3] (logic/run 1 [q] (powo 2 q 8)))) (is (= [1] (logic/run 1 [q] (powo q q q)))) (is (= #{[64 1] [8 2] [4 3] [2 6]} (set (logic/run* [a b] (powo a b 64))))) (is (= '[_0] (logic/run 1 [q] (powo q 0 1)))) (is (= (set (range 101)) (set (logic/run* [q] (fd/in q (fd/interval 0 100)) (powo q 1 q))))))
(rangeo start end result)
: This logic function unifies result
with a sequence of incremental integers from start
to end
(inclusive). Unit tests:
(deftest test-rangeo (is (= [[3 4 5 6 7 8 9 10]] (logic/run 1 [q] (rangeo 3 10 q)))) (is (= [[7]] (logic/run 1 [q] (rangeo 7 7 q)))) (is (= [[]] (logic/run 1 [q] (rangeo 10 1 q)))) (is (= [6] (logic/run 1 [q] (fd/in q (fd/interval 1 10)) (rangeo 2 q [2 3 4 5 6])))) (is (= [[2 6]] (logic/run 1 [q1 q2] (fd/in q1 q2 (fd/interval 1 10)) (rangeo q1 q2 [2 3 4 5 6])))) (is (= #{[] [1] [1 2] [1 2 3] [1 2 3 4] [2] [2 3] [2 3 4] [3] [3 4] [4]} (set (logic/run* [q] (logic/fresh [start end] (fd/in start end (fd/interval 1 4)) (rangeo start end q)))))))
The program source file must include at the top the authors’ personal information (name and student id) within comments. For example:
;---------------------------------------------------------- ; Problem Set #6 ; Date: November 28, 2019. ; Authors: ; A01166611 Pepper Pots ; A01160611 Anthony Stark ;----------------------------------------------------------
Also, each function should include a documentation string (docstring) with a brief description of its behavior. For example:
(defn max2 "Returns the largest of the two numbers x and y." [x y] (if (> x y) x y))
To deliver the problemset6.clj
file, please provide the following information:
Only one team member needs to upload the file.
Due date is Thursday, November 28.
This activity will be evaluated using the following criteria:
-10 | The program doesn't contain within comments the author's personal information. |
---|---|
-30 | A docstring is missing in one or more functions. |
10 | The program contains syntax errors. |
1 | The program was plagiarized in whole or in part. |
10-100 | Depending on the amount of exercises that were solved correctly. |