How to return the output of a recursive function in Clojure

Question

Hi everyone! I'm new to functional languages and clojure, so please bear with me...

I'm trying to construct a list of functions, with either random parameters or constants. The function that constructs the list of functions is already working, though it doesn't return the function itself. I verified this using println.

(edit: Okay, it isn't working correctly yet after all)

(edit: Now it's working, but it cannot be "eval"-ed. it seems I need to recur at least two times, to ensure there are at least two children nodes. Is this possible?)

Here is the snippet:

(def operations (list #(- %1 %2) #(+ %1 %2) #(* %1 %2) #(/ %1 %2)))
(def parameters (list \u \v \w \x \y \z))
(def parameterlistcount 6)
(def paramcount 2)
(def opcount 4)

(defn generate-function

([] (generate-function 2 4 0.5 0.6 () parameters)) ([pc maxdepth fp pp function-list params] (if (and (pos? maxdepth) (< (rand) fp)) (let [function-list (conj function-list (nth operations (rand-int (count operations))))] (recur pc (dec maxdepth) fp pp function-list params)) (if (and (< (rand) pp) (pos? pc)) (let [ params (pop parameters) function-list (conj function-list (nth params (rand-int (count params))))] (if (contains? (set operations) (last function-list) ) (recur (dec pc) maxdepth fp pp function-list params) nil)) (let [function-list (conj function-list (rand-int 100))] (if (or (pos? maxdepth) (pos? pc)) (if (contains? (set operations) (last function-list) ) (recur pc maxdepth fp pp function-list params) nil) function-list))))))

Any help will be appreciated, thanks!

Answer 1

In general it is a better idea in Clojure to use (recur ...) for your recursive functions. From the docs: "Note that recur is the only non-stack-consuming looping construct in Clojure." link

One other thing to note is that you might want to call the randomizer outside the recursive function, so you can define the stop-condition inside the function.

So like this:

(let [n (rand-int 10)] 
  (println "Let's define f with n =" n)
  (defn f [x] 
    (if (> x n) 
      "result" 
      (do (println x) 
          (recur (inc x))))))

It prints:

Let's define f with n = 4

user> (f 0)
0
1
2
3
4
"result"

where 4 is of course a random number between 0 (inclusive) and 10 (exclusive).

Answer 2

Here's my shot at rewriting your function (see comments below):

(defn generate-function
  ([] (generate-function 2 4 0.5 0.6 ()))
  ([pc maxdepth fp pp function-list]
     (if (and (pos? maxdepth) (< (rand) fp))
       (let [function-list
             (conj function-list
                   {:op
                    (nth operations
                         (rand-int (count operations)))})]
         (recur pc (dec maxdepth) fp pp function-list))
       (if (and (< (rand) pp) (pos? pc))
         (let [function-list
               (conj function-list
                     {:param
                      (nth parameters
                           (rand-int (count parameters)))})]
           (recur (dec pc) maxdepth fp pp function-list))
         (let [function-list
               (conj function-list
                     {:const
                      (rand-int 100)})]
           (if (or (pos? maxdepth) (pos? pc))
             (recur pc maxdepth fp pp function-list)
             function-list))))))

And some examples of use from my REPL...

user> (generate-function)
({:const 63} {:op #<user$fn__4557 user$fn__4557@6cbb2d>} {:const 77} {:param \w} {:op #<user$fn__4559 user$fn__4559@8e68bd>} {:const 3} {:param \v} {:const 1} {:const 8} {:op #<user$fn__4559 user$fn__4559@8e68bd>} {:op #<user$fn__4555 user$fn__4555@6f0962>})
user> (generate-function)
({:const 27} {:param \y} {:param \v} {:op #<user$fn__4561 user$fn__4561@10463c3>} {:op #<user$fn__4561 user$fn__4561@10463c3>} {:op #<user$fn__4561 user$fn__4561@10463c3>} {:op #<user$fn__4561 user$fn__4561@10463c3>} {:const 61})

A couple of things to keep in mind, in pretty random order:

1. I used recur in the above to avoid consuming stack in the recursive self-calls. However, you have this dotimes statement which makes me wonder if you might be interested in constructing a bunch of function-lists in parallel with one generate-function call. If so, tail-recursion with recur might not be an option with simplistic code like this, so you could either settle for the regular self-calls (but do consider the possibility of hitting the recursion limit; if you're positive that you'll only generate smallish functions and this won't be a problem, go ahead with the self-calls) or investigate continuation-passing style and rewrite your function in that style.

2. The (do (dec pc) ...) thing in your code does nothing to the value of pc in the next recursive call, or indeed to its current value. Local variables (or locals, as they are most often called in the community) in Clojure are immutable; this includes function parameters. If you want to pass along a decremented pc to some function, you'll have to do just that, like you did with maxdepth in an earlier branch of your code.

3. I renamed your function to generate-function, because camel case in function names is quite unusual in Clojure land. Also, I renamed the parameter which you called function to function-list (so maybe I should have used a name like generate-function-list for the function... hm), because that's what it is for now.

4. Note that there's no point to keeping a separate opcount Var around; Clojure's persistent lists (as created by the list function) carry their count around, so (count some-list) is a constant-time operation (and very fast). Also, it would be idiomatic to use vectors for operations and parameters (and you can switch to vectors without changing anything in the rest of the code!). E.g. [\u \v \w \x \y \z].

5. In Clojure 1.2, you'll be able to use (rand-nth coll) for (nth coll (rand-int (count coll))).

6. If you want to generate actual Clojure functions from trees of items representing ops, params and constants, you'll want to use eval. That's discouraged in most scenarios, but not for evolutionary programming and similar stuff where it's the only way to go.

7. Personally, I'd use a different format of the op/param/constant maps: something like {:category foo, :content bar} where foo is :op, :param or :const and bar is something appropriate in connection to any given foo.

Answer 3

So okay, I discovered I was going about this the wrong way. A recursive definition of a tree is non other than defining vertices, and trying to tie everything with it. So, I came up with this, in less than 15 minutes. >_<

(defn generate-branch
"Generate branches for tree"
  ([] (generate-branch 0.6 () (list \x \y \z)))
  ([pp branch params]
      (loop [branch
        (conj branch (nth operations (rand-int (count operations))))]
    (if (= (count branch) 3)
      branch
      (if (and (< (rand) pp))
        (recur (conj branch (nth params (rand-int (count params)))))
        (recur (conj branch (rand-int 100))))))))

(defn build-vertex
"Generates a vertex from branches"
  []
  (let [vertex (list (nth operations (rand-int (count operations))))]
    (conj vertex (take 5 (repeatedly generate-branch)))))

THANKS EVERYONE!