Взаимно рекурсивные определения в Clojure

Как сделать взаимно рекурсивные определения в Clojure?

Вот код на Scala для поиска простых чисел, который использует рекурсивные определения:

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

Я перевел это на 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)

Но запись определений в Clojure REPL одно за другим дает

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

после того, как я напишу (def primes (cons 2 (filter is-prime odds))).

Есть ли способ сделать взаимно рекурсивные определения в Clojure?


recursion clojure definition
person Abhinav Sarkar    schedule 09.07.2010    source источник
comment
термин, описывающий то, что вы пытаетесь сделать, заключается в том, что вы пытаетесь определить пару взаимно рекурсивных функций. Я отредактировал ваш вопрос, чтобы сделать его более понятным.   -  person Ken Bloom    schedule 09.07.2010
comment
@ken: спасибо за исправление терминологии.   -  person Abhinav Sarkar    schedule 09.07.2010

Ответы (2)


arrow_upward
6
arrow_downward

Ответ Грега правильный. Однако вам нужно изменить код: (def odds ...) (declare primes) (defn prime-divisors ...) (defn prime? ...) (def primes ...). Это должно сработать.

Проблема в том, что определение простых чисел не является функцией. Он выполняется немедленно и, следовательно, пытается разыменовать prime? Var, который еще не привязан. Отсюда исключение. Об этом должна позаботиться перестановка.

(Отказ от ответственности: я не проверял, работает ли код с перестановкой.)

И я думаю, что prime? сломан. (prime? 2) должен дать false, нет?

person kotarak    schedule 09.07.2010
comment
Кстати, есть также letfn для определения взаимно рекурсивных функций. - person kotarak; 09.07.2010
comment
2 — простое число. Это только факторы 2 (само себя) и 1. - person Ken Bloom; 09.07.2010
comment
@Ken: я знаю, что два — это простое число. А в приведенном выше prime-divisors: (Math/ceil (Math/sqrt 2)) дает 2. Итак, 2 из primes проходит через take-while и filter. Следовательно, в (is-prime 2) возвращаемое значение prime-divisors не пусто, и возвращается false. Ergo: is-prime сломан. Признаюсь, моя формулировка была немного неясной. - person kotarak; 12.07.2010

arrow_upward
12
arrow_downward

Вам нужно (declare is-prime) перед первой ссылкой на него.

Это называется «предварительной декларацией».

person G__    schedule 09.07.2010
comment
Затем выдается java.lang.IllegalStateException: Var user/is-prime is unbound. (NO_SOURCE_FILE:3) после ввода строки (def primes (...)). - person Abhinav Sarkar; 09.07.2010