Как создать в Clojure генерирующую lazy-seq анонимную рекурсивную функцию?

Question

Редактировать : Я нашел частичный ответ на свой вопрос в процессе написания этого, но я думаю, что его можно легко улучшить, поэтому я все равно опубликую его.Может быть, есть лучшее решение?

Я ищу простой способ определения рекурсивных функций в форме let, не прибегая к letfn.Это, вероятно, необоснованный запрос, но причина, по которой я ищу эту технику, заключается в том, что у меня есть набор данных и рекурсивных функций, которые в некоторой степени зависят друг от друга и требуют большого количества вложенных операторов let и letfn.

Я хотел написать рекурсивные функции, которые генерируют ленивые последовательности, подобные этой (на примере последовательности Фибоначчи):

(let [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  (take 10 fibs))

Но в ближайшем будущем кажется, что fibs не может использовать егособственный символ во время связывания.Очевидный способ обойти это использование letfn

(letfn [(fibo [] (lazy-cat [0 1] (map + (fibo) (rest (fibo)))))]
  (take 10 (fibo)))

Но, как я уже говорил ранее, это приводит к громоздкому вложению и чередованию let и letfn.

Чтобы сделать это без letfn и просто let, я начал с написания чего-то, что использует, как мне кажется, U-комбинатор (только что слышал о концепции сегодня):

(let [fibs (fn [fi] (lazy-cat [0 1] (map + (fi fi) (rest (fi fi)))))]
  (take 10 (fibs fibs)))

Но как избавиться от избыточности (fi fi)?

Именно в этот момент я обнаружил ответ на свой вопрос после часа борьбы и постепенного добавления битов в комбинатор Q.

(let [Q (fn [r] ((fn [f] (f f)) (fn [y] (r (fn [] (y y))))))
      fibs (Q (fn [fi] (lazy-cat [0 1] (map + (fi) (rest (fi))))))]
  (take 10 fibs))

Что это за комбинатор Qназывается, что я использую, чтобы определить рекурсивную последовательность?Похоже, Y комбинатор без аргументов x.Это то же самое?

(defn Y [r] 
  ((fn [f] (f f)) 
   (fn [y] (r (fn [x] ((y y) x))))))

Есть ли другая функция в clojure.core или clojure.contrib, которая обеспечивает функциональность Y или Q?Я не могу представить, что я только что сделал идиоматическим ...

Answer 1

letrec

Недавно я написал макрос letrec для Clojure, вот Суть этого . Он действует как схема letrec (если вам это известно), это означает, что это нечто среднее между let и letfn: вы можете связать набор имен с взаимно рекурсивными значениями, без необходимости того, чтобы эти значения были функции (ленивые последовательности тоже подойдут), до тех пор, пока можно оценить заголовок каждого элемента, не обращаясь к другим (это язык Хаскелла - или, возможно, теоретико-типовый - на языке; здесь «голова» может означать, например сам ленивый объект последовательности, с - критически важно! - без принуждения).

Вы можете использовать его для написания таких вещей, как

(letrec [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  fibs)

, что обычно возможно только на верхнем уровне. См. Gist для большего количества примеров.

Как указано в тексте вопроса, вышеприведенное можно заменить на

(letfn [(fibs [] (lazy-cat [0 1] (map + (fibs) (rest (fibs)))))]
  (fibs))

для того же результата в экспоненциальном времени ; версия letrec имеет линейную сложность (как и форма (def fibs (lazy-cat [0 1] (map + fibs (rest fibs)))) верхнего уровня).

итерация

Саморекурсивные последовательности часто можно создать с помощью iterate, а именно, когда для вычисления любого заданного элемента достаточно фиксированного диапазона просмотра. См. clojure.contrib.lazy-seqs для примера того, как вычислить fibs с iterate.

clojure.contrib.seq

c.c.seq предоставляет интересную функцию под названием rec-seq, которая включает такие вещи, как

(take 10 (cseq/rec-seq fibs (map + fibs (rest fibs))))

Он имеет ограничение, позволяющее создавать только одну саморекурсивную последовательность, но может быть возможным вывести из его источника некоторые идеи реализации, позволяющие создавать более разнообразные сценарии. Если вам нужна отдельная саморекурсивная последовательность, не определенная на верхнем уровне, это должно быть идиоматическое решение.

комбинаторы

Что касается комбинаторов, подобных отображаемым в тексте вопроса, важно отметить, что им мешает отсутствие TCO (оптимизация хвостового вызова) на JVM (и, следовательно, в Clojure, который выбирает использовать вызов JVM соглашения непосредственно для максимальной производительности).

верхний уровень

Существует также возможность размещения взаимно рекурсивных «вещей» на верхнем уровне, возможно, в их собственном пространстве имен. Это не очень хорошо работает, если эти «вещи» нужно как-то параметризировать, но пространства имен можно создавать динамически, если это необходимо (см. clojure.contrib.with-ns для идей реализации).

последние комментарии

Я с готовностью признаю, что вещь letrec далека от идиоматического Clojure, и я бы избегал использовать ее в производственном коде, если бы что-нибудь еще подействовало (и поскольку всегда есть опция верхнего уровня ...). Тем не менее, это (IMO!) Приятно играть, и, кажется, работает достаточно хорошо. Мне лично интересно узнать, сколько можно достичь без letrec и в какой степени макрос letrec делает вещи проще / чище ... У меня пока нет мнения по этому поводу. Итак, вот оно. Еще раз, для одиночного саморекурсивного случая seq, iterate или contrib могут быть наилучшим способом.

Answer 2

fn принимает необязательный аргумент имени, имя которого связано с функцией в его теле.Используя эту функцию, вы можете написать fibs как:

(def fibs ((fn generator [a b] (lazy-seq (cons a (generator b (+ a b))))) 0 1))