Как создать анонимную рекурсивную функцию, генерирующую ленивую последовательность, в 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-комбинатором (только сегодня услышал об этой концепции):

(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? Я не могу представить, что то, что я только что сделал, было идиоматичным...


binding recursion clojure combinators lazy-sequences
person ivar    schedule 30.07.2010    source источник
comment
Я заметил, что запись выдумок таким образом приводит к ужасной производительности, потому что (я полагаю) комбинатор не сохраняет результаты под символами выдумок, а перегенерирует значения на лету? Как я могу сделать это более производительным?   -  person ivar    schedule 30.07.2010

Ответы (2)


arrow_upward
11
arrow_downward

летрек

Недавно я написал макрос 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, а именно, когда фиксированного диапазона ретроспективного просмотра достаточно для вычисления любого заданного элемента. См. 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 упрощает/чище... Я еще не сформировал мнение на этот счет. Итак, вот оно. Еще раз, для случая одиночной саморекурсивной последовательности iterate или contrib могут быть лучшим способом.

person Michał Marczyk    schedule 30.07.2010
comment
Спасибо за отличный ответ! Я знаю об итерации, но ее трудно использовать в моей конкретной задаче (поскольку реальная структура проблемы использует данные из нескольких деревьев неправильной формы, а не простой Фибоначчи). Я обязательно изучу этот макрос и rec-seq! - person ivar; 31.07.2010
comment
Почему letrec далеко от идиоматического? Он просто делает для defs то же, что letfn делает для defns: обеспечивает самостоятельную и взаимную ссылку на локальном уровне. Если бы мы были готовы отказаться от повторной привязки - обычно (loop [v v]) - let могли бы работать таким образом. Нет? - person Thumbnail; 15.05.2014
comment
Это не идиоматично, потому что это не то, с чем вы столкнетесь в коде Clojure в дикой природе, несмотря на мою реализацию четырехлетней давности. Это не особенно удивительно — во-первых, способ работы макроса отличается от того, как работала бы встроенная реализация, поэтому он несколько чужд языку; и тогда это не то, что нужно так часто. Это не умаление полезности letrec, а просто констатация факта о методах кодирования Clojure. - person Michał Marczyk; 25.05.2014
comment
В качестве примечания: здесь суть более новой версии, которую я написал давным-давно. , но так и не удосужились нигде опубликовать. Это позволяет избежать необходимости делать собственный код, используя symbol-macrolet tools.macro, поэтому мне было бы удобнее его использовать. - person Michał Marczyk; 25.05.2014

arrow_upward
8
arrow_downward

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

(def fibs ((fn generator [a b] (lazy-seq (cons a (generator b (+ a b))))) 0 1))
person Brian    schedule 01.08.2010
comment
Хорошо поймал! Я забыл об этом. - person ivar; 02.08.2010