Tree recursion in Clojure

I’m trying to translate some exercises from The Little Schemer into Clojure for my students and I’m not sure about the idiomatic way to do things. Here’s the function I’ve got. It seems to work. I know this isn’t the way you’re supposed to do it. I’m just trying to introduce them to some basic ideas about recursion.

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

In this case f is just changes

    tags to
    in a representation of an html document.

    (defn transform
              [item]
              (if (= item 'ul)
                'ol
                item))
    

    Here’s the html document:

    (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")
      (ul
       (li "You will gain weight")
       (li "Taxes will rise")
       (li "Fusion power will always be 50 years away"))
      (p "Submit your own fortunes to fortunes@fci.org!")))
    

    My question is this. I know this is inadequate for a number of reasons. What’s the right way to write a recursive function on a nested set of collections in Clojure?

2 Likes

If you want to cheat, you can look at the source for clojure.walk/prewalk and clojure.walk/postwalk :slight_smile:

I think what you’ve written is perfectly fine. In contrast to Scheme, clojure lacks automatic tail call optimization. So your implementation might blow the stack for big trees. To avoid that, look into recur.

You also might want to work with sequences, not lists. That way, you can support vectors.

Edit: looks like clojure.walk simply uses map and reduce.

I would just do something like this:

(defn treemap [f t]
  (if (sequential? t)
    (map (partial treemap f) t)
    (f t)))