Costruire un generatore di id pigro, impuro

Question

Mi piacerebbe sapere come creare una sequenza infinita e impura di valori unici in Clojure.

(def generator ...) ; def, not defn 
(take 4 generator) ; => (1 2 3 4) 
(take 4 generator) ; => (5 6 7 8). note the generator's impurity. 

Penso che un tale progetto potrebbe essere più conveniente di ad es. avvolgere un singolo valore intero in un tipo di riferimento e incrementarlo dai suoi utenti, come:

• L'approccio proposto riduce i dettagli di implementazione a un singolo punto di cambiamento: il generatore. Altrimenti tutti i consumatori dovrebbero preoccuparsi sia del tipo di riferimento (atom), sia della funzione concreta che fornisce il valore successivo (inc)
• Le sequenze possono trarre vantaggio da molte funzioni clojure.core. 'Manualmente' costruire un elenco di id da un atomo sarebbe un po 'ingombrante: (take 4 (repeatedly #(swap! _ inc)))

Non sono riuscito a trovare un'implementazione funzionante. È possibile a tutti?

Answer 1

Puoi avvolgere una sequenza pigro intorno una classe impura (come un java.util.concurrent.atomic.AtomicLong) per creare una sequenza id:

(def id-counter (java.util.concurrent.atomic.AtomicLong.)) 

(defn id-gen [] 
    (cons 
    (.getAndIncrement id-counter) 
    (lazy-seq 
    (id-gen)))) 

Questo funziona, ma solo se non lo fai salva la testa della sequenza.Se si crea un var che cattura la testa:

(def id-seq (id-gen)) 

Poi chiamano più volte, verrà restituito ids dall'inizio della sequenza, perché hai tenuto sulla testa della sequenza:

(take 3 id-seq) 
;; => (0 1 2) 
(take 3 id-seq) 
;; => (0 1 2) 
(take 3 id-seq) 
;; => (0 1 2) 

Se si ri-creare la sequenza, però, si otterrà valori freschi a causa della dell'impurità:

(take 3 (id-gen)) 
;; (3 4 5) 
(take 3 (id-gen)) 
;; (6 7 8) 
(take 3 (id-gen)) 
;; (9 10 11) 

ho solo raccomandare facendo quanto segue per scopi educativi (non codice di produzione), ma è possibile creare la propria istanza di iseq che implementa l'impurità in modo più diretto:

(def custom-seq 
    (reify clojure.lang.ISeq 
      (first [this] (.getAndIncrement id-counter)) 
      (next [this] (.getAndIncrement id-counter)) 
      (cons [this thing] 
        (cons thing this)) 
      (more [this] (cons 
          (.getAndIncrement id-counter) 
          this)) 
      (count [this] (throw (RuntimeException. "count: not supported"))) 
      (empty [this] (throw (RuntimeException. "empty: not supported"))) 
      (equiv [this obj] (throw (RuntimeException. "equiv: not supported"))) 
      (seq [this] this))) 

(take 3 custom-seq) 
;; (12 13 14) 
(take 3 custom-seq) 
;; (15 16 17) 

Answer 2

questa è un'altra soluzione, forse:

user=> (defn positive-numbers 
      ([] (positive-numbers 1)) 
      ([n] (cons n (lazy-seq (positive-numbers (inc n)))))) 
#'user/positive-numbers 
user=> (take 4 (positive-numbers)) 
(1 2 3 4) 
user=> (take 4 (positive-numbers 5)) 
(5 6 7 8) 

Answer 3

ho avuto un momento di divertimento alla scoperta di qualcosa durante rispondere alla tua domanda. La prima cosa che mi è venuta in mente è che forse, per qualunque obiettivo finale ti servano questi ID, la funzione gensym potrebbe essere utile.

Poi, ho pensato "beh, ehi, sembra aumentare un contatore impuro per generare nuovi ID" e "beh, cosa c'è nel codice sorgente?" Il che mi ha portato a questo:

(. clojure.lang.RT (nextID)) 

Che sembra fare quello che ti serve. Freddo! Se si desidera utilizzare nel modo che suggerisci, allora avrei probabilmente renderla una funzione:

(defn generate-id [] 
    (. clojure.lang.RT (nextID))) 

allora si può fare:

user> (repeatedly 5 generate-id) 
=> (372 373 374 375 376) 

non ho ancora testato se questo produrrà sempre valori univoci "globalmente" - Non sono sicuro della terminologia, ma sto parlando di quando potresti usare questa funzione generate-id da thread diversi, ma vuoi essere sicuro che stia producendo valori univoci.

Answer 4

Un modo che sarebbe più idiomatica, thread-safe, e invita senza stranezze sui riferimenti di testa sarebbe quella di utilizzare una chiusura su una delle clojures built in riferimenti mutabili. Ecco un rapido esempio che ho elaborato dal momento che stavo avendo lo stesso problema. Si chiude semplicemente su un rif.

(def id-generator (let [counter (ref 0)] 
       (fn [] (dosync (let [cur-val @counter] 
         (do (alter counter + 1) 
          cur-val)))))) 

Ogni volta che si chiama (id-generator) si otterrà il numero successivo nella sequenza.

Answer 5

Ecco un altro modo veloce:

user> (defn make-generator [& [ii init]] 
    (let [a (atom (or ii 0)) 
     f #(swap! a inc)] 
    #(repeatedly f))) 
#'user/make-generator 
user> (def g (make-generator)) 
#'user/g 
user> (take 3 (g)) 
(1 2 3) 
user> (take 3 (g)) 
(4 5 6) 
user> (take 3 (g)) 
(7 8 9) 

Answer 6

Questo è mod ma funziona ed è estremamente semplice

; there be dragons ! 
(defn id-gen [n] (repeatedly n (fn [] (hash #())))) 
(id-gen 3) ; (2133991908 877609209 1060288067 442239263 274390974) 

Fondamentalmente clojure crea una funzione di 'anonymous', ma dal momento che clojure itselfs ha bisogno di un nome per questo, usa gli impuri univoci per evitare le collisioni. Se hai un nome univoco, dovresti ottenere un numero univoco.

Speranza che aiuta

Answer 7

Creazione di identificatori da una raccolta arbitraria di identificatori di semi:

(defonce ^:private counter (volatile! 0)) 

(defn- next-int [] 
    (vswap! counter inc)) 

(defn- char-range 
    [a b] 
    (mapv char 
     (range (int a) (int b)))) 

(defn- unique-id-gen 
    "Generates a sequence of unique identifiers seeded with ids sequence" 
    [ids] 
    ;; Laziness ftw: 
    (apply concat 
     (iterate (fn [xs] 
        (for [x xs 
          y ids] 
         (str x y))) 
        (map str ids)))) 

(def inf-ids-seq (unique-id-gen (concat (char-range \a \z) 
             (char-range \A \Z) 
             (char-range \0 \9) 
             [\_ \-]))) 

(defn- new-class 
    "Returns an unused new classname" 
    [] 
    (nth inf-ids-seq (next-int))) 

(repeatedly 10 new-class) 

dimostrazione:

(take 16 (unique-id-gen [\a 8 \c])) 
;; => ("a" "8" "c" "aa" "a8" "ac" "8a" "88" "8c" "ca" "c8" "cc" "aaa" "aa8" "aac" "a8a")