Thanks for explaining how one creates a trampolined version from the cps
version! This makes sense.
Thanks also for alerting me to potential issues with the concat laziness.
From a code efficiency point of view, producing a lazy something and then
immediately evaluating it is inefficient. It is better to use a strict
version of the something in the first place. Does Clojure provide strict
versions of things like concat, or would I need to roll-my-own?
Thinking again of efficiency... I had a go at doing an
accumulator-passing-style (APS) version of flatten. Here it is...
(defn my-apsbased-flatten
[xs]
(letfn [(my-flatten-aps [xs avec]
(if (nil? xs)
avec
(let [x (first xs), ys (next xs)]
(if (sequential? x)
(recur ys (into avec (my-flatten-aps (seq x) '[])))
(recur ys (conj avec x))))))]
(seq (my-flatten-aps (seq xs) '[]))))
This is more efficient (I think) than my earlier cps-based flatten. But it
has the problem again of using the stack via the non-recur call to
my-flatten-aps.
I'm wondering if it's somehow possible to modify this aps implementation to
also use trampolining?
Alternatively, maybe there's a combination aps-cps variation which can be
trampolined?? I've had a bit of a go at this and so far can't see how to
do it. Perhaps not, as APS seems to do pre-calculation whereas CPS seems
to do post-calculation?
But I can't help thinking that there must be a more efficient trampolined
version of flatten that utilizes the structure of the "flatten problem"
more, like APS does?
Cheers,
Mark.
On Tuesday, 15 July 2014 19:25:26 UTC+9:30, puzzler wrote:
>
> Yes, here's the trampolined version which won't stack overflow:
>
> (defn my-flatten
> [xs]
> (letfn [(my-flatten-cps [xs k]
> (if (nil? xs)
> (k '())
> (let [x (first xs), ys (next xs)]
> (if (sequential? x)
> (recur ys (fn [v] (fn [] (my-flatten-cps (seq x) (fn [w]
> (fn [] (k (doall (concat w v)))))))))
> (recur ys (fn [v] #(k (conj v x))))))))]
> (trampoline my-flatten-cps (seq xs) identity)))
>
> Basically, you just wrap the body of each continuation in a function of no
> arguments, and call the recursive function with trampoline.
>
> Another thing you have to do is wrap the concat in a doall, otherwise
> you'll get a stack overflow when the deeply nested lazy concatenation is
> realized.
>
>
> On Tue, Jul 15, 2014 at 12:13 AM, Mark P <[email protected] <javascript:>>
> wrote:
>
>> I'm very new to continuation passing style (CPS), and as part of the
>> learning process I've done a CPS version of a "flatten" function. Ie, it
>> does the same thing as the standard clojure "flatten", but is implemented
>> using a recursive local CPS helper function. I'm interested in comments /
>> critiques on what I've done.
>>
>> Here it is...
>>
>> (defn my-flatten
>> [xs]
>> (letfn [(my-flatten-cps [xs k]
>> (if (nil? xs)
>> (k '())
>> (let [x (first xs), ys (next xs)]
>> (if (sequential? x)
>> (recur ys (fn [v] (my-flatten-cps (seq x) (fn [w] (k
>> (concat w v))))))
>> (recur ys (fn [v] (k (conj v x))))))))]
>> (my-flatten-cps (seq xs) identity)))
>>
>> I'm relatively inexperienced with clojure, so please feel free to suggest
>> improvements to my clojure code.
>>
>> But what I'm most interested in is understanding CPS better and about how
>> it interacts with Clojure and with "recur". As you can see, my-flatten-cps
>> uses recur nicely to traverse at a breadth level. But as we sink down into
>> depth, I've done an actual non-recur call to my-flatten-cps. I presume I
>> can't do a recur here instead (because it would attempt to jump to the most
>> immediate fn??) - is this correct?
>>
>> Is there any way around this? (As I write this, the word "trampoline"
>> comes to mind - some videos I've watched speak of this - but not sure how
>> this would work and what efficiency trade-offs would be involved.)
>>
>> The other things is... is it so bad that it is not fully using recur -
>> maybe using a bit of stack is okay??
>>
>> Thanks,
>>
>> Mark.
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Clojure" group.
>> To post to this group, send email to [email protected]
>> <javascript:>
>> 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] <javascript:>
>> 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] <javascript:>.
>> For more options, visit https://groups.google.com/d/optout.
>>
>
>
--
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.
