How can I help Clojure understand that 0 is the smallest natural number?

Question

It's easy to define a lazy sequence of natural numbers in Clojure: (def N (iterate inc 0)). Unsurprisingly, if we ask Clojure to find the minimum of N using (apply min N), it gets stuck in an infinite regress.

Is there a way to "build in" the fact that (= 0 (min N)) to the data structure of N? Implicitly, we know this, since the increment function inc is strictly increasing. The min function doesn't know how to exploit this knowledge, and instead tries to brute force its way to the answer.

I don't know how to encode this programmatically. I would like a way to construct lazy sequences with additional structure like constraints & relations). I would also like a way to exploit these constraints in order to solve optimization problems (like finding the minimum or infimum of the sequence).

Is there a way to do this in native Clojure? What about with Datomic?

Answer 1

You can use metadata for the specific example you have.

(defn my-range
  ([] (my-range 0))
  ([n] (with-meta
         (cons n (lazy-seq (my-range (inc n))))
         {:onlyincreases true})))

(defn my-min [x] (if (:onlyincreases (meta x)) (first x) (min x)))

(my-min (my-range)) ;; => 0
(my-min (next (my-range))) ;; => 1
(my-min (nnext (my-range))) ;; => 2

If you need something more generalized, you might have to look into creating your own type.