This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2018-03-05
Channels
- # beginners (229)
- # cider (54)
- # cljs-dev (187)
- # cljsrn (1)
- # clojure (187)
- # clojure-dev (5)
- # clojure-italy (31)
- # clojure-losangeles (1)
- # clojure-russia (3)
- # clojure-spec (76)
- # clojure-uk (29)
- # clojurescript (94)
- # cursive (18)
- # datascript (8)
- # datomic (26)
- # docker (6)
- # emacs (19)
- # figwheel (6)
- # fulcro (41)
- # garden (1)
- # graphql (1)
- # hoplon (33)
- # jobs (1)
- # jobs-discuss (1)
- # lein-figwheel (14)
- # leiningen (7)
- # nrepl (10)
- # nyc (1)
- # off-topic (2)
- # onyx (2)
- # parinfer (25)
- # portkey (6)
- # powderkeg (1)
- # protorepl (1)
- # re-frame (14)
- # reagent (14)
- # shadow-cljs (31)
- # spacemacs (3)
- # test-check (33)
- # uncomplicate (1)
- # unrepl (40)
- # vim (5)
- # yada (16)
@skuro non fare il misterioso, fuori i nomi! (sì, ti romperò fino a che non usciranno, sorry 😁)
Intuisco il problema, ma se dovessi spiegare la meccanica delle nested recursive lazy-seq
non ce la farei:
(defn lazy-bomb [n]
(letfn [(step2 [[y & ys]] (lazy-seq (cons y (step2 ys))))
(step1 [[x & xs]] (lazy-seq (cons x (step1 (step2 xs)))))]
(take n (step1 (range)))))
(last (lazy-bomb 10000))
;; StackOverflowError
(defn non-lazy-bomb [n]
(letfn [(step2 [[y & ys]] (cons y (step2 ys)))
(step1 [[x & xs]] (cons x (step1 (step2 xs))))]
(step1 (take n (range)))))
(last (non-lazy-bomb 10000))
;;;StackOverflow
Vero, non volevo accusare lazy-seq. Ma l'esempio, senza step2, sarebbe non tail-recursive, ma lo stack non esplode. lazy-seq senza nesting, ha l'interessante properieta' di transformare stack-consuming in heap consuming. Se c'e' nesting, la proprieta' non vale piu'.
>Ma l’esempio, senza step2, sarebbe non tail-recursive, ma lo stack non esplode. scusa, stavo pensando al mio esempio non il tuo — vero e ora ho collegato cosa intendi con l’ultima frase
quindi se sto capendo bene, tu vorresti spiegare perche`
(defn lazy-bomb [n]
(letfn [(step2 [[y & ys]] (lazy-seq (cons y (step2 ys))))
(step1 [[x & xs]] (lazy-seq (cons x (step1 (step2 xs)))))]
(take n (step1 (range)))))
e` stack consuming mentre (defn lazy-bomb [n]
(letfn [(step1 [[x & xs]] (lazy-seq (cons x (step1 xs))))]
(take n (step1 (range)))))
non lo e`?Si'. Anche se vedo dov'e' se ne va lo stack con println debugger, faccio fatica a spiegare il perche' questo accade.
esercizio intellettuale per la maggiorparte, ma il sieve per i numeri primi (naive version) segue questo pattern
(questo per intederci https://clojuredocs.org/clojure.core/lazy-seq#example-542692d3c026201cdc326ff1)
il motivo per cui una (defn foo [[x & y]] (lazy-seq (cons x (foo y))))
non e` stack consuming, e` perche` internamente lazy-seq e` effettivamente un trampoline
(defn lazy-bomb [n]
(letfn [(step2 [g [y & ys]]
(println "step2: " g y)
(lazy-seq (cons y (step2 g ys))))
(step1 [[x & xs]] (let [g (gensym)]
(println "step1: " g x)
(lazy-seq (cons x (step1 (step2 g xs))))))]
(take n (step1 (range)))))
#'user/lazy-bomb
user=> (def x (lazy-bomb 10))
step1: G__152 0
#'user/x
user=> (nth x 0)
step2: G__152 1
step2: G__152 2
step2: G__152 3
step1: G__155 1
0
user=> (nth x 1)
step2: G__152 4
step2: G__155 2
step2: G__152 5
step2: G__155 3
step2: G__152 6
step2: G__155 4
step1: G__158 2
1
user=> (nth x 2)
step2: G__152 7
step2: G__155 5
step2: G__158 3
step2: G__152 8
step2: G__155 6
step2: G__158 4
step2: G__152 9
step2: G__155 7
step2: G__158 5
step1: G__161 3
2
user=> (nth x 3)
step2: G__152 10
step2: G__155 8
step2: G__158 6
step2: G__161 4
step2: G__152 11
step2: G__155 9
step2: G__158 7
step2: G__161 5
step2: G__152 12
step2: G__155 10
step2: G__158 8
step2: G__161 6
step1: G__164 4
3
si, ho fatto qualcosa di simile, ma non sapevo il trick del gensym
per tenere traccia dello stack!
ogni step c'e' un po' delle precedenti lazy-seqs che viene iterato sullo stack fino a che ovviamente non esplode
Dunque, ho una teoria. Mentre una ricorsione normale con lazy-seq
produce un pattern tipo:
(cons 0 (cons 1 (cons ... (lazy-seq n-2, n-1, n))
con la parte non realizzata sempre in fondo, nested lazy-seq
produce qualcosa tipo:
(cons 0 (lazy-seq (cons 2 (cons 3 (cons n-3 (lazy-seq n-2, n-1, n)))))
che e' dovuto al fatto che l'ultima cosa prima di ritornare un risultato e' sempre una chiamata ricorsiva a step1
(infatti "step1: G__" e' sempre l'ultimo print). La cons
da un numero ad una lazy-seq
non realizzata e' sempre in testa, quindi dev'essere traversata sullo stack "modello tunnel" per arrivare al fondo e prendere un nuovo item. Ed ogni giro cresce la larghezza delle cons
centrali.