Converting To loop ... recur recursion

Question

As I understand it, recursing in Clojure without using the loop .. recur syntax might not be a problem for short sequences. However, using the loop .. recur syntax is the preferred method for writing recursive functions. So, I would like to start with the preferred method.

However, I have been struggling to convert this function [edit] which returns the skeleton of a sequence (the sequence structure without its values)

(defn skl
  [tree]
  (map skl (filter seq? tree)))

tested with this data

(def test_data1 '(1 (2 3) ( ) (( )) :a))
(def test_data2 '(1 2 (3 4) (5 ( 6 7 8))))

to loop .. recur syntax. Any ideas or pointers to examples would be appreciated.

Answer 1

Loop and recur is a transformation of a simple iteration. Descending into a tree is inherently recursive, however. You would have to maintain a stack manually in order to transform it into a single iteration. There is thus no "simple" conversion for your code.

Answer 2

You may want to look into the zipper library which allows for good structured tree editing, though it will likely be less elegant than your origional. I almost never need to use loop ... recur. There is almost always a higher order function that solved the problem more elegantly with the same or better efficiency.

Replacing map with loop ... recur makes code more verbose and less clear. You also lose the benefits of chunked sequences.

Answer 3

Take a look at the clojure.walk source. It's a library to do (bulk) operations on all Clojure nested datastructures (excluding ordered maps). There's some very powerful but deceptively simple looking code in there, using recursion through locally defined anonymous functions without using loop/recur.

Most of the functions in there are based on the postwalk and prewalk functions, which in turn are both based on the walk function. With the source and (prewalk-demo form) and (postwalk-demo form) you can get a good insight into the recursive steps taken.

I don't know if this might help you in solving your problem though. I'm currently trying to do something in the same problem domain: create a function to "flatten" nested maps and vectors into a sequence of all paths from root to leaf, each path a sequence of keys and/or indexes ending in the 'leaf' value.

This library seems to make editing values recursively throughout the whole structure pretty simple. However, I still have no idea how to use it to functionally keep track of accumulated data between iterations that are needed for my 'paths' and probably as well for your 'skeleton' problem.