Я подведу итог своей истории решения этой проблемы, используя старую для создания примеров прогонов, и завершу некоторыми наблюдениями и предложениями по расширению.
решение 0
В Во-первых, я уточнил / обобщил подход, который я использовал для решения старой проблемы. Здесь я пишу свои собственные версии concat и map в основном для лучшей презентации и, в случае concat, для некоторой дополнительной лени. Конечно, мы можем использовать версии Clojure или mapcat.
(defn fproduct [f]
(fn [s]
(lazy-seq
(if (and (seq f) (seq s))
(cons
((first f) (first s))
((fproduct (rest f)) (rest s)))))))
(defn concat' [s]
(lazy-seq
(if (seq s)
(if-let [x (seq (first s))]
(cons (first x) (concat' (cons (rest x) (rest s))))
(concat' (rest s))))))
(defn map' [f]
(fn rec [s]
(lazy-seq
(if (seq s)
(cons (f (first s)) (rec (rest s)))))))
(defn nunfoldr [f e]
(fn rec [n]
(fn [x]
(if (zero? n)
(if (= e x) (list ()) ())
((comp
concat'
(map' (comp
(partial apply map)
(fproduct (list
(partial partial cons)
(rec (dec n))))))
f)
x)))))
В попытке получить внутреннюю лень мы могли бы заменить (partial partial cons) чем-то вроде (comp (partial partial concat) list). Хотя таким образом мы получаем внутренние LazySeq s, мы не получаем никакой эффективной лени, потому что перед cons ing выполняется большая часть вычислений, необходимых для полной реализации части rest, что кажется неизбежным в рамках этого общего подхода. , На основе более длинной версии nfoldr мы также можем определить следующую более быструю версию.
(defn nunfoldr [f e]
(fn [n]
(fn [x]
(if (zero? n)
(if (= e x) (list ()) ())
(((fn rec [n]
(fn [x] (println \< x \>)
(if (= 1 n)
(list (list x))
((comp
concat'
(map' (comp
(partial apply map)
(fproduct (list
(partial partial cons)
(rec (dec n))))))
f)
x))))
n)
x)))))
Здесь я добавил вызов println внутри главной рекурсивной функции, чтобы получить некоторую визуализацию рвения. Итак, давайте продемонстрируем внешнюю лень и внутреннее рвение.
user=> (first ((npt 5) (range 3)))
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
(() () () () (0 1 2))
user=> (ffirst ((npt 5) (range 3)))
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
< (0 1 2) >
()
решение 1
Затем я подумал о более многообещающем подходе, используя функцию:
(defn transpose [s]
(lazy-seq
(if (every? seq s)
(cons
(map first s)
(transpose (map rest s))))))
Чтобы получить новое решение, мы заменяем предыдущий аргумент в вызове map' на:
(comp
(partial map (partial apply cons))
transpose
(fproduct (list
repeat
(rec (dec n)))))
Пытаясь получить внутреннюю лень, мы можем заменить (partial apply cons) на #(cons (first %) (lazy-seq (second %))), но этого недостаточно , Проблема заключается в тесте (every? seq s) внутри transpose, где проверка ленивой последовательности факторизаций на пустоту (как условие остановки) приводит к ее реализации.
решение 2
Первым способом решения предыдущей проблемы, которая пришла мне в голову, было использование некоторых дополнительных знаний о количестве n -арных факторизаций элемента. Таким образом, мы можем repeat определенное количество раз и использовать только эту последовательность для условия остановки transpose. Таким образом, мы заменим тест внутри transpose на (seq (first s)), добавим ввод count в nunfoldr и заменим аргумент в вызове map' на:
(comp
(partial map #(cons (first %) (lazy-seq (second %))))
transpose
(fproduct (list
(partial apply repeat)
(rec (dec n))))
(fn [[x y]] (list (list ((count (dec n)) y) x) y)))
Давайте обратимся к Задача разбиения и определения:
(defn npt-count [n]
(comp
(partial apply *)
#(map % (range 1 n))
(partial comp inc)
(partial partial /)
count))
(def npt (nunfoldr pt2 () npt-count))
Теперь мы можем продемонстрировать внешнюю и внутреннюю лень.
user=> (first ((npt 5) (range 3)))
< (0 1 2) >
(< (0 1 2) >
() < (0 1 2) >
() < (0 1 2) >
() < (0 1 2) >
() (0 1 2))
user=> (ffirst ((npt 5) (range 3)))
< (0 1 2) >
()
Однако зависимость от дополнительных знаний и дополнительных вычислительных затрат делает это решение неприемлемым .
решение 3
Наконец, я подумал, что в некоторых критических местах я должен использовать своего рода ленивые последовательности «с не ленивым концом», чтобы иметь возможность проверить на пустоту, не осознавая. Пустая такая последовательность - это просто ленивый пустой список, и в целом они ведут себя примерно как 1067 * ранних дней Clojure. Используя определения, приведенные ниже, мы можем достичь приемлемого решения, которое работает в предположении, что всегда хотя бы одна из concat' ed последовательностей (когда она есть) непуста, что особенно важно, когда каждый элемент имеет хотя бы одну двоичную факторизацию, и мы используем более длинную версию nunfoldr.
(def lazy? (partial instance? clojure.lang.IPending))
(defn empty-eager? [x] (and (not (lazy? x)) (empty? x)))
(defn transpose [s]
(lazy-seq
(if-not (some empty-eager? s)
(cons
(map first s)
(transpose (map rest s))))))
(defn concat' [s]
(if-not (empty-eager? s)
(lazy-seq
(if-let [x (seq (first s))]
(cons (first x) (concat' (cons (rest x) (rest s))))
(concat' (rest s))))
()))
(defn map' [f]
(fn rec [s]
(if-not (empty-eager? s)
(lazy-seq (cons (f (first s)) (rec (rest s))))
())))
. Обратите внимание, что при таком подходе функция ввода f должна создавать ленивые последовательности нового вида, и в результате n -ary-факторизатор также будет производить такие последовательности. Чтобы позаботиться о новом входном требовании, для проблемы разделов мы определяем:
(defn pt2 [s]
(lazy-seq
(let [start (list () s)]
(cons
start
((fn rec [[x y]]
(if (seq y)
(lazy-seq
(let [step (list (concat x (list (first y))) (rest y))]
(cons step (rec step))))
()))
start)))))
Еще раз, давайте продемонстрируем внешнюю и внутреннюю лень.
user=> (first ((npt 5) (range 3)))
< (0 1 2) >
< (0 1 2) >
(< (0 1 2) >
() < (0 1 2) >
() < (0 1 2) >
() () (0 1 2))
user=> (ffirst ((npt 5) (range 3)))
< (0 1 2) >
< (0 1 2) >
()
Чтобы сделать ввод и выводить используя стандартные ленивые последовательности (жертвуя немного лени), мы можем добавить:
(defn lazy-end->eager-end [s]
(if (seq s)
(lazy-seq (cons (first s) (lazy-end->eager-end (rest s))))
()))
(defn eager-end->lazy-end [s]
(lazy-seq
(if-not (empty-eager? s)
(cons (first s) (eager-end->lazy-end (rest s))))))
(def nunfoldr
(comp
(partial comp (partial comp eager-end->lazy-end))
(partial apply nunfoldr)
(fproduct (list
(partial comp lazy-end->eager-end)
identity))
list))
наблюдения и расширения
При создании решения 3 я заметил, что старый механизм поскольку ленивые последовательности в Clojure не обязательно должны уступать текущей. С переходом мы получили возможность создавать ленивые последовательности без каких-либо существенных вычислений, но потеряли способность проверять пустоту без выполнения вычислений, необходимых для получения еще одного элемента. Поскольку обе эти способности могут быть важны в некоторых случаях, было бы неплохо, если бы был введен новый механизм, который бы сочетал в себе преимущества предыдущих. Такой механизм может снова использовать внешний LazySeq thunk, который при принудительном возвращении пустой список или Cons или другой LazySeq или новый LazyCons thunk. Этот новый толчок при принудительном возвращении Cons или, возможно, другой LazyCons. Теперь empty? вызовет только LazySeq thunks, в то время как first и rest также вызовут LazyCons. В этой настройке map может выглядеть так:
(defn map [f s]
(lazy-seq
(if (empty? s) ()
(lazy-cons
(cons (f (first s)) (map f (rest s)))))))
Я также заметил, что подход, взятый из решения 1 и далее, поддается дальнейшему обобщению. Если внутри аргумента в вызове map' в более длинном nunfoldr мы заменим cons на concat, transpose с некоторой реализацией декартового произведения и repeat с другим рекурсивным вызовом, мы можем затем создать версии, которые "раскол в разных местах". Например, используя следующее в качестве аргумента, мы можем определить функцию nunfoldm, которая «разбивается посередине» и соответствует легко представляемому nfoldm. Обратите внимание, что все «стратегии расщепления» эквивалентны, когда f является ассоциативным.
(comp
(partial map (partial apply concat))
cproduct
(fproduct (let [n-half (quot n 2)]
(list (rec n-half) (rec (- n n-half))))))
Другая естественная модификация допускает бесконечные факторизации. Чтобы достичь этого, если f генерирует бесконечные факторизации, nunfoldr(f , e)(n) должен генерировать факторизации в порядке типа ω, чтобы каждая из них могла быть произведена за конечное время.
Другие возможные расширения включают отбрасывание параметр n, создающий реляционные сгибы (в соответствии с рассматриваемыми здесь реляционными развёртываниями) и обрабатывающий алгебраические структуры данных c, отличные от последовательностей, как ввод / вывод. Эта книга , которую я только что обнаружил, кажется, содержит ценную релевантную информацию, представленную на категориальном / реляционном языке.
Наконец, чтобы сделать этот вид программирования более удобным, мы могли бы перевести его в бессчетную настройку алгебры c. Это потребовало бы создания значительной «дополнительной машины», фактически фактически создавая новый язык. Эта статья демонстрирует такой язык.