Thanks, this was very helpful. I am pretty new at Clojure (and
functional programming) - I'm just tinkering with it a bit in my spare
time these days, with an eye towards integrating it into a larger
project once I'm a little more comfortable with it.
Just to follow up on a few things - by SICP, do you mean the book
"Structure and Interpretation of Computer Programs"? That's the most
likely match I could find. I'm not familiar with the book, though, so
I might have another reading project.
So, map et. al let me tandem-iterate multiple sequences? I had an
early implementation that did basically that using the 'for' list
comprehension, but I couldn't figure out how to add an element to my
result for some steps in the iteration and not others. The early
implementation got around this because I was actually writing a method
that would count matching elements, but couldn't return them. It
looked something like this:
(defn count-matching-elements [coll1 coll2]
(reduce +
(for [e1 coll1 e2 coll2]
(if (= e1 e2) 1 0))))
I wanted instead to re-implement this solution as:
(defn count-matching-elements [coll1 coll2] (count (matching-elements
coll1 coll2)))
This was partially for my own debugging purposes, so I could see what
things were being counted.
On Oct 14, 12:23 am, John Harrop <jharrop...@gmail.com> wrote:
> On Wed, Oct 14, 2009 at 2:06 AM, Mark Tomko <mjt0...@gmail.com> 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 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
-~----------~----~----~----~------~----~------~--~---
