How do I write a predicate that checks if a value exists in an infinite seq?

Question

I had an idea for a higher-order function today that I'm not sure how to write. I have several sparse, lazy infinite sequences, and I want to create an abstraction that lets me check to see if a given number is in any of these lazy sequences. To improve performance, I wanted to push the values of the sparse sequence into a hashmap (or set), dynamically increasing the number of values in the hashmap whenever it is necessary. Automatic memoization is not the answer here due to sparsity of the lazy seqs.

Probably code is easiest to understand, so here's what I have so far. How do I change the following code so that the predicate uses a closed-over hashmap, but if needed increases the size of the hashmap and redefines itself to use the new hashmap?

(defn make-lazy-predicate [coll]
  "Returns a predicate that returns true or false if a number is in
  coll. Coll must be an ordered, increasing lazy seq of numbers."
  (let [in-lazy-list? (fn [n coll top cache]
                        (if (> top n)
                          (not (nil? (cache n)))
                          (recur n (next coll) (first coll) 
                                 (conj cache (first coll)))]
    (fn [n] (in-lazy-list? n coll (first coll) (sorted-set)))))

(def my-lazy-list (iterate #(+ % 100) 1))

(let [in-my-list? (make-lazy-predicate my-lazy-list)]
  (doall (filter in-my-list? (range 10000))))

How do I solve this problem without reverting to an imperative style?

Answer 1

This is a thread-safe variant of Adam's solution.

(defn make-lazy-predicate
  [coll]
  (let [state        (atom {:mem #{} :unknown coll})
        update-state (fn [{:keys [mem unknown] :as state} item]
                       (let [[just-checked remainder]
                             (split-with #(<= % item) unknown)]
                         (if (seq just-checked)
                           (-> state
                             (assoc :mem (apply conj mem just-checked))
                             (assoc :unknown remainder))
                           state)))]
    (fn [item]
      (get-in (if (< item (first (:unknown @state)))
                @state
                (swap! state update-state item))
              [:mem item]))))

One could also consider using refs, but than your predicate search might get rolled back by an enclosing transaction. This might or might not be what you want.

Answer 2

This function is based on the idea how the core memoize function works. Only numbers already consumed from the lazy list are cached in a set. It uses the built-in take-while instead of doing the search manually.

(defn make-lazy-predicate [coll]
  (let [mem (atom #{})
        unknown (atom coll)]
    (fn [item]
      (if (< item (first @unknown))
        (@mem item)
        (let [just-checked (take-while #(>= item %) @unknown)]
          (swap! mem #(apply conj % just-checked))
          (swap! unknown #(drop (count just-checked) %))
          (= item (last just-checked)))))))