How to simulate an 'outer join' in core.logic?

Question

I've just started playing with core.logic, and to work on it I'm trying to implement something simple that is similar to a problem that I am currently working on professionally. However, one part of the problem has me stumped...

As a simplification of my example, if I have a catalog of items, and some of them are only available in certain countries, and some are not available in specific countries. I'd like to be able specify the list of items, and the exceptions, something like:

(defrel items Name Color)
(defrel restricted-to Country Name)
(defrel not-allowed-in Country Name)

(facts items [['Purse 'Blue]
              ['Car 'Red]
              ['Banana 'Yellow]])

(facts restricted-to [['US 'Car]])

(facts not-allowed-in [['UK 'Banana]
                       ['France 'Purse]])

If possible, I'd rather not specify allowed-in for all countries, as the set of items with restrictions is relatively small, and I'd like to be able to make a single change to allow/exclude for an item for a given country.

How can I write a rule that gives the list of items/colors for a country, with the following constraints:

• The item must be in the list of items
• The country/item must be not be in the 'not-allowed-in' list
• Either:
  • There is no country in the restricted-to list for that item
  • The country/item pair is in the restricted-to list

Is there some way to do this? Am I thinking about things in entirely the wrong way?

Answer 1

Usually when you start negating goals in logic programming, you need to reach for non-relational operations (cut in Prolog, conda in core.logic).

This solution should only be called with ground arguments.

(defn get-items-colors-for-country [country]
  (run* [q]
    (fresh [item-name item-color not-country]
      (== q [item-name item-color])
      (items item-name item-color)
      (!= country not-country)

      (conda
        [(restricted-to country item-name)
         (conda
           [(not-allowed-in country item-name)
            fail]
           [succeed])]
        [(restricted-to not-country item-name)
         fail]
        ;; No entry in restricted-to for item-name
        [(not-allowed-in country item-name)
         fail]
        [succeed]))))

(get-items-colors-for-country 'US)
;=> ([Purse Blue] [Banana Yellow] [Car Red])

(get-items-colors-for-country 'UK)
;=> ([Purse Blue])

(get-items-colors-for-country 'France)
;=> ([Banana Yellow])

(get-items-colors-for-country 'Australia)
;=> ([Purse Blue] [Banana Yellow])

Full solution

Answer 2

Conda may complexifies the code, using nafc, you can more easily reorder goals if you want. This is still non-relational ! :)

(ns somenamespace
  (:refer-clojure :exclude [==])
  (:use [clojure.core.logic][clojure.core.logic.pldb]))

(db-rel items Name Color)
(db-rel restricted-to Country Name)
(db-rel not-allowed-in Country Name)

(def stackoverflow-db 
  (db [items 'Purse 'Blue]
      [items  'Car 'Red]
      [items 'Banana 'Yellow]
      [restricted-to 'US 'Car]
      [not-allowed-in 'UK 'Banana]
      [not-allowed-in 'France 'Purse]))


(defn get-items-colors-for-country [country]
  (with-db stackoverflow-db
    (run* [it co]
         (items  it co)
         (nafc not-allowed-in country it)
         (conde 
          [(restricted-to country it)]
          [(nafc #(fresh [not-c] (restricted-to not-c %)) it)]))))

(get-items-colors-for-country 'US)
;=> ([Purse Blue] [Banana Yellow] [Car Red])

(get-items-colors-for-country 'UK)
;=> ([Purse Blue])

(get-items-colors-for-country 'France)
;=> ([Banana Yellow])

(get-items-colors-for-country 'Australia)
;=> ([Purse Blue] [Banana Yellow])

For more examples : https://gist.github.com/ahoy-jon/cd0f025276234de464d5