В продолжение этой темы (a.k.a. «детский сад») и функциональный код vs. императивный. (Другая задачка была тут.)
Вот пусть есть такая простейшая задача - нужно отфильтровать список по предикату на две части и свернуть первую с помощью какой-то функции.
;;;; motivation (dully functional perspective)
;;;;
;;;; (+ a 1 b 2 c 3) => (+ 6 a b c)
;;;;
;;;; wanted
;;;;
;;;; (filter/reduce #'+ 0 #'numberp '(a 1 b 2 c 3))
;;;; => (6 a b c)
;;;;
;;;; with
;;;;
;;;; 1) (n + m) iterations over the LIST (where n is the number of LIST elements
;;;; that satisfy to PREDICATE and m is the number of elements which do not
;;;; satisfy, (n + m) is the length of the LIST of course).
;;;;
;;;; 2) memory allocation only for the new list (with (m + 1) elements),
;;;; without temporary lists.
т.е. нужна более менее общая функция filter/reduce которая фильтрует на две части и сворачивает на одной из них. Но тут ещё поставлено условие: это должно осуществляться в _один_ проход (n + m итераций) и не должно использовать лишнюю память - только аллокация списка-результата.
Отличительная особенность тут в том, что одна списочная функция (reduce) применяется к результату работы другой списочной функции (filter). Понятно, что это приводит к излишним итерациям и аллокации излишней памяти, поэтому есть варианты.
Соответственно, возможные решения:
;;;; assume that compiler don't have the list fusion optimizations
;;;; for all variants:
(declaim (ftype (function (function t function list) (values t list)) filter/reduce))
;;;; I. functional variants
;;;; higher-order functions (expressed in terms of cata/ana/para/hylo)
;;; 1) FILTER/REDUCE as two FILTER and FOLD-LEFT combination.
;;;
;;; this version do (3*n + 2*m) iterations and allocate (2*n + m + 1) elements.
;;;
(defun filter/reduce (function initial-value predicate list)
(values (fold-left function initial-value (filter predicate list))
(filter (compose 'not predicate) list)))
;;; 2) FILTER/REDUCE as PARTITION and FOLD-LEFT combination.
;;;
;;; (2*n + m) iterations in this version and (2*n + m + 1) new elements.
;;;
(defun filter/reduce (function initial-value predicate list)
(multiple-value-bind (allows not-allows)
(partition predicate list)
(values (fold-left function initial-value allows) not-allows)))
;;; 3) FILTER/REDUCE straigh from the folder FOLD-LEFT.
;;;
;;; (n + m) iterations and allocate more than (2*n + m + 1) new elements
;;; because fold-left used accumulators which add quadratic item to the sum.
;;;
(defun filter/reduce (function initial-value predicate list)
(fold-left #'(lambda (rest e)
(if (funcall predicate e)
(cons (funcall function (car rest) e) (cdr rest))
(cons (car rest) (cons e (cdr rest)))))
(list* initial-value nil)
list))
;;;; recursive variant (when you sedulous SICP reader)
;;; 4) FILTER/REDUCE as recursive function (in TCO form).
;;;
;;; (n + m) iterations and allocate (m + 1) new elements + n garbage elements.
;;;
;;; KLUDGE: REST in reverse order.
;;;
(defun filter/reduce (function initial-value predicate list)
(labels ((rec (list reduced rest)
(cond ((endp list)
(values reduced rest))
((funcall predicate (first list))
(rec (rest list)
(funcall function reduced (first list))
rest))
(t
(rec (rest list)
reduced
(cons (first list) rest))))))
(rec list initial-value nil)))
;;;; II. imperative variants
;;;; all variants do (n + m) iterations and allocate (m + 1) new elements
;;;; + n garbage elements.
;;; 5) COLLECT + DOLIST + SETF
(defun filter/reduce (function initial-value predicate list)
(collect ((not-constants))
(dolist (e list)
(if (funcall predicate e)
(setf initial-value (funcall function initial-value e))
(not-constants e)))
(values initial-value (not-constants))))
;;;; 6) LOOP
(defun filter/reduce (function initial-value predicate list)
(loop :for e :in list
:if (funcall predicate e)
:do (setf initial-value (funcall function initial-value e))
:else
:collect e :into not-constants
:end
:finally (return (values initial-value not-constants))))
;;;; 7) ITERATE
(defun filter/reduce (function initial-value predicate list)
(iter (for e in list)
(if (funcall predicate e)
(setf initial-value (funcall function initial-value e))
(collect e into not-constants))
(finally (return (values initial-value not-constants)))))
(CL notes: fold-left это reduce, filter - mapcan, collect это SB-IMPL::COLLECT)
Т.е. можно:
(1) и (2) Писать декларативно, не глядя на производительность.
Учитывая, что filter/reduce может быть представлена как:
- Свёртка
- Рекурсивная функция
- Инструкции некой регистровой машины с последовательным исполнением команд и GOTO.
(т.е. это три таких независимых формализма) можно:
(3) Выражать filter/reduce напрямую через свёртку, что несколько уменьшает понятность и декларативность, но эффективно. Правда, тут есть оверхед на память под аккумуляторы, чего нет в (4) варианте.
(4) Писать filter/reduce как рекурсивную процедуру (если реализация поддерживает TCO - писать в TC форме). В некоторых простых случаях это самый естесвенный способ (в SICP много таких примеров). Но в данном случае это ещё больше уменьшает понятность, но также как и (3) имеет хорошую производительность (если TCO).
(5) Писать императивно, в смысле (c).
(6) и (7) Писать на DSL для обработки последовательностей, который сводится к императивному коду. Тут это LOOP и ITERATE. Это эффективно, не декларативно (отстаёт в понятности от (1)), но довольно легко по коду проследить за логикой и понять что этот код делает.
Ну и последний вариант:
- Использовать реализацию языка с list fusion оптимизациями :)
В целом получается такая картинка:
читаемость
-(4)----(3)----(6?)--(5)--(7)-------------------------(2)-(1)->
4,5,6,7
V
<-*--(3)--------------------------------------------------(1)--
производительность
Т.е. (1) совсем плохо работате, а iterate оказывается компромисом в вопросе производительность/читаемость.
З.Ы.
Сама задачка такая - как заставить (1) работать эквивалентно последним вариантам? :) Почему три последних варианта работают быстро понятно - они легко сводятся к естественному для железа представлению (регистровая машина с jump-ами), про (4) тоже понятно - TCO делает своё дело (сводит к естественному для железа ...). Но что касается (1) - единственная основа которую сюда можно подвести это какие-нибудь алгебраические соображения, на тему того что cata = out . rec . gen и есть соответствующая диаграма отображений; ana, para и hylo имеют подобные соотношения (и некоторый категорный смысл), а все сабжевые функции выражаются через них (и аналогично для других АТД). Например, filter/reduce очень просто выражается через две функции одна из которых свёртка, а другая выражается через свёртку, а также filter/reduce выражается через свёртку непосредственно - должно существовать преобразование из первого во второе. Может уже есть где-нибудь такие оптимизации (list fusion?), или какие-нибудь статьи на тему?
