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

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

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

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

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

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

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

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

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

(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 combinator без аргументов x. Это то же самое?

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

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

Ответ 1

letrec

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

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

(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))))).

итерация

Саморекурсивные seqs часто могут быть построены с помощью iterate, а именно, когда для вычисления любого заданного элемента достаточно фиксированного диапазона look-behind. См. 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 может быть лучшим способом.