How to write a predicate that checks if a value exists in infinite seq?

Question

I had an idea for a higher order function today that I'm not sure how to write. I have some rare, lazy infinite sequences, and I want to create an abstraction that allows me to check if a given number is in any of these lazy sequences. To improve performance, I wanted to push the sparse sequence values ​​into the hash map (or set), dynamically increasing the number of values ​​in the hash map whenever necessary. Automatic memoization is not the answer here due to the limited lazy sections.

The code is probably the easiest to understand, so here is what I still have. How to change the following code so that the predicate uses a closed hash file, but if necessary increases the size of the hash map and redefines itself to use the new hash file?

(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 to solve this problem without returning to the imperative style?

Answer 1

This is a thread-safe version 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])))) 

You might also consider using links, but your crawl search might be a rollback of an attached transaction. This may or may not be what you want.

Answer 2

This function is based on the idea of ​​how memoize function works. Only numbers already consumed from the lazy list are cached in the set. It uses a built-in capture instead of performing a manual search.

 (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)))))))