On Wed, Oct 14, 2009 at 2:06 AM, Mark Tomko <[email protected]> wrote:
>
> This is basically a problem of parallel iteration. I've devised 2
> solutions, one is recursive (alas, not tail-recursive) and the other
> appears to be a more idiomatic Clojure solution. Can someone suggest
> a more efficient or cleaner solution?
>
Meikel provided a quickie high-level-function solution, but I thought I
might take a look at this anyway:
Here's the "literal" solution:
>
> (defn matching-elements [coll1 coll2]
> (if (or (empty? coll1) (empty? coll2)) ()
> (let [e1 (first coll1) e2 (first coll2)]
> (if (= e1 e2) (cons e1 (matching-elements (rest coll1) (rest
> coll2)))
> (matching-elements (rest coll1) (rest coll2))))))
>
First of all, the second matching-elements call is in tail position, so you
can improve this to:
(defn matching-elements [coll1 coll2]
(if (or (empty? coll1) (empty? coll2))
()
(let [e1 (first coll1) e2 (first coll2)]
(if (= e1 e2)
(cons e1 (matching-elements (rest coll1) (rest coll2)))
(recur (rest coll1) (rest coll2))))))
But it can be made fully tail-recursive:
(defn- matching-elements* [coll1 coll2 res]
(if (or (empty? coll1) (empty? coll2))
res
(let [e1 (first coll1) e2 (first coll2)]
(if (= e1 e2)
(recur (rest coll1) (rest coll2) (cons e1 res))
(recur (rest coll1) (rest coll2) res)))))
(defn matching-elements [coll1 coll2]
(matching-elements* coll1 coll2 nil))
This handy trick is described fairly early in SICP and can generally be
applied almost anywhere where you're "almost" tail recursive, because you do
something to massage the return value of the recursive call on the way out
but don't make multiple recursive calls on a single path through the
function.
I believe that the cons prevents the use of recur to make this tail
> recursive.
>
Only on the first recursive call, and only if the above trick isn't
employed.
> After a little digging and reading through a thread on this group
> about parallel iteration, I devised the following alternative
> solution, which makes use of lazy sequences:
>
> (defn matching-elements2 [coll1 coll2]
> (map first (filter #(let [[e1 e2] %] (= e1 e2)) (partition 2
> (interleave coll1 coll2)))))
>
That's clever, though it's eclipsed by Meikel's. Apparently you didn't
realize that map and friends can tandem-iterate more than one sequence at a
time. Understandable enough if you're fairly new to Clojure.
> Can anyone suggest an improved implementation of either
> implementation?
Meikel improved the second; I improved the first, above, not because it's
better than Meikel's but because I think it might be enlightening to many
readers here interested in tail recursion and, more generally, in design and
optimization of recursive functions.
HTH, HAND, and all that.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
