sicp-ex-4.68



<< Previous exercise (4.67) | Index | Next exercise (4.69) >>


meteorgan

  
  
 rule: 
 (assert! (rule (reverse () ()))) 
 (assert! (rule (reverse ?x ?y) 
                (and (append-to-form (?first) ?rest ?x) 
                     (append-to-form ?rev-rest (?first) ?y) 
                     (reverse ?rest ?rev-rest)))) 
  
 (reverse (1 2 3) ?x)  : infinite loop 
 ;;; Query input: 
 (reverse ?x (1 2 3)) 
  
 ;;; Query output: 
 (reverse (3 2 1) (1 2 3)) 

poly

My solution based on the following procedure.

  
 (define (reverse seq) 
   (if (null? seq) 
       '() 
       (append (reverse (cdr seq)) (list (car seq))))) 

So, there will be two rules:

--1st: an empty list will be got if reverse an empty list.

--2nd: for x y v z, we will get a reversed seq 'z' of (cons x y) only if 'v' is a reversed seq of 'y' and 'z' is (append v '(x))

(assert! (rule (reverse () ())))

(assert! (rule (reverse (?x . ?y) ?z)
               (and (reverse ?y ?v)
                    (append-to-form ?v (?x) ?z)))))

the above one will work for (reverse (1 2 3) ?x), but end up with an infinite loop for (reverse ?x (1 2 3)). But this situation will be opposite if change the order of sequence like:

(assert! (rule (reverse () ())))

(assert! (rule (reverse (?x . ?y) ?z)
               (and (append-to-form ?v (?x) ?z)  ;; changed
                    (reverse ?y ?v)))))          ;;