Programming challenge: wildcard exclusion in cartesian products

[Mark Tarver]

Hi,

You wrote into the Qilang News group with your problem.
This is a solution in 17 lines of Qi for any n-product >= 2.
It falls short of your complete requirement since it uses
generate and then test, rather than interleaving the
two.

(define challenge
   Patterns N X -> (filter (/. Y (member Y Patterns)) (n-product N X)))

(define n-product
    2 X -> (cartesian-product l X X)
    N X -> (cartesian-product c X (n-product (- N 1) X)))

(define cartesian-product
   _ [ ] _ -> [ ]
   c [X | Y] Z -> (append (map (/. W [X | W]) Z) (cartesian-product c Y
Z))
   l  [X | Y] Z -> (append (map (/. W [X W]) Z) (cartesian-product l Y
Z)))

(define filter
    _ [] -> []
    F [X | Y] -> (filter F Y)	where (F X)
    F [X | Y] -> [X | (filter F Y)])

(define member
    _ [] -> false
    X [Pattern | _]  -> true	where (query-prolog [[= Pattern X]])
    X [_ | Patterns] -> (member X Patterns))

Notes:

Pattern filtering is done by a unification test within the member
function.  You
can do this most easily by calling Qi Prolog using query-prolog.
Here's a test.

(42 -) (n-product 3 [a b c])
[[a a a] [a a b] [a a c] [a b a] [a b b] [a b c] [a c a] [a c b] [a c
c]
 [b a a] [b a b] [b a c] [b b a] [b b b] [b b c] [b c a] [b c b] [b c
c]
 [c a a] [c a b] [c a c] [c b a] [c b b] [c b c] [c c a] [c c b] [c c
c]]

OK, remove all lists beginning [a a ....].

(43-) (challenge [[a a | X]] 3 [a b c])
[[a b a] [a b b] [a b c] [a c a] [a c b] [a c c] [b a a] [b a b] [b a
c]
 [b b a] [b b b] [b b c] [b c a] [b c b] [b c c] [c a a] [c a b] [c a
c]
 [c b a] [c b b] [c b c] [c c a] [c c b] [c c c]]

Remove all lists beginning with a or b.

(51-) (challenge [[a | X] [b | X]] 3 [a b c])
[[c a a] [c a b] [c a c] [c b a] [c b b] [c b c] [c c a] [c c b] [c c
c]]

Mark