On Thu, Sep 15, 2011 at 8:56 AM, Herwig Hochleitner <hhochleit...@gmail.com> wrote: > Hi, > > as you might know, the original version actually does run in fixed > stack space, thanks to lazy sequences.
You are right! Without testing it I had thought that the way recursion was used would cause skl to overflow the stack if the input tree was very deep on its first elements. > (defn skl > [tree] > (map skl (filter seq? tree))) But in testing this skl fn I couldn't get it to overflow. This is because the tree is not flattened, and so calling 'first' on the top level of the resulting tree only forces the top-level map, whose first item remains a lazy seq, neatly avoiding an overflow error. Good catch, Herwig! > Consider > > (defn find-in-tree > ([tree pred?] > (concat > (filter pred? tree) > (mapcat find-in-tree (filter sequential? tree) (repeat pred?))))) > > which of course is much simpler written as > > (defn find-in-tree > ([tree pred?] (filter pred? (flatten tree)))) > > all of which are lazy, hence consume constant stack space Alas, this suffers from exactly the problem that I incorrectly believed skl suffered from. It works fine for some trees: (find-in-tree (reduce list (range 1000)) #(when-not (seq? %) (even? %))) ;=> (0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 174 176 178 180 182 184 186 188 190 192 194 196 198 200 202 204 ...) But the lazy seqs form a chain so that in order to return the first element of the result, they seqs must each force the next in the chain, consuming call stack frames as they go. Provide a tree deep enough and it overflows the stack: (find-in-tree (reduce list (range 10000)) #(when-not (seq? %) (even? %))) ; StackOverflowError clojure.lang.RT.boundedLength (RT.java:1607) Nevertheless let us now marvel for a moment at the beauty of lazy seqs, that they can sometimes avoid both premature computation and stack overflows, even in cases where no amount of tail-call-optimization would help! And all this while delivering code so similar to the problem statement and therefore concise, compared to the long and tortured loop/recur version I posted yesterday. --Chouser -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
