code.delx.au - gnu-emacs-elpa/blob - packages/iterators/iterators.el

   1 ;;; iterators.el --- Functions for working with iterators  -*- lexical-binding: t -*-
   2
   3 ;; Copyright (C) 2015 Free Software Foundation, Inc
   4
   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
  10 ;; Version: 0.1
  11 ;; Package-Requires: ((emacs "25"))
  12
  13
  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.
  18
  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.
  23
  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/>.
  26
  27
  28 ;;; Commentary:
  29 ;;
  30 ;; This package extends "generator.el" with higher-level functions.
  31
  32 ;;; Code:
  33
  34
  35 (eval-when-compile (require 'cl-lib))
  36 (require 'generator)
  37
  38
  39 ;;;; Basic stuff
  40
  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)))
  45
  46
  47 ;;;; Special simple iterators
  48
  49 (defun iterator-from-elts (&rest elements)
  50   "Return an iterator generating the ELEMENTS."
  51   (iterator-make (while elements (iter-yield (pop elements)))))
  52
  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
  57 again ad finitum."
  58   (if (null elements)
  59       (iterator-from-elts)
  60     (setcdr (last elements) elements)
  61     (iterator-make (while t (iter-yield (pop elements))))))
  62
  63 (defun iterator--cons (val iterator)
  64   (iterator-make
  65    (iter-yield val)
  66    (iter-yield-from iterator)))
  67
  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
  72 preceding element."
  73   (iterator--cons
  74    value
  75    (iterator-make
  76     (while t (iter-yield (setq value (funcall function value)))))))
  77
  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))
  85          (start (or start 0))
  86          (i start))
  87     (if end
  88         (let ((comp (if (> inc 0) #'< #'>)))
  89           (iterator-make
  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))))))))
  93
  94
  95 ;;;; Operations on iterators, transducers
  96
  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."
 102   (iterator-make
 103    (while t
 104      (let ((el (iter-next iterator)))
 105        (while (not (funcall predicate el))
 106          (setq el (iter-next iterator)))
 107        (iter-yield el)))))
 108
 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))
 112
 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."
 118   (iterator-make
 119    (let (current)
 120      (while (setq current (pop iterators))
 121        (iter-yield-from current)))))
 122
 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."
 128   (iterator-make
 129    (while t (iter-yield (apply function (mapcar #'iter-next iterators))))))
 130
 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."
 135   (iterator-make
 136    (let (el)
 137      (while (funcall predicate (setq el (iter-next iterator)))
 138        (iter-yield el)))))
 139
 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."
 144   (iterator-make
 145    (let (el)
 146      (while (not (funcall predicate (setq el (iter-next iterator))))
 147        (iter-yield el))
 148      (iter-yield el))))
 149
 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)))))
 156
 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
 162
 163   s_1     = init
 164   s_(n+1) = (funcall f s_n  i_n)
 165
 166 as long as i_n exists.
 167
 168 Example: (iterator-scan #'* 1 (iterator-number-range 1))
 169 returns an iterator of the factorials."
 170   (let ((res init))
 171     (iterator--cons
 172      res
 173      (iterator-map (lambda (el) (setq res (funcall function res el)))
 174                    iterator))))
 175
 176
 177 ;;;; Iteration
 178
 179 (defun iterator-flush (iterator)
 180   "Request all elements from ITERATOR, for side effects only."
 181   (condition-case nil
 182       (while t (iter-next iterator))
 183     (iter-end-of-sequence nil)))
 184
 185
 186 ;;;; Processing elements
 187
 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
 191
 192   (iter-last (iterator-scan function init iterator))
 193
 194 would return."
 195   (let ((res init))
 196     (iterator-flush (iterator-map (lambda (el) (setq res (funcall function res el))) iterator))
 197     res))
 198
 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)))
 204
 205 (defun iterator-last (iterator)
 206   "Request all elements from ITERATOR and return the last one."
 207   (let ((el (iter-next iterator)))
 208     (condition-case nil
 209         (while t (setq el (iter-next iterator)))
 210       (iter-end-of-sequence el))))
 211
 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))
 215
 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...)"
 220   (catch 'success
 221     (iterator-flush
 222      (apply #'iterator-map
 223             (lambda (&rest elts) (let (res) (when (setq res (apply predicate elts))
 224                                          (throw 'success res))))
 225             iterators))
 226     nil))
 227
 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)))
 232
 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'.
 239
 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)))
 244     (iterator-reduce
 245      (lambda (x y) (if (< (funcall function x) (funcall function y))  y  x))
 246      first iterator)))
 247
 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))))))
 256
 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))))
 265
 266
 267 ;;;; ILists - "Delayed" lists via iterators
 268
 269 (defconst ilist--last-link-tag 'ilist--last-link-tag)
 270
 271 (defun iterator-to-ilist (iterator)
 272   "Return an ilist using ITERATOR to produce elements."
 273   (cons ilist--last-link-tag iterator))
 274
 275 (defmacro ilist-make (expr)
 276   "Return an ilist calling an iterator using EXPR to produce elements."
 277   `(iterator-to-ilist (iterator-make ,expr)))
 278
 279 (defconst ilist-null
 280   (cons ilist--last-link-tag nil)
 281   "A distinguished empty ilist.")
 282
 283 (defun ilistp (object)
 284   "Return t if OBJECT is an ilist, that is, a cons cell or nil.
 285 Otherwise, return nil."
 286   (listp object))
 287
 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
 294           (condition-case 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)
 299                                   nil))))
 300     (car ilist)))
 301
 302 (defun ilist-empty-p (ilist)
 303   "Return t if ILIST is empty."
 304   (ignore (ilist-car ilist))
 305   (null (cdr ilist)))
 306
 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)))
 311
 312 (defun ilist-cons (el ilist)
 313   "Return a new ilist with EL as `ilist-car' ILIST as `ilist-cdr'."
 314   (cons el ilist))
 315
 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))
 319   ilist)
 320
 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)))
 325
 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
 330 created in ILIST."
 331   (iterator-make
 332    (while (not (ilist-empty-p ilist))
 333      (prog1 (iter-yield (ilist-car ilist))
 334        (cl-callf ilist-cdr ilist)))))
 335
 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."
 339   (iterator-to-ilist
 340    (iterator-map function (ilist-to-iterator ilist))))
 341
 342 (defun ilist (&rest objects)
 343   "Return a newly created ilist with specified arguments as elements."
 344   (nconc objects ilist-null))
 345
 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))
 351
 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."
 355   (let ((elts '()))
 356     (while (not (ilist-empty-p ilist))
 357       (push (ilist-car ilist) elts)
 358       (cl-callf ilist-cdr ilist))
 359     (nreverse elts)))
 360
 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."
 366   (iterator-to-ilist
 367    (apply #'iterator-concatenate
 368           (mapcar #'ilist-to-iterator ilists))))
 369
 370 (define-error 'empty-ilist "Empty ilist")
 371
 372 (defun ilist-setcar (ilist object)
 373   "Set the first element of ILIST to OBJECT.
 374 Error if ILIST is empty.  Return OBJECT."
 375   (if (ilist-empty-p ilist)
 376       (signal 'empty-ilist nil)
 377     (setcar ilist object)))
 378
 379 (defun ilist-setcdr (ilist newcdr)
 380   "Set the `ilist-cdr' of ILIST to NEWCDR.
 381 Error if ILIST is empty.  Return NEWCDR."
 382   (if (ilist-empty-p ilist)
 383       (signal 'empty-ilist nil)
 384     (setcdr ilist newcdr)))
 385
 386
 387 (provide 'iterators)
 388
 389 ;;; iterators.el ends here