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.
41 (defmacro iterator-make (&rest body)
42 "Create an anonymous iterator.
43 This is equivalent to (funcall (iter-lambda () BODY...))"
44 `(funcall (iter-lambda () ,@body)))
47 ;; Special simple iterators
49 (defun iterator-from-elts (&rest elements)
50 "Return an iterator generating the ELEMENTS."
51 (iterator-make (while elements (iter-yield (pop elements)))))
53 (defun iterator-cycle-elts (&rest elements)
54 "Return an iterator cycling through the ELEMENTS.
55 Unlike `iterator-from-elts', after the last of the ELEMENTS has been
56 generated, the resulting iterator will generate all ELEMENTS
60 (setcdr (last elements) elements)
61 (iterator-make (while t (iter-yield (pop elements))))))
63 (defun iterator--cons (val iterator)
66 (iter-yield-from iterator)))
68 (defun iterator-iterate-function (function value)
69 "Return an iterator of repeated applications of FUNCTION to VALUE.
70 The sequence of returned elements is starting with VALUE. Any
71 successive element will be found by calling FUNCTION on the
76 (while t (iter-yield (setq value (funcall function value)))))))
78 (defun iterator-number-range (&optional start end inc)
79 "Return an iterator of a number range.
80 START denotes the first number and defaults to 0. The second,
81 optional argument END specifies the upper limit (exclusively).
82 If nil, the returned iterator is infinite. INC is the increment
83 used between the numbers and defaults to 1."
84 (let* ((inc (or inc +1))
88 (let ((comp (if (> inc 0) #'< #'>)))
90 (while (funcall comp i end)
91 (iter-yield (prog1 i (cl-incf i inc))))))
92 (iterator-make (while t (iter-yield (prog1 i (cl-incf i))))))))
95 ;; Operations on iterators, transducers
97 (defun iterator-filter (predicate iterator)
98 "Return an iterator filtering ITERATOR with PREDICATE.
99 This new iterator will return elements in the same order as
100 ITERATOR, but only those that fulfill PREDICATE, a function that
101 accepts one argument."
104 (let ((el (iter-next iterator)))
105 (while (not (funcall predicate el))
106 (setq el (iter-next iterator)))
109 (defun iterator-delq (elt iterator)
110 "Return an iterator of the elements of ITERATOR not `eq' to ELT."
111 (iterator-filter (lambda (el) (not (eq el elt))) iterator))
113 (defun iterator-concatenate (&rest iterators)
114 "Concatenate the ITERATORS.
115 Return a new iterator that returns the elements generated by
116 each iterator in ITERATORS, in order. The ITERATORS are each
117 invoked to completion, in order."
120 (while (setq current (pop iterators))
121 (iter-yield-from current)))))
123 (defun iterator-map (function &rest iterators)
124 "Return an iterator mapping FUNCTION across ITERATORS.
125 If there are several ITERATORS, FUNCTION is called with that
126 many arguments. The resulting iterator will produce elements as
127 long as the shortest iterator does."
129 (while t (iter-yield (apply function (mapcar #'iter-next iterators))))))
131 (defun iterator-take-while (predicate iterator)
132 "Return an iterator representing a \"do-while\" loop.
133 It will invoke ITERATOR to produce elements as long they fulfill
134 PREDICATE and stop then."
137 (while (funcall predicate (setq el (iter-next iterator)))
140 (defun iterator-take-until (predicate iterator)
141 "Return an iterator representing an \"until-do\" loop.
142 It will invoke ITERATOR to produce elements until one fulfills
143 PREDICATE. It will stop after returning this element."
146 (while (not (funcall predicate (setq el (iter-next iterator))))
150 (defun iterator-take (n iterator)
151 "Return an iterator of the first N elements of ITERATOR.
152 This iterator generates at most the first N elements generated
153 by ITERATOR, in order."
154 (iterator-make (while (>= (cl-decf n) 0)
155 (iter-yield (iter-next iterator)))))
157 (defun iterator-scan (function init iterator)
158 "Return an iterator of successive reduced values.
159 If the elements generated by iterator i are i_1, i_2, ..., the
160 elements s_1, s_2, ... of the iterator returned by
161 \(iterator-scan f init i\) are defined recursively by
164 s_(n+1) = (funcall f s_n i_n)
166 as long as i_n exists.
168 Example: (iterator-scan #'* 1 (iterator-number-range 1))
169 returns an iterator of the factorials."
173 (iterator-map (lambda (el) (setq res (funcall function res el)))
179 (defun iterator-flush (iterator)
180 "Request all elements from ITERATOR, for side effects only."
182 (while t (iter-next iterator))
183 (iter-end-of-sequence nil)))
186 ;; Processing elements
188 (defun iterator-reduce (function init iterator)
189 "Reduce two-argument FUNCTION across ITERATOR starting with INIT.
190 This is the same value as the expression
192 (iter-last (iterator-scan function init iterator))
196 (iterator-flush (iterator-map (lambda (el) (setq res (funcall function res el))) iterator))
199 (defun iterator-to-list (iterator)
200 "Convert ITERATOR into a list.
201 Run ITERATOR until it runs out of elements and return a list of
202 the generated elements."
203 (nreverse (iterator-reduce (lambda (x y) (cons y x)) () iterator)))
205 (defun iterator-last (iterator)
206 "Request all elements from ITERATOR and return the last one."
207 (let ((el (iter-next iterator)))
209 (while t (setq el (iter-next iterator)))
210 (iter-end-of-sequence el))))
212 (defun iterator-count (iterator)
213 "Request all elements from ITERATOR and return their count."
214 (iterator-reduce (lambda (s _el) (1+ s)) 0 iterator))
216 (defun iterator-some (predicate &rest iterators)
217 "Return non-nil if PREDICATE is true for any element of ITER or ITERs.
218 If so, return the true (non-nil) value returned by PREDICATE.
219 \n(fn PREDICATE ITER...)"
222 (apply #'iterator-map
223 (lambda (&rest elts) (let (res) (when (setq res (apply predicate elts))
224 (throw 'success res))))
228 (defun iterator-every (predicate &rest iterators)
229 "Return non-nil if PREDICATE is true for every element of ITER or ITERs.
230 \n(fn PREDICATE ITER...)"
231 (not (apply #'iterator-some (lambda (&rest args) (not (apply predicate args))) iterators)))
233 (defun iterator-max (iterator &optional function)
234 "Return an element of finite ITERATOR maximizing FUNCTION.
235 Request all elements from ITERATOR and pass them to FUNCTION, a
236 one-argument function that must return a number. Return an
237 element for which FUNCTION was maximal. Raise an error if
238 ITERATOR produced no elements. FUNCTION defaults to `identity'.
240 Example: if ITERATOR is an iterator of lists, this would return
241 a longest generated list: (iterator-max iterator #'length)."
242 (let ((first (iter-next iterator))
243 (function (or function #'identity)))
245 (lambda (x y) (if (< (funcall function x) (funcall function y)) y x))
248 (defun iterator-min (iterator &optional function)
249 "Return an element of ITERATOR that minimizes FUNCTION.
250 Request all elements from ITERATOR and pass them to FUNCTION, a
251 one-argument function that must return a number. Return an
252 element for which FUNCTION was minimal. Raise an error if
253 ITERATOR produced no elements. FUNCTION defaults to `identity'."
254 (let ((function (or function #'identity)))
255 (iterator-max iterator (lambda (x) (- (funcall function x))))))
257 (defun iterator-mapconcat (function iterator separator)
258 "Apply FUNCTION to each element of ITERATOR, and concat the results as strings.
259 In between of each pair of results, stick in SEPARATOR. This is
260 like `mapconcat', but for iterators."
261 (let ((first (iter-next iterator)))
262 (iterator-reduce (lambda (x y) (concat x separator y))
263 (funcall function first)
264 (iterator-map function iterator))))
267 ;;; ILists - "Delayed" lists via iterators
269 (defconst ilist--last-link-tag 'ilist--last-link-tag)
271 (defun iterator-to-ilist (iterator)
272 "Return an ilist using ITERATOR to produce elements."
273 (cons ilist--last-link-tag iterator))
275 (defmacro ilist-make (expr)
276 "Return an ilist calling an iterator using EXPR to produce elements."
277 `(iterator-to-ilist (iterator-make ,expr)))
280 (cons ilist--last-link-tag nil)
281 "A distinguished empty ilist.")
283 (defun ilistp (object)
284 "Return t if OBJECT is an ilist, that is, a cons cell or nil.
285 Otherwise, return nil."
288 (defun ilist-car (ilist)
289 "Return the first element of ILIST.
290 Error if arg is not nil and not a cons cell."
291 (if (eq (car ilist) ilist--last-link-tag)
292 (let ((iterator (cdr ilist)) new-el)
293 (if (null iterator) nil
295 (prog1 (setq new-el (iter-next iterator))
296 (setcar ilist new-el)
297 (setcdr ilist (cons ilist--last-link-tag iterator)))
298 (iter-end-of-sequence (setcdr ilist nil)
302 (defun ilist-empty-p (ilist)
303 "Return t if ILIST is empty."
304 (ignore (ilist-car ilist))
307 (defun ilist-cdr (ilist)
308 "Return the `ilist-cdr' of ILIST.
309 Error if arg is not nil and not a cons cell."
310 (if (ilist-empty-p ilist) ilist (cdr ilist)))
312 (defun ilist-cons (el ilist)
313 "Return a new ilist with EL as `ilist-car' ILIST as `ilist-cdr'."
316 (defun ilist-nthcdr (n ilist)
317 "Take `ilist-cdr' N times on ILIST, return the result."
318 (cl-dotimes (_ n) (cl-callf ilist-cdr ilist))
321 (defun ilist-nth (n ilist)
322 "Return the Nth element of ILIST.
323 N counts from zero. If ILIST is not that long, nil is returned."
324 (ilist-car (ilist-nthcdr n ilist)))
326 (defun ilist-to-iterator (ilist)
327 "Return an iterator generating the elements of ILIST.
328 The structure of ILIST is updated as side effect if new elements
329 are generated by the returned iterator which were not yet
332 (while (not (ilist-empty-p ilist))
333 (prog1 (iter-yield (ilist-car ilist))
334 (cl-callf ilist-cdr ilist)))))
336 (defun ilist-mapcar (function ilist)
337 "Apply FUNCTION to each element of ILIST, and make an ilist of the results.
338 The result is an ilist just as long as ILIST."
340 (iterator-map function (ilist-to-iterator ilist))))
342 (defun ilist (&rest objects)
343 "Return a newly created ilist with specified arguments as elements."
344 (nconc objects ilist-null))
346 (defun list-to-ilist (list)
347 "Convert LIST into an ilist.
348 The result is an ilist containing the same elements as LIST in
349 the same order. This is a destructive operation modifying LIST."
350 (nconc list ilist-null))
352 (defun ilist-to-list (ilist)
353 "Return a list of all elements of ILIST.
354 All elements of ILIST are generated as side effect."
356 (while (not (ilist-empty-p ilist))
357 (push (ilist-car ilist) elts)
358 (cl-callf ilist-cdr ilist))
361 (defun ilist-concatenate (&rest ilists)
362 "Concatenate the ILISTS into a new ilist and return the result.
363 New elements in the argument ilists are generated when being
364 referenced in the concatenated ilist. Apart from that, the
365 argument ilists are not modified."
367 (apply #'iterator-concatenate
368 (mapcar #'ilist-to-iterator ilists))))
370 (define-error 'empty-ilist "Empty ilist")
372 (defun ilist-setcar (ilist object)
373 "Set the first element of ILIST to OBJECT.
374 Error if ILIST is empty. Returns OBJECT."
375 (if (ilist-empty-p ilist)
376 (signal 'empty-ilist nil)
377 (setcar ilist object)))
379 (defun ilist-setcdr (ilist newcdr)
380 "Set the `ilist-cdr' of ILIST to NEWCDR.
381 Error if ILIST is empty. Returns NEWCDR."
382 (if (ilist-empty-p ilist)
383 (signal 'empty-ilist nil)
384 (setcdr ilist newcdr)))
389 ;;; iterators.el ends here