atom-backed-lru-cache

(defn lru-cache
  "Returns {:get f :put f} for a cache that evicts the least recently used key."
  [capacity]
  (let [state (atom {:order [] :data {}})
        touch (fn [{:keys [order data]} k]
                (let [order (conj (vec (remove #{k} order)) k)]
                  (if (> (count order) capacity)
                    (let [old (first order)]
                      {:order (vec (rest order)) :data (dissoc data old)})
                    {:order order :data data})))]
    {:get (fn [k]
            (let [v (get-in @state [:data k])]
              (when (some? v) (swap! state touch k))
              v))
     :put (fn [k v]
            (swap! state (fn [s] (assoc-in (touch s k) [:data k] v)))
            v)}))