Лисп, итератор

> <i>Хочется сделать функцию, которая будет принимать некий итератор, проходить по нему и что-нибудь делать.</i>

Итераторы -- это антипаттерн. В советской России ты можешь саму функцию передать туда, где ее последовательно применят к токену в файле или элементу списка :)

cl-containers?

А что, сделать что-то вроде (map 'что-нужно-получить #'функция то-с-чем-надо-что-сделать) не прокатит?

Если речь идёт о Common Lisp, то вопрос о том, как правильно итерировать, недавно обсуждался - http://www.linux.org.ru/view-message.jsp?msgid=2745078
Особенно хорошая статья
http://common-lisp.net/project/iterate/doc/Don_0027t-Loop-Iterate.html
- перечислены разные способы итерировать.

Например, чтобы в iterate пройти по файлу и сделать что-то с каждой строкой, нужно написать
(iter
(for line in-file "my-file" using 'read-line)
... ; Ваши действия с переменной line
)

мне лично такой стиль нравится и я считаю его оптимальным:

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

Во-вторых, можно одновременно итерировать ещё по чему-то, например, ввести счётчик строк, агрегировать элементы, добавлять "пролог" и "эпилог". В виде функции написать то же самое будет гораздо труднее.
(iter
(for s in-file "my-file" using 'read-line) ; идём по файлу
(for l in '(1 2 3 4)) ; идём по списку
(for i from 0)
(declare (simple-string s) (fixnum i)) ; тип
(collecting s into lines) ; агрегирование
...)

В-третьих, макрос iter достаточно умён, чтобы сгенерировать быстрый код.

В-четвёртых, не нужно договариваться об обозначении конца файла. Если программировать общо, то любой возврат, который Вы захотите считать концом файла, может рано или поздно встретиться в последовательности. Значит, нужно или рисковать, или передавать его при вызове Вашей функции, а это не особо элегантно.

Но если Вам всё же критично сделать именно итератор, то нужно определиться с его оформлением. Например, можно ли двигаться только вперёд или назад тоже? Как обозначить конец последовательности? Как закрывать? И, если уж Вы заговорили об оптимизации, то нужно дать пользователю возможность задекларировать типы переменных в итераторе. Iterate умеет и это.

Вообще лиспом служит Scheme, но это не важно.

Передать нужную функцию, это интересная идея, у меня мозги не в том направлении крутились. Я об этом обязательно подумаю.

Закрывать смысла не вижу, это не задача обработчика информации. Закрывать скорее будет тот, кто его вызывает. Т.е. открыли, сделали итератор, вызвали обработчик, закрыли.

Я сейчас думаю, фактически 2 главных применения это чтение из файла и обработка строки. Возможно я просто сразу буду вычитывать всё в строку и сведу эти случаи к одному.

За мысли спасибо, буду изучать.

..... Петрович оптимизировал лифт ... 
Потратил почти два часа, чтобы сделать пример того, что Вы хотите. 
Честно пытался сделать его таким же быстрым, как и iterate, но не 
получилось. Iterate всё равно работает в 3 раза быстрее на sbcl:

вызов пользовательской функции для итератора
  0.01 seconds of real time
  0.008001 seconds of user run time
  0 bytes consed.
обычный цикл
  0.003 seconds of real time
  0.004 seconds of user run time
  0 bytes consed.


и в 20 (!) раз - на lispworks:
вызов пользовательской функции для итератора
user time    =      0.200
Elapsed time =   0:00:00
Allocation   = 2192 bytes standard / 1298 bytes conses

обычный цикл
user time    =      0.010
Elapsed time =   0:00:00
Allocation   = 0 bytes standard / 0 bytes conses

Попутно заметим, что sbcl порвал lispworks. Хотя это может быть из-за 
того, что lispworks - безплатное персональное издание и на winxp, а sbcl - на линуксе. Во всяком случае, обе реализации сумели обойтись
одним стеком и не порождать ничего в хипе (в худшем случае лиспворкс
сожрал 3кб хипа, но для списка из 500000 элементов - это явно O(1)). 

Вот сам файл. Пришлось задекларировать все типы, которые я смог - это
обязательное требование для скорости. Хотя, возможно, от части 
деклараций можно отказаться и компилятор сам догадается, но мне лень
уже это проверять. 

90% файла - это вариант с "итератором". В конце 7 строчек - это более
общее (!) решение, использущее макрос iterate. По-моему, вполне
очевидно, что функциональный подход здесь слил. Хотя, может быть, это
я - ламер. Может быть, кто-нибудь сделает лучше? 

;;; Пример итератора. 
(defpackage "PERVERSE-ITERATOR" (:use :cl :iterate))
(in-package :perverse-iterator)
(declaim (optimize (safety 0) (speed 3) (space 0)))

(declaim (ftype (function (list) (function () fixnum)) 
         make-list-iterator))
(defun make-list-iterator (list)
  "предполагаем, что список состоит из целых чисел. 
0 - признак конца (глупо!)"
  (declare (cons list))
  (let ((sublist list)
        (end (the fixnum 0)))
    (declare (cons sublist) (fixnum end))
    (lambda () 
      (the fixnum 
           (cond
            ((= end (the fixnum 1)) (the fixnum 0))
            ((cdr sublist) (pop sublist))
            (t (setf end 1) (car sublist)))))))

(declaim (ftype (function ((function (fixnum) null) 
                (function () fixnum)) null) 
          call-fn-on-iterator))
(defun call-fn-on-iterator (fn iterator) 
  "вызвать функцию fn для каждого значения, возвращаемого итератором"
  (do ((x (funcall iterator) (funcall iterator)))
      ((= x (the fixnum 0)) nil)
    (declare (fixnum x))
    (funcall fn x)))

(defparameter *lst* (iter (for i from 1 to 500000) (collecting 1)))
(declaim (cons *lst*))

(defun test-call-fn-on-iterator ()
  "суммируем все значения, которые вернул итератор"
  (let ((sum 0))
    (declare (fixnum sum))
    (call-fn-on-iterator 
     (lambda (x) 
       (declare (fixnum x)) 
       (incf sum x)) 
     (make-list-iterator *lst*))
    sum))


(defun test-simple-iterate () 
  (iter 
    (for x in *lst*)
    (summing x into sum)
    (declare (fixnum x) (fixnum sum))
    (finally (return sum))
    ))

(time (test-call-fn-on-iterator))
(time (test-simple-iterate))
;;; eof

А в Scheme вроде есть такие слова как delay и force. Наиболее естественно это реализовать как раз с помощью delay, если сопрограммы не нравятся. Хотя не факт, что сопрограммы будут тормозить - ведь в C тоже есть сопрограммы, и они как-то умудряются работать с типичной для C скоростью. Также не факт, что delay сам не основан на сопрограммах.

Хороший компилятор Scheme должен превратить первое во второе...

Ну и остаётся вариант с лексическими замыканиями (как я сделал для Common Lisp, в котором сопрограмм нету).

Лучше написать все три варианта и сравнить время выполнения.

А вообще, лучше уточняйте, что имеете в виду, потому что Scheme и Common Lisp - это, в общем-то, разные языки. Ну и если хотите скорости, то Scheme слаба, как я понимаю. Scheme - это язык прототипирования.

Анонимус, попытался поставить cl-containers, но не ставится
dynamic-classes-test. А могли бы Вы запостить код суммирования
списка целых чисел на этих cl-контейнерах? О... вот нашёл:

http://common-lisp.net/project/dynamic-classes/

> (let ((i (make-iterator '(1 2 3) :circular t :transform #'sqrt)))  
	    (loop repeat 5 when (move-forward-p i) do  
		 (print (next-element i))))  
1.0  
1.4142135  
1.7320508  
1.0  
1.4142135 

Ну что сказать... Нормальный лисп говорит:
"пройди по списку"
На iterate тот же код пишется так:


Лисп, повреждённый извращённым (после C и Явы) ОО мышлением, говорит:
"сделай итератор хождения по списку"
"пройди по итератору"
За что я не люблю такое ОО - за нарушение принципа лезвия Оккама. Не
 знаю, как в других языках,а в лиспе в этом нет нужды, т.к. есть 
полноценное метапрограммирование. Итератор, практически всегда - это не
объект, а "объект времени компиляции", который нужно вычислить в статике и 
превратить в вычисления на стеке, безусловные переходы и т.п., если только
не (debug 3). Но если вообще этого объекта нет, а есть макрос, то так удобнее 
для всех - и писать удобнее, и компилятору тоже удобнее компилировать, и не
нужно морочиться по поводу того, "а сможет ли компилятор сделать это в статике, 
а не в динамике". Нормальный лисп честно делает его макросом. cl-containers 
повторяют извращённый путь С++ и Явы (которые я именно за этот путь считаю
убогими и... ладно, не будем ругаться утром в субботу). 
Что мы видим внутри? 

(defmethod make-iterator  
    (iteratee &rest args &key (iterator-class nil) &allow-other-keys)  
  (apply #'make-instance  
	 (apply #'determine-iterator-class iteratee iterator-class args)  
         :container iteratee  
         args)) 
Т.е., это видимо, называется "аспектно-ориентированное программирование". 
Но зачем же в динамике? Слишком быстрая машина? 

Может быть, я ламер и на самом деле, компилятор всё это сможет сделать во время
компиляции, хотя я сильно сомневаюсь, что apply магически перенесётся в статику. 
Но тогда, если Вам интересно, может быть, Вы прогоните по скорости и сравните 
с моим тестом - мне что-то уже расхотелось ставить эти cl-containers на свою машину... 
Начинка хорошая, но оболочка... И что у Вас получится - напишите, будьте так добры. 

Спасибо, познавательно почитать. Буду разбираться.