Как мне написать предикат, который проверяет, существует ли значение в бесконечной последовательности?

Сегодня у меня возникла идея функции высшего порядка, которую я не знаю, как писать. У меня есть несколько разреженных ленивых бесконечных последовательностей, и я хочу создать абстракцию, которая позволяет мне проверять, входит ли данное число в какую-либо из этих ленивых последовательностей. Чтобы повысить производительность, я хотел поместить значения разреженной последовательности в хэш-карту (или набор), динамически увеличивая количество значений в хеш-карте всякий раз, когда это необходимо. Автоматическая запоминание здесь не решение из-за редкости ленивых последовательностей.

Вероятно, код легче всего понять, так что вот что у меня есть. Как изменить следующий код, чтобы предикат использовал закрытый хэш-карту, но при необходимости увеличивал размер хэш-карты и переопределял себя для использования нового хеш-карты?

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

Как мне решить эту проблему, не возвращаясь к императивному стилю?


clojure predicate lazy-sequences
person ivar    schedule 18.07.2010    source источник
comment
Я считаю концептуально сложным доказать, что значение не содержится в бесконечной последовательности.   -  person Svante    schedule 19.07.2010

Ответы (2)


arrow_upward
2
arrow_downward

Это поточно-ориентированный вариант решения Адама.

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

Можно также рассмотреть возможность использования ссылок, но тогда ваш поиск по предикату может быть отменен включающей транзакцией. Это может быть, а может и не быть тем, что вы хотите.

person kotarak    schedule 19.07.2010
comment
Очень хорошо! Я предполагал, что мне придется использовать атомы, чтобы каким-то образом удерживать изменение состояния, но не знал, как именно этого добиться. Мне нравится, как много здесь проделано с разделением, деструктуризацией и входом. Спасибо! - person ivar; 19.07.2010

arrow_upward
1
arrow_downward

Эта функция основана на представлении о том, как работает основная функция memoize. В наборе кэшируются только числа, уже использованные из ленивого списка. Он использует встроенную функцию поиска вместо того, чтобы выполнять поиск вручную.

(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)))))))
person Adam Schmideg    schedule 18.07.2010
comment
Спасибо, Адам! Первое чтение вашего решения помогло мне понять улучшение котарака. - person ivar; 19.07.2010