Как создать ленивую-seq генерацию, анонимную рекурсивную функцию в Clojure?
Править: Я обнаружил частичный ответ на свой собственный вопрос в процессе записи этого, но я думаю, что это может легко быть улучшено так, я отправлю его так или иначе. Возможно, там существует лучшее решение?
Я ищу простой способ определить рекурсивные функции в a let форма, не обращаясь к letfn. Это - вероятно, неблагоразумный запрос, но причина, я ищу эту технику, состоит в том, потому что у меня есть соединение данных и рекурсивных функций, которые зависят друг от друга, способом требует большого количества вложенных let и letfn операторы.
Я хотел записать рекурсивные функции, которые генерируют ленивые последовательности как это (использование последовательности Fibonacci как пример):
(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)?
Это было в этой точке, когда я обнаружил ответ на свой собственный вопрос после часа борьбы и инкрементно добавления битов к combinator 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 combinator назвал это, я использую для определения рекурсивной последовательности? Это похоже на Y combinator без аргументов x. Действительно ли это - то же?
(defn Y [r]
((fn [f] (f f))
(fn [y] (r (fn [x] ((y y) x))))))
Есть ли другая функция в clojure.core или clojure.contrib, который обеспечивает функциональность Y или Q? Я не могу вообразить то, что я просто сделал было идиоматично...
2 ответа
letrec
Недавно я написал макрос letrec для Clojure, вот его суть . Он действует как letrec схемы Scheme (если вы это знаете), что означает, что это нечто среднее между 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)))) ).
iterate
Саморекурсивные последовательности часто можно построить с помощью 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 могут быть лучшим способом.
fn принимает необязательный аргумент имени с этим именем, привязанным к функции в ее теле. Используя эту функцию, вы можете написать fibs как:
(def fibs ((fn generator [a b] (lazy-seq (cons a (generator b (+ a b))))) 0 1))