reduce, or explicit recursion?

I recently started reading through Paul Graham's On Lisp with a friend, and we realized that we have very different opinions of reduce: I think it expresses a certain kind of recursive form very clearly and concisely; he prefers to write out the recursion very explicitly.

I suspect we're each right in some context and wrong in another, but we don't know where the line is. When do you choose one form over the other, and what do you think about when making that choice?

To be clear about what I mean by reduce vs. explicit recursion, here's the same function implemented twice:

(defun my-remove-if (pred lst)
    (fold (lambda (left right)
                  (if (funcall pred left) 
                      right 
                      (cons left right)))
          lst :from-end t))

(defun my-remove-if (pred lst)
    (if lst
        (if (funcall pred (car lst))
            (my-remove-if pred (cdr lst))
            (cons (car lst) (my-remove-if pred (cdr lst))))
        '()))

I'm afraid I started out a Schemer (now we're Racketeers?) so please let me know if I've botched the Common Lisp syntax. Hopefully the point will be clear even if the code is incorrect.

coding-style lisp

Edit Report

I'm going to take a slightly-subjective question and give a highly-subjective answer, since Ira already gave a perfectly pragmatic and logical one. :-)

I know writing things out explicitly is highly valued in some circles (the Python guys make it part of their "zen"), but even when I was writing Python I never understood it. I want to write at the highest level possible, all the time. When I want to write things out explicitly, I use assembly language. The point of using a computer (and a HLL) is to get it to do these things for me!

For your my-remove-if example, the reduce one looks fine to me (apart from the Scheme-isms like fold and lst :-)). I'm familiar with the concept of reduce, so all I need to understand it is figure out your f(x,y) -> z. For the explicit variant, I had to think it for a second: I have to figure out the loop myself. Recursion isn't the hardest concept out there, but I think it is harder than "a function of two arguments".

I also don't care for a whole line being repeated -- (my-remove-if pred (cdr lst)). I think I like Lisp in part because I'm absolutely ruthless at DRY, and Lisp allows me to be DRY on axes that other languages don't. (You could put in another LET at the top to avoid this, but then it's longer and more complex, which I think is another reason to prefer the reduction, though at this point I might just be rationalizing.)

I think maybe the contexts in which the Python guys, at least, dislike implicit functionality would be:

when no-one could be expected to guess the behavior (like frobnicate("hello, world", True) -- what does True mean?), or:
cases when it's reasonable for implicit behavior to change (like when the True argument gets moved, or removed, or replaced with something else, since there's no compile-time error in most dynamic languages)<

answered 2010-07-05T22:17:03.753

reduce, or explicit recursion?

1 Answer

Your Answer