Comment écrire un prédicat qui vérifie si une valeur existe dans un seq infini?

Question

J'ai eu une idée pour une fonction d'ordre supérieur aujourd'hui que je ne suis pas sûr de savoir comment écrire. J'ai plusieurs séquences infinies, paresseuses, et je veux créer une abstraction qui me permet de vérifier si un nombre donné est dans l'une de ces séquences paresseuses. Pour améliorer les performances, je voulais pousser les valeurs de la séquence fragmentée dans un hashmap (ou ensemble), en augmentant dynamiquement le nombre de valeurs dans le hashmap chaque fois que cela est nécessaire. Mémo automatique n'est pas la réponse ici en raison de la parcimonie des seqs paresseux. Le code est probablement le plus facile à comprendre, alors voici ce que j'ai jusqu'à présent. Comment puis-je modifier le code suivant afin que le prédicat utilise un hashmap fermé, mais si nécessaire, augmente la taille du hashmap et redéfinit lui-même pour utiliser le nouveau 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)))) 

Comment résoudre ce problème sans revenir à un style impératif?

Answer 1

Ceci est une variante de la solution d'Adam qui est sûre pour les threads.

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

On pourrait également envisager d'utiliser refs, mais que votre recherche sous-jacente pourrait obtenir annulée par une transaction englobante. Cela pourrait ou ne pas être ce que vous voulez.

Answer 2

Cette fonction est basée sur l'idée de fonctionnement de la fonction memoize de base. Seuls les numéros déjà utilisés dans la liste paresseuse sont mis en cache dans un ensemble. Il utilise le take-in intégré au lieu de faire la recherche manuellement.

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