Mutually recursive definitions in Clojure

Question

How do I do mutually recursive definitions in Clojure?

Here is a code in Scala to find prime numbers which uses recursive definitions:

val odds: Stream[Int] = cons(3, odds map { _ + 2 })
val primes: Stream[Int] = cons(2, odds filter isPrime)
def primeDivisors(n: Int) =
    primes takeWhile { _ <= Math.ceil(Math.sqrt(n))} filter { n % _ == 0 }
def isPrime(n: Int) = primeDivisors(n) isEmpty

primes take 10

I translated this to Clojure:

(def odds (iterate #(+ % 2) 3))
(def primes (cons 2 (filter is-prime odds)))
(defn prime-divisors [n]
    (filter #(zero? (mod n %)) 
        (take-while #(<= % (Math/ceil (Math/sqrt n))) 
            primes)))
(defn is-prime [n] (empty? (prime-divisors n)))

(take 10 primes)

But writing the definitions in the Clojure REPL one by one gives

java.lang.Exception: Unable to resolve symbol: is-prime in this context (NO_SOURCE_FILE:8)

after I write (def primes (cons 2 (filter is-prime odds))).

Is there a way to do mutually recursive definitions in Clojure?

the term that describes what you're trying to do is that you're trying to define a pair of mutually recursive functions. I've edited your question to make that more clear. — Ken Bloom
– Ken Bloom, Commented Jul 9, 2010 at 14:23

G__ · Accepted Answer · 2010-07-09 14:20:50Z

16

You need to (declare is-prime) before the first time you reference it.

This is referred to as a "forward declaration".

answered Jul 9, 2010 at 14:20

G__

7,1215 gold badges38 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Abhinav Sarkar Over a year ago

Then java.lang.IllegalStateException: Var user/is-prime is unbound. (NO_SOURCE_FILE:3) is thrown after typing (def primes (...)) line.

kotarak · Accepted Answer · 2010-07-09 14:39:16Z

7

Greg's answer is correct. However you have to rearrange your code: (def odds ...) (declare primes) (defn prime-divisors ...) (defn prime? ...) (def primes ...). This should do the trick.

The problem is, that the definition of primes is not a function. It is executed immediately and hence tries to dereference the prime? Var which is not bound, yet. Hence the exception. Re-arranging should take care of that.

(Disclaimer: I haven't checked that the code works with the re-arrangement.)

And I think prime? is broken. (prime? 2) should give false, no?

answered Jul 9, 2010 at 14:39

kotarak

17.3k2 gold badges53 silver badges41 bronze badges

3 Comments

kotarak Over a year ago

BTW, there is also letfn to define mutually recursive functions.

Ken Bloom Over a year ago

2 is a prime number. It's only factors are 2 (itself) and 1.

kotarak Over a year ago

@Ken: I know that two is a prime number. And in the above prime-divisors: (Math/ceil (Math/sqrt 2)) gives 2. So the 2 from primes passes through the take-while and the filter. Hence in (is-prime 2) the return value of prime-divisors is not empty and false is returned. Ergo: is-prime is broken. I admit, that my formulation was a little unclear.

Collectives™ on Stack Overflow

Mutually recursive definitions in Clojure

2 Answers 2

1 Comment

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related