Interesting - thank you!
Good to know about "into" as a way to achieve a non-lazy concat - in
conjunction with a vector.
I like your accumulator version - morphing the structure of the input as
you go to achieve the desired result.
I've come up with another version, that passes through both a "result so
far" accumulator and a "still to be computed" stack. It is very much
non-lazy, but that's okay in some applications (a performance feature
even!). Here it is...
(defn my-accandstackbased-flatten
[xs]
(letfn [(flatten-accandstack [xs accvec stackvec]
(if (empty? xs)
(if (empty? stackvec)
accvec
(recur (peek stackvec) accvec (pop stackvec)))
(let [x (first xs), ys (next xs)]
(if (sequential? x)
(recur x accvec (conj stackvec ys))
(recur ys (conj accvec x) stackvec)))))]
(seq (flatten-accandstack xs [] []))))
This has nice recur behaviour and doesn't mess too much with the structure
of the input nested lists. In the case of flatten, retaining structure is
not important (as you nicely illustrated), but there are generalizations of
this kind of function where retaining structure becomes more important.
Now here's the thing... In the above, my stackvec is sort of like a
continuation. It contains a stack of computation to be performed later on.
That sounds very much like a continuation to me (though I am still in the
process of getting my head around this stuff). So I've thought, surely I
could write an "acc and cps" version of my-flatten? Here is what I came up
with...
(defn my-accandcpsbased-flatten
[xs]
(letfn [(flatten-accandcps [xs accvec k]
(if (empty? xs)
(k accvec)
(let [x (first xs), ys (next xs)]
(if (sequential? x)
(recur x accvec (fn [v] (flatten-accandcps ys [] (fn [w]
(k (into v w))))))
(recur ys (conj accvec x) k)))))]
(seq (flatten-accandcps xs [] identity))))
And I could do the trick you showed me with thunks and a trampoline, if I
wanted to make it completely stack-avoiding.
What does this show? I'm not sure.
Presumably the acc and stack version is the most efficient as it uses recur
everywhere?
The structure of the continuation I pass in with the "acc and cps" version
is very similar in complexity to the continuation I passed as part of my
original cps implementation. So where's the gain? I guess the inclusion
of an accvec means that continuations are generated less frequently so that
the overall size and execution time of continuations is smaller? And it is
an improvement over my earlier aps version that used only an acc vector -
because this version has everything in tail-call position and is amenable
to trampolining.
Is this attempt at analysis reasonable? Is there anything else worth
observing etc?
Presumably I could make the "acc and cps" above more lazy using concat,
cons and lazy-seq. I'd need to think about how easy/hard it would be to
make my "acc and stack" version as lazy.
Thanks again for your helpful comments and examples.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
