1 ;;; iterators.el --- Functions for working with iterators -*- lexical-binding: t -*-
3 ;; Copyright (C) 2015 Free Software Foundation, Inc
5 ;; Author: Michael Heerdegen <michael_heerdegen@web.de>
6 ;; Maintainer: Michael Heerdegen <michael_heerdegen@web.de>
7 ;; Created: Mar 18 2015
8 ;; Keywords: extensions, elisp
9 ;; Compatibility: GNU Emacs >=25
11 ;; Package-Requires: ((emacs "25"))
14 ;; GNU Emacs is free software: you can redistribute it and/or modify
15 ;; it under the terms of the GNU General Public License as published by
16 ;; the Free Software Foundation, either version 3 of the License, or
17 ;; (at your option) any later version.
19 ;; GNU Emacs is distributed in the hope that it will be useful,
20 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
21 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 ;; GNU General Public License for more details.
24 ;; You should have received a copy of the GNU General Public License
25 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
30 ;; This package extends "generator.el" with higher-level functions.
35 ;; - hook ilists into seq.el via `cl-defgeneric'
41 (eval-when-compile (require 'cl-lib))
47 (defmacro iterator-make (&rest body)
48 "Create an anonymous iterator.
49 This is equivalent to (funcall (iter-lambda () BODY...))"
50 `(funcall (iter-lambda () ,@body)))
53 ;;;; Special simple iterators
55 (defun iterator-from-elts (&rest elements)
56 "Return an iterator generating the ELEMENTS."
57 (iterator-make (while elements (iter-yield (pop elements)))))
59 (defun iterator-cycle-elts (&rest elements)
60 "Return an iterator cycling through the ELEMENTS.
61 Unlike `iterator-from-elts', after the last of the ELEMENTS has been
62 generated, the resulting iterator will generate all ELEMENTS
66 (setcdr (last elements) elements)
67 (iterator-make (while t (iter-yield (pop elements))))))
69 (defun iterator--cons (val iterator)
72 (iter-yield-from iterator)))
74 (defun iterator-iterate-function (function value)
75 "Return an iterator of repeated applications of FUNCTION to VALUE.
76 The sequence of returned elements is starting with VALUE. Any
77 successive element will be found by calling FUNCTION on the
82 (while t (iter-yield (setq value (funcall function value)))))))
84 (defun iterator-number-range (&optional start end inc)
85 "Return an iterator of a number range.
86 START denotes the first number and defaults to 0. The second,
87 optional argument END specifies the upper limit (exclusively).
88 If nil, the returned iterator is infinite. INC is the increment
89 used between the numbers and defaults to 1."
90 (let* ((inc (or inc +1))
94 (let ((comp (if (> inc 0) #'< #'>)))
96 (while (funcall comp i end)
97 (iter-yield (prog1 i (cl-incf i inc))))))
98 (iterator-make (while t (iter-yield (prog1 i (cl-incf i))))))))
100 (iter-defun iterator-of-directory-files-1 (directory &optional match nosort recurse follow-links)
101 "Helper for `iterator-of-directory-files'."
102 (when (file-accessible-directory-p directory)
103 (let ((files (directory-files directory t match nosort)) file)
104 (while (setq file (pop files))
106 ((not (file-directory-p file))
108 ((member (file-name-nondirectory (directory-file-name file))
112 (when (and (or follow-links (not (file-symlink-p file)))
113 (if (functionp recurse) (funcall recurse file) recurse))
114 (iter-yield-from (iterator-of-directory-files-1
115 file match nosort recurse follow-links)))))))))
117 (defun iterator-of-directory-files (directory &optional full match nosort recurse follow-links)
118 "Return an iterator of names of files in DIRECTORY.
119 Don't include files named \".\" or \"..\". The arguments FULL,
120 MATCH and NOSORT are like in `directory-files'.
122 Optional argument RECURSE non-nil means recurse on
123 subdirectories. If RECURSE is a function, it should be a
124 predicate accepting one argument, an absolute file name of a
125 directory, and return non-nil when the returned iterator should
126 recurse into that directory. Any other non-nil value means
127 recurse into every readable subdirectory.
129 Even with recurse non-nil, don't descent into directories by
130 following symlinks unless FOLLOW-LINKS is non-nil."
132 (lambda (file) (if full file (file-relative-name file directory)))
133 (iterator-of-directory-files-1 directory match nosort recurse follow-links)))
136 ;;;; Operations on iterators, transducers
138 (defun iterator-filter (predicate iterator)
139 "Return an iterator filtering ITERATOR with PREDICATE.
140 This new iterator will return elements in the same order as
141 ITERATOR, but only those that fulfill PREDICATE, a function that
142 accepts one argument."
145 (let ((el (iter-next iterator)))
146 (while (not (funcall predicate el))
147 (setq el (iter-next iterator)))
150 (defun iterator-delq (elt iterator)
151 "Return an iterator of the elements of ITERATOR not `eq' to ELT."
152 (iterator-filter (lambda (el) (not (eq el elt))) iterator))
154 (defun iterator-concatenate (&rest iterators)
155 "Concatenate the ITERATORS.
156 Return a new iterator that returns the elements generated by
157 each iterator in ITERATORS, in order. The ITERATORS are each
158 invoked to completion, in order."
161 (while (setq current (pop iterators))
162 (iter-yield-from current)))))
164 (defun iterator-map (function &rest iterators)
165 "Return an iterator mapping FUNCTION across ITERATORS.
166 If there are several ITERATORS, FUNCTION is called with that
167 many arguments. The resulting iterator will produce elements as
168 long as the shortest iterator does."
170 (while t (iter-yield (apply function (mapcar #'iter-next iterators))))))
172 (defun iterator-take-while (predicate iterator)
173 "Return an iterator representing a \"do-while\" loop.
174 It will invoke ITERATOR to produce elements as long they fulfill
175 PREDICATE and stop then."
178 (while (funcall predicate (setq el (iter-next iterator)))
181 (defun iterator-take-until (predicate iterator)
182 "Return an iterator representing an \"until-do\" loop.
183 It will invoke ITERATOR to produce elements until one fulfills
184 PREDICATE. It will stop after returning this element."
187 (while (not (funcall predicate (setq el (iter-next iterator))))
191 (defun iterator-take (n iterator)
192 "Return an iterator of the first N elements of ITERATOR.
193 This iterator generates at most the first N elements generated
194 by ITERATOR, in order."
195 (iterator-make (while (>= (cl-decf n) 0)
196 (iter-yield (iter-next iterator)))))
198 (defun iterator-scan (function init iterator)
199 "Return an iterator of successive reduced values.
200 If the elements generated by iterator i are i_1, i_2, ..., the
201 elements s_1, s_2, ... of the iterator returned by
202 \(iterator-scan f init i\) are defined recursively by
205 s_(n+1) = (funcall f s_n i_n)
207 as long as i_n exists.
209 Example: (iterator-scan #'* 1 (iterator-number-range 1))
210 returns an iterator of the factorials."
214 (iterator-map (lambda (el) (setq res (funcall function res el)))
220 (defun iterator-flush (iterator)
221 "Request all elements from ITERATOR, for side effects only."
223 (while t (iter-next iterator))
224 (iter-end-of-sequence nil)))
227 ;;;; Processing elements
229 (defun iterator-reduce (function init iterator)
230 "Reduce two-argument FUNCTION across ITERATOR starting with INIT.
231 This is the same value as the expression
233 (iter-last (iterator-scan function init iterator))
237 (iterator-flush (iterator-map (lambda (el) (setq res (funcall function res el))) iterator))
240 (defun iterator-to-list (iterator)
241 "Convert ITERATOR into a list.
242 Run ITERATOR until it runs out of elements and return a list of
243 the generated elements."
244 (nreverse (iterator-reduce (lambda (x y) (cons y x)) () iterator)))
246 (defun iterator-last (iterator)
247 "Request all elements from ITERATOR and return the last one."
248 (let ((el (iter-next iterator)))
250 (while t (setq el (iter-next iterator)))
251 (iter-end-of-sequence el))))
253 (defun iterator-count (iterator)
254 "Request all elements from ITERATOR and return their count."
255 (iterator-reduce (lambda (s _el) (1+ s)) 0 iterator))
257 (defun iterator-some (predicate &rest iterators)
258 "Return non-nil if PREDICATE is true for any element of ITER or ITERs.
259 If so, return the true (non-nil) value returned by PREDICATE.
260 \n(fn PREDICATE ITER...)"
263 (apply #'iterator-map
264 (lambda (&rest elts) (let (res) (when (setq res (apply predicate elts))
265 (throw 'success res))))
269 (defun iterator-every (predicate &rest iterators)
270 "Return non-nil if PREDICATE is true for every element of ITER or ITERs.
271 \n(fn PREDICATE ITER...)"
272 (not (apply #'iterator-some (lambda (&rest args) (not (apply predicate args))) iterators)))
274 (defun iterator-max (iterator &optional function)
275 "Return an element of finite ITERATOR maximizing FUNCTION.
276 Request all elements from ITERATOR and pass them to FUNCTION, a
277 one-argument function that must return a number. Return an
278 element for which FUNCTION was maximal. Raise an error if
279 ITERATOR produced no elements. FUNCTION defaults to `identity'.
281 Example: if ITERATOR is an iterator of lists, this would return
282 a longest generated list: (iterator-max iterator #'length)."
283 (let ((first (iter-next iterator))
284 (function (or function #'identity)))
286 (lambda (x y) (if (< (funcall function x) (funcall function y)) y x))
289 (defun iterator-min (iterator &optional function)
290 "Return an element of ITERATOR that minimizes FUNCTION.
291 Request all elements from ITERATOR and pass them to FUNCTION, a
292 one-argument function that must return a number. Return an
293 element for which FUNCTION was minimal. Raise an error if
294 ITERATOR produced no elements. FUNCTION defaults to `identity'."
295 (let ((function (or function #'identity)))
296 (iterator-max iterator (lambda (x) (- (funcall function x))))))
298 (defun iterator-mapconcat (function iterator separator)
299 "Apply FUNCTION to each element of ITERATOR, and concat the results as strings.
300 In between of each pair of results, stick in SEPARATOR. This is
301 like `mapconcat', but for iterators."
302 (let ((first (iter-next iterator)))
303 (iterator-reduce (lambda (x y) (concat x separator y))
304 (funcall function first)
305 (iterator-map function iterator))))
308 ;;;; ILists - "Delayed" lists via iterators
310 (defconst ilist--last-link-tag 'ilist--last-link-tag)
312 (defun iterator-to-ilist (iterator)
313 "Return an ilist using ITERATOR to produce elements."
314 (cons ilist--last-link-tag iterator))
316 (defmacro ilist-make (expr)
317 "Return an ilist calling an iterator using EXPR to produce elements."
318 `(iterator-to-ilist (iterator-make ,expr)))
321 (cons ilist--last-link-tag nil)
322 "A distinguished empty ilist.")
324 (defun ilistp (object)
325 "Return t if OBJECT is an ilist, that is, a cons cell or nil.
326 Otherwise, return nil."
329 (defun ilist-car (ilist)
330 "Return the first element of ILIST.
331 Error if arg is not nil and not a cons cell."
332 (if (eq (car ilist) ilist--last-link-tag)
333 (let ((iterator (cdr ilist)) new-el)
334 (if (null iterator) nil
336 (prog1 (setq new-el (iter-next iterator))
337 (setcar ilist new-el)
338 (setcdr ilist (cons ilist--last-link-tag iterator)))
339 (iter-end-of-sequence (setcdr ilist nil)
343 (defun ilist-empty-p (ilist)
344 "Return t if ILIST is empty."
345 (ignore (ilist-car ilist))
348 (defun ilist-cdr (ilist)
349 "Return the `ilist-cdr' of ILIST.
350 Error if arg is not nil and not a cons cell."
351 (if (ilist-empty-p ilist) ilist (cdr ilist)))
353 (defun ilist-cons (el ilist)
354 "Return a new ilist with EL as `ilist-car' ILIST as `ilist-cdr'."
357 (defun ilist-nthcdr (n ilist)
358 "Take `ilist-cdr' N times on ILIST, return the result."
359 (cl-dotimes (_ n) (cl-callf ilist-cdr ilist))
362 (defun ilist-nth (n ilist)
363 "Return the Nth element of ILIST.
364 N counts from zero. If ILIST is not that long, nil is returned."
365 (ilist-car (ilist-nthcdr n ilist)))
367 (defun ilist-to-iterator (ilist)
368 "Return an iterator generating the elements of ILIST.
369 The structure of ILIST is updated as side effect if new elements
370 are generated by the returned iterator which were not yet
373 (while (not (ilist-empty-p ilist))
374 (prog1 (iter-yield (ilist-car ilist))
375 (cl-callf ilist-cdr ilist)))))
377 (defun ilist-mapcar (function ilist)
378 "Apply FUNCTION to each element of ILIST, and make an ilist of the results.
379 The result is an ilist just as long as ILIST."
381 (iterator-map function (ilist-to-iterator ilist))))
383 (defun ilist (&rest objects)
384 "Return a newly created ilist with specified arguments as elements."
385 (nconc objects ilist-null))
387 (defun list-to-ilist (list)
388 "Convert LIST into an ilist.
389 The result is an ilist containing the same elements as LIST in
390 the same order. This is a destructive operation modifying LIST."
391 (nconc list ilist-null))
393 (defun ilist-to-list (ilist)
394 "Return a list of all elements of ILIST.
395 All elements of ILIST are generated as side effect."
397 (while (not (ilist-empty-p ilist))
398 (push (ilist-car ilist) elts)
399 (cl-callf ilist-cdr ilist))
402 (defun ilist-concatenate (&rest ilists)
403 "Concatenate the ILISTS into a new ilist and return the result.
404 New elements in the argument ilists are generated when being
405 referenced in the concatenated ilist. Apart from that, the
406 argument ilists are not modified."
408 (apply #'iterator-concatenate
409 (mapcar #'ilist-to-iterator ilists))))
411 (define-error 'empty-ilist "Empty ilist")
413 (defun ilist-setcar (ilist object)
414 "Set the first element of ILIST to OBJECT.
415 Error if ILIST is empty. Return OBJECT."
416 (if (ilist-empty-p ilist)
417 (signal 'empty-ilist nil)
418 (setcar ilist object)))
420 (defun ilist-setcdr (ilist newcdr)
421 "Set the `ilist-cdr' of ILIST to NEWCDR.
422 Error if ILIST is empty. Return NEWCDR."
423 (if (ilist-empty-p ilist)
424 (signal 'empty-ilist nil)
425 (setcdr ilist newcdr)))
430 ;;; iterators.el ends here