Is recursion a smell (in idiomatic Clojure) because of of zippers and HOFs?

Question

The classic book The Little Lisper (The Little Schemer) is founded on two big ideas

1. You can solve most problems in a recursive way (instead of using loops) (assuming you have Tail Call Optimisation)
2. Lisp is great because it is easy to implement in itself.

Now one might think this holds true for all Lispy languages (including Clojure). The trouble is, the book is an artefact of its time (1989), probably before Functional Programming with Higher Order Functions (HOFs) was what we have today.(Or was at least considered palatable for undergraduates).

The benefit of recursion (at least in part) is the ease of traversal of nested data structures like ('a 'b ('c ('d 'e))).

For example:

(def leftmost
  (fn [l]
    (println "(leftmost " l)
    (println (non-atom? l))
    (cond
      (null? l) '()
      (non-atom? (first l)) (leftmost (first l))
      true (first l))))

Now with Functional Zippers - we have a non-recursive approach to traversing nested data structures, and can traverse them as we would any lazy data structure. For example:

(defn map-zipper [m]
  (zip/zipper 
    (fn [x] (or (map? x) (map? (nth x 1))))
    (fn [x] (seq (if (map? x) x (nth x 1))))
    (fn [x children] 
      (if (map? x) 
        (into {} children) 
        (assoc x 1 (into {} children))))
    m))

(def m {:a 3 :b {:x true :y false} :c 4})

(-> (map-zipper m) zip/down zip/right zip/node)
;;=> [:b {:y false, :x true}]

Now it seems you can solve any nested list traversal problem with either:

• a zipper as above, or
• a zipper that walks the structure and returns a set of keys that will let you modify the structure using assoc.

Assumptions:

• I'm assuming of course data structures that fixed-size, and fully known prior to traversal
• I'm excluding the streaming data source scenario.

My question is: Is recursion a smell (in idiomatic Clojure) because of of zippers and HOFs?

Aggressor

It may be a smell, but not one unpleasant to the particular problems at hand. For example, processing unstructured (or ambiguous) input to produce something structured and deterministic. – Britannia

Could you give an answer and provide an example? It sounds like something from Norvig's Paradigms of Artificial Intelligence Programming – Aggressor

Answer 1

I would say that, yes, if you are doing manual recursion you should at least reconsider whether you need to. But I wouldn't say that zippers have anything to do with this. My experience with zippers has been that they are of theoretical use, and are very exciting to Clojure newcomers, but of little practical value once you get the hang of things, because the situations in which they are useful are vanishingly rare.

It's really because of higher-order functions that have already implemented the common recursive patterns for you that manual recursion is uncommon. However, it's certainly not the case that you should never use manual recursion: it's just a warning sign, suggesting you might be able to do something else. I can't even recall a situation in my four years of using Clojure that I've actually needed a zipper, but I end up using recursion fairly often.

Arrestment

Answer 2

Clojure idioms discourage explicit recursion because the call stack is limited: usually to about 10K deep. Amending the first of Halloway & Bedra's Six Rules of Clojure Functional Programming (Programming Clojure (p 89)),

Avoid unbounded recursion. The JVM cannot optimize recursive calls and Clojure programs that recurse without bound will blow their stack.

There are a couple of palliatives:

• recur deals with tail recursion.
• Lazy sequences can turn a deep call stack into a shallow call stack
  across an unfolding data structure. Many HOFs in the sequence
  library, such as map and filter, do this.

Neese

Sure - I think the question behind it was "are there scenarios where you have to resort to recursion"? – Aggressor

hawkeye, another question worth asking: Are there scenarios where recursion is easier to understand? (I find your recursive definition easier to understand than your zipper function, but that's me. Others may find the zipper version clearer, and that's fine.) The fact that Clojure doesn't support full-fledged tail-call optimization is largely an artifact of being implemented on the JVM. But note that TCO won't necessarily help when traversing tree structures. – Maldives

@Aggressor I think you can always substitute closures for recursion by 1) converting the functions to continuation passing style and 2) in Clojure, using trampoline to flatten the mutual tail calls. This process moves the recursion from the stack to the heap. – Neese

@Aggressor There's a link to the Wikipedia article on continuation passing style in my previous comment. The code is in Scheme. I hope you're OK with that. There are several good accounts of trampoline around - I'm guessing you know about trampoline. – Neese

@Neese - I was looking for an example in Clojure. – Aggressor

@Aggressor Look and ye shall find: here and here in StackOverflow. – Neese