Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
404 - PurelyFunctional.tv Newsletter

Boolean combinators

In the Clojure Tip above, I described a kind of Boolean combinator that lets us build complex rules out of simpler rules. Your task is to build those combinators. Please define:

(defn rule-and
  ([])
  ([rule])
  ([rule1 rule2])
  ([rule1 rule2 & rules]))
(defn rule-or
  ([])
  ([rule])
  ([rule1 rule2])
  ([rule1 rule2 & rules]))
(defn rule-not [rule])

Note that rule-and and rule-or are monoids and so they follow the monoid pattern.

For a bonus, write the functions rule-if (that implements the logical if arrow operator) and rule-iff (that implements the logical if and only if double-arrow operator). Not that rule-if is different from the programming if since it returns true if the condition is false.

Please submit your solutions as comments on this gist.

@steffan-westcott
Copy link

steffan-westcott commented Nov 23, 2020

(defn rule-and
  ([]
    (constantly true))
  ([rule]
    rule)
  ([rule1 rule2]
    (fn [& args]
      (and (apply rule1 args) (apply rule2 args))))
  ([rule1 rule2 & rules]
    (fn [& args]
      (and (apply rule1 args) (apply rule2 args) (apply (apply rule-and rules) args)))))

(defn rule-or
  ([]
    (constantly false))
  ([rule]
    rule)
  ([rule1 rule2]
    (fn [& args]
      (or (apply rule1 args) (apply rule2 args))))
  ([rule1 rule2 & rules]
    (fn [& args]
      (or (apply rule1 args) (apply rule2 args) (apply (apply rule-or rules) args)))))

(defn rule-not [rule]
  (complement rule))

(defn rule-if [p q]
  (rule-or (rule-not p) q))

(defn rule-iff [p q]
  (rule-and
    (rule-if p q)
    (rule-if q p)))

Edit: Changed rule-not to use complement

@NPException
Copy link

NPException commented Nov 23, 2020

(defn rule-and
  ([] (constantly true))
  ([rule] rule)
  ([rule1 rule2]
   #(and (apply rule1 %&) (apply rule2 %&)))
  ([rule1 rule2 & rules]
   (apply rule-and (rule-and rule1 rule2) rules)))

(defn rule-or
  ([] (constantly false))
  ([rule] rule)
  ([rule1 rule2]
   #(or (apply rule1 %&) (apply rule2 %&)))
  ([rule1 rule2 & rules]
   (apply rule-or (rule-or rule1 rule2) rules)))

(defn rule-not [rule]
  #(not (apply rule %&)))

(defn rule-if [rule-p rule-q]
  (rule-or (rule-not rule-p) rule-q))

(defn rule-iff [rule-p rule-q]
  (rule-and (rule-if rule-p rule-q)
            (rule-if rule-q rule-p)))

@mchampine
Copy link

mchampine commented Nov 24, 2020

Note: "every?/some identity" is a hack to pass and/or as functions because you can't take the value of a macro.

(defn mk-rule-combo [dboo andor]
  (fn thisfn
    ([] (fn [] dboo))
    ([rule] rule)
    ([rule1 rule2] (fn [& args] (andor (apply rule1 args) (apply rule2 args))))
    ([rule1 rule2 & rules] (apply thisfn (thisfn rule1 rule2) rules))))

(def rule-and (mk-rule-combo true #(every? identity %&)))
(def rule-or (mk-rule-combo false #(some identity %&)))
(defn rule-not [rule] (fn [& args] (not (apply rule args))))

@steffan-westcott
Copy link

steffan-westcott commented Nov 24, 2020

If we're willing to forego macro expansions (and and or), then we could have this:

(defn junction [f rules]
  (fn [& args]
    (f identity (map #(apply % args) rules))))

(defn rule-and [& rules]
  (junction every? rules))

(defn rule-or [& rules]
  (junction some rules))

(def rule-not complement)

(defn rule-if [p q]
  (rule-or (rule-not p) q))

(defn rule-iff [p q]
  (rule-and (rule-if p q) (rule-if q p)))

Edit: Updated junction to allow short-circuit evaluation

@steffan-westcott
Copy link

steffan-westcott commented Nov 24, 2020

@mchampine Nice! As always, the discussion here leads to more elegant solutions. I suggest though looking at constantly to make a function which takes any number of arguments. (fn [] dboo) is a function which can only take exactly 0 arguments.

@miner
Copy link

miner commented Nov 24, 2020

You can use a macro to generate the similar rule-and and rule-or definitions.

(defmacro mkrule [andor]
  `(fn rule-name#
     ([] (constantly (~andor)))
     ([rule#] rule#)
     ([rule1# rule2#] (fn [& args#] (~andor (apply rule1# args#) (apply rule2# args#))))
     ([rule1# rule2# & rules#] (apply rule-name#
                                      (rule-name# rule1# rule2#)
                                      rules#))))

(def rule-and (mkrule and))

(def rule-or (mkrule or))

@mchampine
Copy link

mchampine commented Nov 24, 2020

@steffan-westcott Yup, the zero args vs any-arity issue didn't show up in my testing, and I didn't notice the lack of generality. Nice solution with junction, btw.

@miner Cool! My macro-fu is weak, so I tend to take refuge in The First Rule of Clojure Macro Club. :) In practice, I wouldn't bother golfing this stuff down (original w/ duplication is fine) but I wanted to offer at least something different. It's fun and educational to see the other approaches here!

@KingCode
Copy link

KingCode commented Nov 25, 2020

Very interesting comments and elegant solutions above! I was working on a macro as well. Since rule-and and rule-or are the only ones where sugar-coating is handy, I ended up adding a number of combinators (rule-xor, rule-oneof, rule-count etc) to try and push the idea further.

I remember writing a logical rule-based system in Java years ago, due to complex specifications written in tabular form, where the outcome was predicated on some 30 rules, some of which required and some optional etc....The naive approach of spaghetti style nested if-else junk would have been a nightmare. This exercise reminds me of that experience (but much more fun and less work:)

(defn monoid* [init body]
  `(fn f# 
     ([] 
      (fn [& ~'xs] ~init))
     ([~'r] 
      (fn [& ~'xs] (~body (apply ~'r ~'xs))))
     ([~'r1 ~'r2] 
      (fn [& ~'xs] (~body(apply ~'r1 ~'xs) (apply ~'r2 ~'xs))))
     ([~'r1 ~'r2 & ~'rs]
      (fn [& ~'xs] 
        (~body(apply ~'r1 ~'xs)
         (~body (apply ~'r2 ~'xs)
          (apply (apply f# ~'rs) ~'xs)))))))

(defn ->1+2ary [ary-1 ary-2]
  `(fn ([~'x] (~ary-1 ~'x))
     ([~'x ~'y] (~ary-2 ~'x ~'y))))

(defmacro defmonoid 
  ([rule-name-sym init cdecl]
   `(def ~rule-name-sym  ~(monoid* init cdecl)))
  ([rule-name-sym init ary1-body ary2-body]
   `(def ~rule-name-sym ~(monoid* init (->1+2ary ary1-body 
                                                 ary2-body)))))
;; utilities for rule counting combinators
(defn ->bit [bool-or-bit] 
  (cond 
    (= 0 bool-or-bit) 0
    (number? bool-or-bit) bool-or-bit
    bool-or-bit 1
    :else 0))

(defn +bool
  ([] 0)
  ([x] (+ (->bit x)))
  ([x y]
   (+ (->bit x) (->bit y))))

;; COMBINATORS 
(defmonoid rule-and true and)

(defmonoid rule-or false or)

(def rule-not complement)

(defn rule-if [p q]
  (rule-or (rule-not p) q))

(defn rule-iff [p q]
  (rule-and (rule-if p q) (rule-if q p)))

(defn rule-xor [p q]
  (rule-and (rule-or p q) (rule-not (rule-and p q))))

(defmonoid rule-oneof (comp boolean identity) identity 
  #(= 1 (+ (->bit %) (->bit %2))))

;; A combinator yielding the number of satisfied rules.
;; Each argument rule is a boolean predicate, or results are undetermined.
(defmonoid rule-count* (+bool) +bool)

;; Same as rule-count*, but rule return types are auto-converted to booleans. 
(defn rule-count [& rules]
  (->> rules (map #(comp boolean %)) 
       (apply rule-count*)))

;; Yields a rule returning the result of applying 'pred to the number 
;; of satisfied rules; 'rules are wrapped/converted to boolean predicates
(defn rule-filter-count [pred rules]
  (let [cmbtr (apply rule-count rules)]
    (fn [& xs]
      (apply (comp pred cmbtr) xs))))

(defn rule-at-least [n & rules]
  (rule-filter-count #(<= n %) rules))

(defn rule-at-most [n & rules]
  (rule-filter-count #(<= % n) rules))

(defn rule-exactly [n & rules]
  (rule-filter-count #(= n %) rules))

;; tests
(-> (rule-and odd? #(< 2 %) #(< % 6))
    (map (range 2 7))) ;; => (false, true, false, true, false)

(-> (rule-or even? #(zero? (rem % 5)))
    (map [2 7 15 300])) ;;=> (true false true true)

(-> (rule-if #(zero? (rem % 4)) even?)
    (map [10 16 3])) ;;=> (true true true)

(-> (rule-iff #(zero? (rem % 2)) even?)
    (map (range 4))) ;;=> (true true true true)

(-> (rule-xor even? odd?)
    (map (range 4))) ;;=> (true true true true)

(-> (rule-xor #(zero? (rem % 5)) #(zero? (rem % 3)))
    (map '(1 2 3 5 10 15 25 30))) 
;;=> (false false true true true false true false) 

(-> (rule-oneof :berlin :rome :new-york)
    (map '({:berlin true} {:rome true} {:new-york :work :rome :home})))
;;=> (true true false)

(-> (rule-oneof :berlin :rome :new-york)
    (map '({} {:rome :ok} {:new-york :work :rome :home})))
;;=> (false true false)

(-> (rule-at-least 2 :berlin :rome :new-york)
    (map '({:berlin :sales} {:new-york :home :rome :overseas} {})))
;;=> (false true false
(-> (rule-at-most 2 :berlin :rome :new-york)
    (map '({:berlin :away :rome :summer} {:rome :summer :berlin 1 :new-york 2} {:new-york :sales})))
;;=> (true false true)

(def can-vote? (rule-and
                (rule-and #(<= 18 (:age %)) :citizen?) 
                (rule-at-least 1 :affiliated? :registered?)))

(->> '({:age 17 :citizen? :acquired} {:age 40 :citizen? :at-birth :registered? :yes}) 
     (map can-vote?)) ;;=> (false true)

EDITS: some refactoring and shameless copy of better ideas: passing and/or directly to the macro from @miner (passing a macro to a fn is a no-no but a macro will take anything), and using complement for rule-not from @steffan-westcott

@KingCode
Copy link

KingCode commented Nov 26, 2020

This is just a thought, but while "testing" rule-if/iff, I remembered that these are tautologies, i.e. that timeless properties such as (rule-iff even? (complement odd?)) and (rule-if #(= 0 (rem % 4)) even?) are always true.

In the limited experience I had with spec and test.check, I have always struggled to identify (timeless) properties: rule-if would probably be a great way to test-discover properties using test.check generators.

Has anyone here tried this before?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment