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:

## 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``