LINUX.ORG.RU

[common lisp][ищу морфизм] ещё одна годная задачка про списки


0

1

В продолжение этой темы (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 может быть представлена как:

  1. Свёртка

  2. Рекурсивная функция

  3. Инструкции некой регистровой машины с последовательным исполнением команд и 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?), или какие-нибудь статьи на тему?

Именно для SBCL результаты такие:

;;;; tested with
;;;;
;;;;   (defun gen (n)
;;;;    (when (> n 0)
;;;;      (if (= 1 (random 2))
;;;;          (cons (random 100) (gen (1- n)))
;;;;          (cons (gensym)     (gen (1- n))))))
;;;;
;;;;   (defparameter *gen* (gen 10000))
;;;;
;;;;   (time (dotimes (_ 10) (filter/reduce #'+ 0 #'numberp *gen*)))

1)
Evaluation took:
  0.096 seconds of real time
  0.078988 seconds of total run time (0.078988 user, 0.000000 system)
  82.29% CPU
  242,867,671 processor cycles
  1,605,560 bytes consed

2)
Evaluation took:
  0.098 seconds of real time
  0.078988 seconds of total run time (0.078988 user, 0.000000 system)
  80.61% CPU
  250,301,924 processor cycles
  1 page fault
  1,597,368 bytes consed

3)
Evaluation took:
  0.032 seconds of real time
  0.018997 seconds of total run time (0.018997 user, 0.000000 system)
  59.38% CPU
  83,299,562 processor cycles
  2,002,160 bytes consed

4)
Evaluation took:
  0.034 seconds of real time
  0.016997 seconds of total run time (0.016997 user, 0.000000 system)
  50.00% CPU
  85,306,191 processor cycles
  1,195,208 bytes consed

5)
Evaluation took:
  0.034 seconds of real time
  0.016997 seconds of total run time (0.016997 user, 0.000000 system)
  50.00% CPU
  86,590,876 processor cycles
  1,199,312 bytes consed

6)
Evaluation took:
  0.030 seconds of real time
  0.016997 seconds of total run time (0.013998 user, 0.002999 system)
  56.67% CPU
  76,051,671 processor cycles
  1,199,392 bytes consed

7)
Evaluation took:
  0.028 seconds of real time
  0.016997 seconds of total run time (0.016997 user, 0.000000 system)
  60.71% CPU
  71,036,763 processor cycles
  1,195,216 bytes consed

----
  801,256 bytes consed is aproximated ideal (n+m new elements, no garbage)
----
quasimoto ★★★★ ()

Как я завидую твоему количеству свободного времени.

paranonymous ()

>Сама задачка такая - как заставить (1) работать эквивалентно последним вариантам? :)

Написать соответствующий compiler-macro

dmitry_vk ★★★ ()

*нудит: ну во первых это не filter, а partition

arhibot ()

А вообще, лучше, конечно, писать кошерный язык для обработки последовательностей.

В CL некоторые предполагали включить пакет series, операции над последовательностями в котором «may be composed functionally and yet execute iteratively, without the need to construct intermediate series values».

dmitry_vk ★★★ ()
Ответ на: комментарий от dmitry_vk

В CL некоторые предполагали включить пакет series, операции над последовательностями в котором «may be composed functionally and yet execute iteratively, without the need to construct intermediate series values».

Я как-то смотрел на этот series. Имхо, правильно сделали, что выбросили из стандарта. Но сама идея отквотированных английских букв - это да, хорошо.

mv ★★★★★ ()
Ответ на: комментарий от arhibot

Я тоже думал сюда написать что-нибудь а-ля reduce f a p = (\(xs, ys) -> foldl f a xs : ys) . partition p; но потом передумал, шутку не поймут ведь.

balodja ★★★ ()

«Как перестать компилировать и начать жить»...

yoghurt ★★★★★ ()
Ответ на: комментарий от paranonymous

> Как я завидую твоему количеству свободного времени.

Время от времени такие вещи надо делать, чтобы знать, что на что размениваешь при выборе способа реализации алгоритма. Но не так подробно, конечно.

balodja ★★★ ()
Ответ на: комментарий от dmitry_vk

Написать соответствующий compiler-macro

Это правильно, но количество возможных комбинаций списочных функций столь велико, что все их не предусмотреть - в SBCL есть достаточно много подобных оптимизаций, но они не покрывают всех возможных вариантов. Поэтому я подумал о возможности автоматического преобразования, скажем, двойных применений в однопроходный алгоритм. Или более сложных комбинаций (если это возможно), исходя их значения некоторого параметра (как с трансляцией nthcar в последовательность c.r при n < некоторого значения (последовательность инструкций получается) и вызов nthcar при большем n (просто вызов функции)).

quasimoto ★★★★ ()
Ответ на: комментарий от arhibot

ну во первых это не filter, а partition

partition там во (2) варианте, а filter/reduce называется потому что в итоге получается reduced-value (одна часть partition) и оставшийся список (другая), т.е. это фильтр + дополнительное значение от свёртки - обычный фильтр отбрасывает одну часть, partition возвращает обе, а filter/reduce возвращает одну часть и значение свёрнутое из второй.

quasimoto ★★★★ ()
Ответ на: комментарий от balodja

reduce f a p = (\(xs, ys) -> foldl f a xs : ys) . partition p;

Это ровным счётом второй вариант (с поправкой на point-free). Вопрос в том подвергает ли GHC этот код list fusion оптимизациям (или как они называются, я пока не изучал это подробно). И если да, то хотелось бы знать как (article?) и в какой файл в исходном коде смотреть.

Что-то мне подсказывает что это есть в «Comprehending Queries», но там преобразования для языка запросов к БД, а не для списков (разные АТД, короче).

quasimoto ★★★★ ()
Ответ на: комментарий от Love5an

Иди лучше напиши что-то подобное

Зачем? Ты ведь уже написал :)

Я не понимаю, нахрена эта херня нужна.

Скажем так, это одна из возможных оптимизаций, которую может делать компилятор. Наряду с TCO можно её поставить. Конечно, херня не нужна, но всё же лучше с TCO чем без - «чтобы не зависало», если говорить по-просту. Желание писать всегда простейший логически код вполне естественное, но без оптимизаций он получается хуже в цифрах (время/память) что можно видеть выше ((1) и последние варианты).

Тебе делать нечего?

Я бы не сказал, что это занимает много времени.

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

> Это ровным счётом второй вариант (с поправкой на point-free).

Нет. Это не второй вариант, и никогда им не будет. Самый близкий аналог среди предложенных тобой — это 3ий, но я не уверен, ибо не знаю, как работает 7ой с iterate.

balodja ★★★ ()
Ответ на: комментарий от quasimoto

> Вопрос в том подвергает ли GHC этот код list fusion оптимизациям (или как они называются, я пока не изучал это подробно).

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

balodja ★★★ ()
Ответ на: комментарий от balodja

Хотя, вру, третий тоже не подходит. Пятый вариант с collect похож больше на правду.

balodja ★★★ ()
Ответ на: комментарий от balodja

Да и пятый тоже не подходит. Короче, нет аналога.

balodja ★★★ ()
Ответ на: комментарий от quasimoto

>Зачем? Ты ведь уже написал :)
Я имею ввиду, почему бы не потратить силы на что-нибудь перспективное и действительно полезное сообществу CL?

Никто из лисперов в здравом уме не программирует в терминах морфизмов, монад и сверток. И хвостовой рекурсией мало кто из них пользуется(т.к. loop/iterate есть). А в нормальных проектах вообще от таких деталей абстрагируются и полагаются на CLOS(в т.ч. метаобъектный протокол) и/или кодогенерацию макросами.

Love5an ()
Ответ на: комментарий от balodja

Это не второй вариант, и никогда им не будет.

Я говорю о логике работы. Можно записать это один в один:

;;; Note: using `multiple-value-compose' from `alexandria'

(defun filter/reduce-closure (function initial-value predicate)
  ;; (.)
  (multiple-value-compose
   ;; (\(xs, ys) -> foldl f a xs : ys)
   #'(lambda (xs ys) (cons (fold-left function initial-value xs) ys))
   ;; partition p
   #'(lambda (list) (partition predicate list))))

(defun filter/reduce (function initial-value predicate list)
  (funcall (filter/reduce-closure function initial-value predicate) list))

Но работать это будет ровно так же как и (2) - сначала partition, потом fold-left на части.

Ты же не хочешь сказать, что твоя строчка удовлетворяет условиям - n+m итераций и m+1 аллокаций? (ну или хотя бы n+m+1 - n временных элементов соберёт GC). Если это так, то (.) должен выполнять очень сложную трансформацию - не просто типичный compose функций, а некоторое «перемешивание» логики списочных функций, т.е. преобразование многопроходного алгоритма в однопроходный (сабж).

Я не вижу в задаче генерируемых списков.

Ну к примеру, как работает (2)

list --partition--> tmp-list-1 --foldl--> reduced-value --\
               \                                           > list* --> result
                `-> tmp-list-2 ---------------------------/

по моему тут достаточно и лишних итераций и лишних аллокаций, в том числе промежуточные списки присутствуют. Вариант (3) не обладает недостатком лишних итераций, но тратит память на свои аккомуляторы, варианты 4-7 не обладают вообще недостатками, но их труднее читать и писать.

Вопрос о сведении 1,2 к 3-7 в общем виде.

quasimoto ★★★★ ()
Ответ на: комментарий от Love5an

Никто из лисперов в здравом уме не программирует в терминах морфизмов, монад и сверток.

Я тоже не программирую в этих терминах. Заметь, что по итогам топика приз отдан iterate :) Никто не программирует в этих терминах, эти термины и подходы используют при изучении программирования (CS, построение компиляторов, базы данных, файловые системы).

А я всего лишь спросил - как преобразовать многопроходный функциональный код в однопроходный. Если какой-нибудь талант покажет как это сделать полагаются на CLOS(в т.ч. метаобъектный протокол) и/или кодогенерацию макросами, то это будет здорово, но пока я думаю что это пример задачи, которую довольно трудно решить без привличения формальных методов.

Вообще вопрос возник после написания одного патча для SBCL, спецификация там такая:

;;; constant folding for transitive (and then for intransitive) functions:
(reduce-constants f i p list) => `(,(fold f i (filter p list)) ,@(filter (compose 'not p) list))

и ведь написать прямо так было бы здорово, в том числе с точки зрения понятности кода. Но пришлось нагородить COLLECT + DOLIST + SETF (ну в духе loop/iterate, не суть).

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

Замечу ещё, что в соглашении о стилях (STYLE) в SBCL советуют писать в большей степени функционально - и такого кода есть там, также как и императивного (когда это нужно), также как и разных DSL. Вопрос ведь не в том, что что-то «круче» чем другое - все перечисленные примеры могут быть удобны в том или ином случае. Проблема в том, что приходится ограничиваться более топорными вариантами по причине недостаточно хорошей трансляции более лаконичных :) (а то ведь если все ({+|*|...} ...) будут при трансляции пробегаться по несколько раз - не принципиально, но не совсем хорошо; там зажали, тут зажали - и будут «тормоза»).

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

> Ты же не хочешь сказать, что твоя строчка удовлетворяет условиям - n+m итераций и m+1 аллокаций? (ну или хотя бы n+m+1 - n временных элементов соберёт GC).

Нет, я этого не хочу сказать. И никто не возьмется говорить, ибо это зависит от реализации, от флагов при компиляции, от версии компилятора и от еще кучи вещей.

Если это так, то (.) должен выполнять очень сложную трансформацию - не просто типичный compose функций, а некоторое «перемешивание» логики списочных функций, т.е. преобразование многопроходного алгоритма в однопроходный (сабж).

В том куске, что я привел, проход по списку будет один.

balodja ★★★ ()
Ответ на: комментарий от balodja

И никто не возьмется говорить, ибо это зависит от реализации, от флагов при компиляции, от версии компилятора и от еще кучи вещей.

Ну я не против - пусть будет иметься ввиду GHC текущей версии (я имел ввиду во всех вариантах SBCL текущей версии - нужно учитывать что там энергичные функции, то как происходит аллокация списков, и что существующий ряд оптимизаций).

В том куске, что я привел, проход по списку будет один.

Это связано с ленивостью?

quasimoto ★★★★ ()

почему это 4 нечитаемый? Логика работы такой ф-ции очевидна - пройтись по списку, собирая результат в зависимости от conditions. Я именно такую запись использую для сложных, на мой взгляд, алгоритмов. Из последних - поиск подграфа в графе, который, коллеги пытались реализовать циклами и запутались в нагромождении получившегося кода=)

pseudo-cat ★★★ ()
Ответ на: комментарий от balodja

> В том куске, что я привел, проход по списку будет один.

Это почему только один? partition сделает n + m разбиений списка на голову и хвост, foldl сделает ещё n. Всего разбиений будет 2n + m, что эквивалентно двум проходам

tarc ()

Правильный хаскельный подход: комбинаторы.

Вводим тип Fold:

data Fold a b = Fold {initial :: b, step :: a -> b -> b}
Этот тип говорит о том, каким образом мы будем идти по списку. Собственно проход по списку делается так:
foldList :: Fold a b -> [a] -> b
foldList f [] = initial f
foldList f (x:xs) = step f x $ foldList f xs
Заметим, что никто не мешает вместо списка использовать другие виды коллекций, лишь бы упорядочивались.

Делаем комбинатор, разваливающий список на два в соответствии с предикатом, и сворачивающий первый список одним фолдом, второй - другим:

predicateFold :: (a -> Bool) -> Fold a b -> Fold a c -> Fold a (b, c)
predicateFold pred fTrue fFalse = Fold {initial = i, step = s} where
    i = (initial fTrue, initial fFalse)
    s a (b, c) = if pred a then (step fTrue a b, c) else (b, step fFalse a c)
Парочка «строительных кирпичиков» - фолды для суммирования и накопления:
plus :: Num a => Fold a a
plus = Fold {initial = 0, step = (+)} -- можно просто Fold 0 (+)
collect :: Fold a [a]
collect = Fold {initial = [], step = (:)} -- можно просто Fold [] (:)
Финальный гвоздик - нужный нам вызов, практически декларативный:
foldList (predicateFold odd plus collect) [1,2,3,4,5,6]
Возвращает (9,[2,4,6]).

Miguel ★★★★★ ()
Ответ на: комментарий от tarc

> Это почему только один? partition сделает n + m разбиений списка на голову и хвост, foldl сделает ещё n. Всего разбиений будет 2n + m, что эквивалентно двум проходам

Если так считать, то в любом случае получится, что надо через фильтр прогнать (n + m) элементов и n элементов сложить. Любой алгоритм будет «эквивалентен двум проходам». В данном случае именно проход по списку будет один.

balodja ★★★ ()
Ответ на: комментарий от balodja

> Красиво. А как это называется?

Красиво это iterate:

(iter (for i in '(1 2 3 4 5 6))
      (if (oddp i)
          (sum i into l)
          (collect i into r))
      (finally (return (values l r))))

А все прочие варианты (включая вариант на Haskell) излишне сложные и менее выразительные.

archimag ★★★ ()
Ответ на: комментарий от archimag

Да? А по-моему

foldList (predicateFold odd plus collect) [1,2,3,4,5,6]
гораздо красивее.

balodja ★★★ ()
Ответ на: комментарий от Love5an

Да ты, оказывается монстр и делаешь полезные вещи. Даже не знаю теперь, игнорить тебя или нет.

den73 ★★★★★ ()
Ответ на: комментарий от den73

И да, тема похожа на церебральный онанизм.

den73 ★★★★★ ()
Ответ на: комментарий от balodja

> гораздо красивее.

Нет, поскольку всё решение очень длинное. А iterate позволяет легко и непринуждённо записывать самые различные алгоритмы без написания каких-либо дополнительных специальных решений.

И уж тем более выразительнее.


Издеваешься? Выразительность это когда смотришь на код и сразу понимаешь что он делает. Очевидно же, что данный код таковым не является, ибо зависит от специального решения, приведённого выше. Т.е. для понимания данного куска кода надо распарсить также связанный с ним код. Плюс для понимания результата данного вызова, в отличие от версии с iterate (где решение записано буквально), надо напрягать мозг.

archimag ★★★ ()
Ответ на: комментарий от archimag

анонимус одобряет - чтение кода не менее важно чем его написание, а порой и важнее

anonymous ()
Ответ на: комментарий от Miguel

А кстати, на шутауте Хаскель уверенно сливает С по двум параметрам (скорость и расход памяти), при этом объём кода, по сути, идентичен. Вот и вся наука.

den73 ★★★★★ ()
Ответ на: комментарий от anonymous

> чтение кода не менее важно чем его написание, а порой и важнее

Всегда важнее, если только речь не идёт об одноразовых скриптах.

archimag ★★★ ()
Ответ на: комментарий от archimag

Нет, поскольку всё решение очень длинное. А iterate позволяет легко и непринуждённо записывать самые различные алгоритмы без написания каких-либо дополнительных специальных решений.

Если к решению с iterate приплюсовать исходный код iterate, тогда получится аналог того, что изобразил Мигель. Аналогом показанных тобой строк является всего одна строчка

foldList (predicateFold odd plus collect) [1,2,3,4,5,6]

Издеваешься?

Я уже много раз на ЛОР'е видел куски кода с iterate, и у меня они вызывают сплошное недоумение. /me не понимает, как это работает. Видимо, чтобы их осознать, придется-таки почитать сырцы iterate.

Ну, чтобы понять решение Мигеля, мне понадобилось одним глазом пробежаться по коду. Так что тут все весьма и весьма выразительно. И очень хочется узнать, есть ли библиотека, которая реализует такой подход к обработке списков.

Выразительность это когда смотришь на код и сразу понимаешь что он делает.

Не хочется тебя огорчать, но это не так.

Очевидно же, что данный код таковым не является, ибо зависит от специального решения, приведённого выше.

А приведенный код на лиспе не зависит от iterate?

Т.е. для понимания данного куска кода надо распарсить также связанный с ним код.

Либо прочитать описание API, да.

Плюс для понимания результата данного вызова, в отличие от версии с iterate (где решение записано буквально), надо напрягать мозг.

Это тебе не надо напрягать мозг, потому что ты уже напряг, чтобы осознать iterate. А вот мне приходится.

balodja ★★★ ()
Ответ на: комментарий от balodja

Сырцы iterate читать не обязательно, достаточно почитать мануал, он хороший. А так вообще, конечно, iterate знать нужно. То, что в стандарте loop, а не iterate - это просто диверсия против лиспа.

den73 ★★★★★ ()
Ответ на: комментарий от balodja
(итерации (для i в списке '(1 2 3 4 5 6))
      (если i чётное
          (суммировать i в переменную l)
          (иначе накапливать i в переменную r))
      (по окончанию итераций (возвратить два значения: l и r))))

а теперь понятно?
pseudo-cat ★★★ ()
Ответ на: комментарий от balodja

Ты сравниваешь универсальное решение (iterate) с частным костылем, угу.

archimag ★★★ ()
Ответ на: комментарий от balodja

> Я сравниваю подходы к решению.

Вот и о чём, что подход на базе iterate более красив, гибок и выразителен для большинства подобных задач. Вообще, на фоне iterate «чисто функциональный» подход к обработке последовательностей выглядит убогим.

archimag ★★★ ()
Ответ на: комментарий от archimag

> Вообще, на фоне iterate «чисто функциональный» подход к обработке последовательностей выглядит убогим.

В коммон лиспе? Не буду спорить, тебе лучше знать.

balodja ★★★ ()
Ответ на: комментарий от balodja

Не гони, просто опыт использования разных подходов.

archimag ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.