Tree recursion in Clojure

Question

I'm trying to translate some exercises from The Little Schemer into Clojure. The idea is to produce a variant of map that works on collections of nested lists.

(defn treemap [f tr]
      (if (list? tr)
        (if (empty? tr)
          ()
          (cons (treemap f (first tr))
                (treemap f (rest tr))))
        (f tr)))

In my example I call this on a mocked-up html page

(html

 (head (title "the fortune cookie institute"))
 (body
  (h1 "Welcome to the Fortune Cookie Institute")
  (p "Our fortunes are guaranteed accurate no matter what.")
  (br)
  (p "Like these")
  (ol
   (li "You will gain weight")
   (li "Taxes will rise")
   (li "Fusion power will always be 50 years away"))
  (br)
  (p "Submit your own fortunes to fortunes@fci.org!")))

In the example I call treemap with a function called SHOUT that substitutes all p tags for h1.

My question is this. My goal here is to show my students that there are things you can do with recursion that you can't do with a for loop. But I know that what I've written here is inadequate for real-world use for a lot of reasons. What's the right way to do recursion on a nested set of collections in Clojure?

Answer 1

What's the right way to do recursion on a nested set of collections in Clojure?

Maybe zip --- https://clojure.github.io/clojure/clojure.zip-api.html

It looks like you might also be interested in hiccup --- https://github.com/weavejester/hiccup

There is also Specter --- https://github.com/redplanetlabs/specter

But, for me, the real answer here is that in practice one rarely needs to 'do recursion on a nested set of collections in Clojure'. Such nested structures are rare, and edits to them (when necessary) can often be accomplished with assoc-in, update-in, or even more rarely some nested reduce called inside a map fn.

Answer 2

Scheme examples nicely translate to Clojure, so your example looks very good. Instead of calling "treemap" recursively, use loop/recur.

However, if you need to iterate a deeply nested structure with some built-in tools, try with clojure.walk [1]. It comes with standard iteration primitives you don't have to write every time.

[1] https://clojuredocs.org/clojure.walk/walk

Comments

loop/recur won't work in a straightforward way on a tree.  If you're constructing a result from recursing down different branches, and use loop/recur, you'll get "Can only recur from tail position" compile-time error.  As OP said, "there are things you can do with recursion that you can't do with a for loop."  Or with loop/recur.  I'm not saying that it's impossible to process a tree without recursion, but it's harder.

---

You should be able `loop/recur` if you keep a stack in your loop onto which you push things that you need to visit later? That's basically what you do with recursion?

Answer 3

with this data:

(def html
'(html (head (title "the fortune cookie institute"))
     (body
      (h1 "Welcome to the Fortune Cookie Institute")
      (p "Our fortunes are guaranteed accurate no matter what.")
      (br)
      (div (p "Like these"))
      (ol
       (li "You will gain weight")
       (li "Taxes will rise")
       (li "Fusion power will always be 50 years away"))
      (br)
      (p "Submit your own fortunes to fortunes@fci.org!"))))

Option 1: using builtin clojure walk:

(require '[clojure.walk :refer [prewalk]])
(prewalk (fn [x] (if (= x 'p) 'h2 x)) html)

Note that the walker continues to walk and would find a 'p in places other than the head of a list (not desired).

Option 2: using specter:

(require  '[com.rpl.specter :refer [ALL FIRST setval recursive-path]] )
(setval [ALL (recursive-path [] RECURSE
            (cond-path
             [sequential? FIRST (pred= 'p)] FIRST
             sequential? [ALL RECURSE]))]
    'h2
    html)

specter here is only looking for 'p at the head of a list (using sequential? rather than list? as your structure is quite close to hiccup which would use vectors. sequential worls for lists and vectors.

option3:

(defn shout [html]
  (if-not (sequential? html)
      html
    (if (= 'p (first html))
      (cons 'h2 (->> (rest html)
                        (map shout)))
      (map shout html))))

This i think truely recurses and consumes stack but the depth of html is not such that it would ever matter. I'm not sure if there is a loop [h html] ... (recur ... answer that is better.