Due by 11:59pm on Wednesday, 8/3

Instructions

Download hw09.zip. Inside the archive, you will find a file called hw09.logic, along with a copy of the OK autograder.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. See Lab 0 for instructions on submitting assignments.

Using OK: If you have any questions about using OK, please refer to this guide.

Readings: You might find the following references useful:

• 4.4

Logic

Question 1: Unique

Write facts for unique, a relation that holds for any list that has no duplicate elements.

Hint: Use the in relation, which is provided for you.

(fact (in ?elem (?elem . ?rest)))
(fact (in ?elem (?first . ?rest))
      (in ?elem ?rest))

; Define the unique relation here!

; (query (unique (1 2 3)))
; expect Success!
; (query (unique ()))
; expect Success!
; (query (unique (1 2 3 3 4)))
; expect Failed.
; (query (unique (1 2 3 1)))
; expect Failed.

Use OK to test your code:

python3 ok -q unique

Question 2: Add to all

Write facts for add-to-all, which declares a relation between an item, a list of lists, and a second list whose elements are the elements of the first list with the item added to the front of each:

; Define the add-to-all relation here!

; (query (add-to-all a ((b) (c d)) ((a b) (a c d))))
; expect Success!
; (query (add-to-all a ((b c) (b) (foo)) ?what))
; expect Success! ; what: ((a b c) (a b) (a foo))
; (query (add-to-all ?what ((c) (d e) ()) ((b c) (b d e) (b))))
; expect Success! ; what: b
; (query (add-to-all ?what ?list ((b c) (d e) (b))))
; expect Failed.

Use OK to test your code:

python3 ok -q add-to-all

Question 3: Sublists

Write facts for sublists, which relates a list of items to another list that contains every possible sublist of the first. A sublist of a list is a list that contains zero or more items from the original list, in the same order that they appear in the original list:

Hint: Use the append relation, which is provided for you, and the add-to-all relation, which you implemented in the previous question.

(fact (append () ?a ?a))
(fact (append (?x . ?r) ?b (?x . ?c))
      (append ?r ?b ?c))

; Define the sublists relation here!

; (query (sublists (1 2 3) ?subs))
; expect Success! ; subs: (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

Use OK to test your code:

python3 ok -q sublists