Review - Logic


Remember that every code prompt in this worksheet is interactive! Type in Logic code, and press Ctrl-Enter to evaluate facts and queries.

On Append

Remember the append relation that we saw in class:

(fact (append () ?lst ?lst)) (fact (append (?f . ?r1) ?lst (?f . ?r2)) (append ?r1 ?lst ?r2))
(query (append ?what (3 4) (1 2 3 4)))

Write a fact last, which checks if an item is the last element of a list.

;; YOUR CODE HERE (query (last (1 2 3) 3)) ; Success! (query (last (1 2 3) ?x)) ; Success! ; ?x: 3

The palindrome relation indicates that a list is the same backward and forward. Write palindrome using only append.

;; YOUR CODE HERE (query (palindrome a b c a)) ; Failed. (query (palindrome a b c b a)) ; Success! (query (palindrome a b b a)) ; Success! (query (palindrome a ?x c b ?y)) ; Success! ; ?x: b ; ?y: a

A New Subset

Remember the subsets relation that we wrote in the homework which finds a list of all the subsets of a given set? Let's now write a relation subset that checks if a set is a subset of another set. We will represent a set as a sorted list.

;; YOUR CODE HERE (query (subset () (hi))) ; Success! (query (subset (b d e) (a b c d e))) ; Success! (query (subset (b c f) (a b c d e))) ; Faliure. (query (subset ?set (1 2 3))) ; Success! ; ?set: () ; ?set: (3) ; ?set: (2) ; ?set: (2 3) ; ?set: (1) ; ?set: (1 3) ; ?set: (1 2) ; ?set: (1 2 3)

Notice that by just stating what a subset is, we can get logic to enumerate all subsets of a set for us. How cool is that!

Tree Manipulation

We shall now represent trees in logic! Suppose we represent a tree by a list (entry left right) and represent a null tree by the empty list (). We also have a few relations that extracts the left, right and entry of a tree.

Write relations for in-tree, which checks if a tree has a specific entry.

(fact (t-left (?entry ?left ?right) ?left)) (fact (t-right (?entry ?left ?right) ?right)) (fact (t-entry (?entry ?left ?right) ?entry)) (fact (bst (3 (1 () (2 () ())) (5 (4 () ()) (6 () ()))))) ; Represents this tree: ; -3- ; / \ ; 1 5 ; \ / \ ; 2 4 6 (query (t-entry ?left-tree ?what) (t-left ?bst ?left-tree) (bst ?bst)) ;; YOUR CODE HERE (fact (in-bst ?x) (bst ?bst) (in-tree ?bst ?x)) (query (in-bst 4)) ; Success! (query (in-bst 7)) ; Failure. (query (in-bst ?x)) ; Success! ; ?x: 3 ; ?x: 1 ; ?x: 2 ; ?x: 5 ; ?x: 4 ; ?x: 6

Can you tell what order the leaves of the tree appear in? Hint: do you know what kind of search the logic interpreter does when it tries to match patterns?