Re: SICP's exercise 4.68
- From: bh@xxxxxxxxxxxxxxxxxxxxxxx (Brian Harvey)
- Date: Wed, 21 Dec 2005 18:39:10 +0000 (UTC)
s_lesha@xxxxxxx writes:
>(assert! (rule (reverse () ())))
>(assert!
> (rule
> (reverse ?list1 ?list2)
> (and (append-to-form (?x) ?tail ?list1)
> (append-to-form ?head (?x) ?list2)
> (reverse ?tail ?head))))
>
>As for me it looks ok, but stick on (reverse (a) ?x).
Your program is logically correct, but the query system's algorithm isn't quite
smart enough to solve it. I think the problem comes in the clause
> (append-to-form ?head (?x) ?list2)
When this clause is seen, in your example query, the system knows that ?x = a,
but there are no constraints on ?head or ?list2. So, this sub-query matches
(append-to-form (?e1) (a) (?e1 a))
or
(append-to-form (?e1 ?e2) (a) (?e1 ?e2 a))
and so on. Now, as it turns out, the REVERSE clause will eliminate most of
those matches, but the system has to test them all.
The trick is to avoid generating infinitely many matches to sub-queries.
One way to do that is to define a reverse-helper-with-length relation that
includes the two lists and a third list whose only purpose is to be the same
length as those. If you do it right, most matches of sub-queries will be
known to be too long before they get you in trouble.
The most elegant solution I've seen involves a ZIP relation like this:
(zip (a b c) (d e f) ((a d) (b e) (c f)))
With this, and a FORWARD-REVERSE that only works in one direction, you can make
a REVERSE that works in both directions. This still really involves counting,
since ZIP ensures that all three of its list components have the same length.
.
- References:
- SICP's exercise 4.68
- From: Aleksei Smirnoff
- SICP's exercise 4.68
- Prev by Date: SICP's exercise 4.68
- Next by Date: Stalin (Re: Why aren't you using Bigloo?)
- Previous by thread: SICP's exercise 4.68
- Next by thread: SICP's exercise 4.68
- Index(es):
Relevant Pages
|
