reduce, or explicit recursion?

Question

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.

Answer 1

If you have a choice, you should always express your computational intent in the most abstract terms possible. This makes it easier for a reader to figure out your intentions, and it makes it easier for the compiler to optimize your code. In your example, when the compiler trivially knows you are doing a fold operation by virtue of you naming it, it also trivially knows that it could possibly parallelize the leaf operations. It would be much harder for a compiler to figure that out when you write extremely low level operations.

Answer 2

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)

But reduce in Lisp fails both of these criteria: it's a well-understood abstraction that everybody knows, and that isn't going to change, at least not on any timescale I care about.

Now, I absolutely believe there are some cases where it'd be easier for me to read an explicit function call, but I think you'd have to be pretty creative to come up with them. I can't think of any offhand, because reduce and mapcar and friends are really good abstractions.

Answer 3

In Common Lisp one prefers the higher-order functions for data structure traversal, filtering, and other related operations over recursion. That's also to see from many provided functions like REDUCE, REMOVE-IF, MAP and others.

Tail recursion is a) not supported by the standard, b) maybe invoked differently with different CL compilers and c) using tail recursion may have side effects on the generated machine code for surrounding code.

Often, for certain data structures, many of these above operations are implemented with LOOP or ITERATE and provided as higher-order function. There is a tendency to prefer new language extensions (like LOOP and ITERATE) for iterative code over using recursion for iteration.

(defun my-remove-if (pred list)
   (loop for item in list
         unless (funcall pred item)
         collect item))

Here is also a version that uses the Common Lisp function REDUCE:

(defun my-remove-if (pred list)
  (reduce (lambda (left right)
            (if (funcall pred left) 
                right 
              (cons left right)))
          list
          :from-end t
          :initial-value nil))