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 (iter-defun iterator-of-directory-files-1 (directory &optional match nosort recurse follow-links)
  95   "Helper for `iterator-of-directory-files'."
  96   (when (file-accessible-directory-p directory)
  97     (let ((files (directory-files directory t match nosort))  file)
  98       (while (setq file (pop files))
  99         (cond
 100          ((not (file-directory-p file))
 101           (iter-yield file))
 102          ((member (file-name-nondirectory (directory-file-name file))
 103                   '("." "..")))
 104          (t
 105           (iter-yield file)
 106           (when (and (or follow-links (not (file-symlink-p file)))
 107                      (if (functionp recurse) (funcall recurse file) recurse))
 108             (iter-yield-from (iterator-of-directory-files-1
 109                               file match nosort recurse follow-links)))))))))
 110
 111 (defun iterator-of-directory-files (directory &optional full match nosort recurse follow-links)
 112   "Return an iterator of names of files in DIRECTORY.
 113 Don't include files named \".\" or \"..\".  The arguments FULL,
 114 MATCH and NOSORT are like in `directory-files'.
 115
 116 Optional argument RECURSE non-nil means recurse on
 117 subdirectories.  If RECURSE is a function, it should be a
 118 predicate accepting one argument, an absolute file name of a
 119 directory, and return non-nil when the returned iterator should
 120 recurse into that directory.  Any other non-nil value means
 121 recurse into every readable subdirectory.
 122
 123 Even with recurse non-nil, don't descent into directories by
 124 following symlinks unless FOLLOW-LINKS is non-nil."
 125   (iterator-map
 126    (lambda (file) (if full file (file-relative-name file directory)))
 127    (iterator-of-directory-files-1 directory match nosort recurse follow-links)))
 128
 129
 130 ;;;; Operations on iterators, transducers
 131
 132 (defun iterator-filter (predicate iterator)
 133   "Return an iterator filtering ITERATOR with PREDICATE.
 134 This new iterator will return elements in the same order as
 135 ITERATOR, but only those that fulfill PREDICATE, a function that
 136 accepts one argument."
 137   (iterator-make
 138    (while t
 139      (let ((el (iter-next iterator)))
 140        (while (not (funcall predicate el))
 141          (setq el (iter-next iterator)))
 142        (iter-yield el)))))
 143
 144 (defun iterator-delq (elt iterator)
 145   "Return an iterator of the elements of ITERATOR not `eq' to ELT."
 146   (iterator-filter (lambda (el) (not (eq el elt)))  iterator))
 147
 148 (defun iterator-concatenate (&rest iterators)
 149   "Concatenate the ITERATORS.
 150 Return a new iterator that returns the elements generated by
 151 each iterator in ITERATORS, in order.  The ITERATORS are each
 152 invoked to completion, in order."
 153   (iterator-make
 154    (let (current)
 155      (while (setq current (pop iterators))
 156        (iter-yield-from current)))))
 157
 158 (defun iterator-map (function &rest iterators)
 159   "Return an iterator mapping FUNCTION across ITERATORS.
 160 If there are several ITERATORS, FUNCTION is called with that
 161 many arguments.  The resulting iterator will produce elements as
 162 long as the shortest iterator does."
 163   (iterator-make
 164    (while t (iter-yield (apply function (mapcar #'iter-next iterators))))))
 165
 166 (defun iterator-take-while (predicate iterator)
 167   "Return an iterator representing a \"do-while\" loop.
 168 It will invoke ITERATOR to produce elements as long they fulfill
 169 PREDICATE and stop then."
 170   (iterator-make
 171    (let (el)
 172      (while (funcall predicate (setq el (iter-next iterator)))
 173        (iter-yield el)))))
 174
 175 (defun iterator-take-until (predicate iterator)
 176   "Return an iterator representing an \"until-do\" loop.
 177 It will invoke ITERATOR to produce elements until one fulfills
 178 PREDICATE.  It will stop after returning this element."
 179   (iterator-make
 180    (let (el)
 181      (while (not (funcall predicate (setq el (iter-next iterator))))
 182        (iter-yield el))
 183      (iter-yield el))))
 184
 185 (defun iterator-take (n iterator)
 186   "Return an iterator of the first N elements of ITERATOR.
 187 This iterator generates at most the first N elements generated
 188 by ITERATOR, in order."
 189   (iterator-make (while (>= (cl-decf n) 0)
 190                    (iter-yield (iter-next iterator)))))
 191
 192 (defun iterator-scan (function init iterator)
 193   "Return an iterator of successive reduced values.
 194 If the elements generated by iterator i are i_1, i_2, ..., the
 195 elements s_1, s_2, ... of the iterator returned by
 196 \(iterator-scan f init i\) are defined recursively by
 197
 198   s_1     = init
 199   s_(n+1) = (funcall f s_n  i_n)
 200
 201 as long as i_n exists.
 202
 203 Example: (iterator-scan #'* 1 (iterator-number-range 1))
 204 returns an iterator of the factorials."
 205   (let ((res init))
 206     (iterator--cons
 207      res
 208      (iterator-map (lambda (el) (setq res (funcall function res el)))
 209                    iterator))))
 210
 211
 212 ;;;; Iteration
 213
 214 (defun iterator-flush (iterator)
 215   "Request all elements from ITERATOR, for side effects only."
 216   (condition-case nil
 217       (while t (iter-next iterator))
 218     (iter-end-of-sequence nil)))
 219
 220
 221 ;;;; Processing elements
 222
 223 (defun iterator-reduce (function init iterator)
 224   "Reduce two-argument FUNCTION across ITERATOR starting with INIT.
 225 This is the same value as the expression
 226
 227   (iter-last (iterator-scan function init iterator))
 228
 229 would return."
 230   (let ((res init))
 231     (iterator-flush (iterator-map (lambda (el) (setq res (funcall function res el))) iterator))
 232     res))
 233
 234 (defun iterator-to-list (iterator)
 235   "Convert ITERATOR into a list.
 236 Run ITERATOR until it runs out of elements and return a list of
 237 the generated elements."
 238   (nreverse (iterator-reduce (lambda (x y) (cons y x)) () iterator)))
 239
 240 (defun iterator-last (iterator)
 241   "Request all elements from ITERATOR and return the last one."
 242   (let ((el (iter-next iterator)))
 243     (condition-case nil
 244         (while t (setq el (iter-next iterator)))
 245       (iter-end-of-sequence el))))
 246
 247 (defun iterator-count (iterator)
 248   "Request all elements from ITERATOR and return their count."
 249   (iterator-reduce (lambda (s _el) (1+ s)) 0 iterator))
 250
 251 (defun iterator-some (predicate &rest iterators)
 252   "Return non-nil if PREDICATE is true for any element of ITER or ITERs.
 253 If so, return the true (non-nil) value returned by PREDICATE.
 254 \n(fn PREDICATE ITER...)"
 255   (catch 'success
 256     (iterator-flush
 257      (apply #'iterator-map
 258             (lambda (&rest elts) (let (res) (when (setq res (apply predicate elts))
 259                                          (throw 'success res))))
 260             iterators))
 261     nil))
 262
 263 (defun iterator-every (predicate &rest iterators)
 264   "Return non-nil if PREDICATE is true for every element of ITER or ITERs.
 265 \n(fn PREDICATE ITER...)"
 266   (not (apply #'iterator-some (lambda (&rest args) (not (apply predicate args))) iterators)))
 267
 268 (defun iterator-max (iterator &optional function)
 269   "Return an element of finite ITERATOR maximizing FUNCTION.
 270 Request all elements from ITERATOR and pass them to FUNCTION, a
 271 one-argument function that must return a number.  Return an
 272 element for which FUNCTION was maximal.  Raise an error if
 273 ITERATOR produced no elements.  FUNCTION defaults to `identity'.
 274
 275 Example: if ITERATOR is an iterator of lists, this would return
 276 a longest generated list: (iterator-max iterator #'length)."
 277   (let ((first (iter-next iterator))
 278         (function (or function #'identity)))
 279     (iterator-reduce
 280      (lambda (x y) (if (< (funcall function x) (funcall function y))  y  x))
 281      first iterator)))
 282
 283 (defun iterator-min (iterator &optional function)
 284   "Return an element of ITERATOR that minimizes FUNCTION.
 285 Request all elements from ITERATOR and pass them to FUNCTION, a
 286 one-argument function that must return a number.  Return an
 287 element for which FUNCTION was minimal.  Raise an error if
 288 ITERATOR produced no elements.  FUNCTION defaults to `identity'."
 289   (let ((function (or function #'identity)))
 290     (iterator-max iterator (lambda (x) (- (funcall function x))))))
 291
 292 (defun iterator-mapconcat (function iterator separator)
 293   "Apply FUNCTION to each element of ITERATOR, and concat the results as strings.
 294 In between of each pair of results, stick in SEPARATOR.  This is
 295 like `mapconcat', but for iterators."
 296   (let ((first (iter-next iterator)))
 297     (iterator-reduce (lambda (x y) (concat x separator y))
 298                      (funcall function first)
 299                      (iterator-map function iterator))))
 300
 301
 302 ;;;; ILists - "Delayed" lists via iterators
 303
 304 (defconst ilist--last-link-tag 'ilist--last-link-tag)
 305
 306 (defun iterator-to-ilist (iterator)
 307   "Return an ilist using ITERATOR to produce elements."
 308   (cons ilist--last-link-tag iterator))
 309
 310 (defmacro ilist-make (expr)
 311   "Return an ilist calling an iterator using EXPR to produce elements."
 312   `(iterator-to-ilist (iterator-make ,expr)))
 313
 314 (defconst ilist-null
 315   (cons ilist--last-link-tag nil)
 316   "A distinguished empty ilist.")
 317
 318 (defun ilistp (object)
 319   "Return t if OBJECT is an ilist, that is, a cons cell or nil.
 320 Otherwise, return nil."
 321   (listp object))
 322
 323 (defun ilist-car (ilist)
 324   "Return the first element of ILIST.
 325 Error if arg is not nil and not a cons cell."
 326   (if (eq (car ilist) ilist--last-link-tag)
 327       (let ((iterator (cdr ilist)) new-el)
 328         (if (null iterator) nil
 329           (condition-case nil
 330               (prog1 (setq new-el (iter-next iterator))
 331                 (setcar ilist new-el)
 332                 (setcdr ilist (cons ilist--last-link-tag iterator)))
 333             (iter-end-of-sequence (setcdr ilist nil)
 334                                   nil))))
 335     (car ilist)))
 336
 337 (defun ilist-empty-p (ilist)
 338   "Return t if ILIST is empty."
 339   (ignore (ilist-car ilist))
 340   (null (cdr ilist)))
 341
 342 (defun ilist-cdr (ilist)
 343   "Return the `ilist-cdr' of ILIST.
 344 Error if arg is not nil and not a cons cell."
 345   (if (ilist-empty-p ilist) ilist (cdr ilist)))
 346
 347 (defun ilist-cons (el ilist)
 348   "Return a new ilist with EL as `ilist-car' ILIST as `ilist-cdr'."
 349   (cons el ilist))
 350
 351 (defun ilist-nthcdr (n ilist)
 352   "Take `ilist-cdr' N times on ILIST, return the result."
 353   (cl-dotimes (_ n) (cl-callf ilist-cdr ilist))
 354   ilist)
 355
 356 (defun ilist-nth (n ilist)
 357   "Return the Nth element of ILIST.
 358 N counts from zero.  If ILIST is not that long, nil is returned."
 359   (ilist-car (ilist-nthcdr n ilist)))
 360
 361 (defun ilist-to-iterator (ilist)
 362   "Return an iterator generating the elements of ILIST.
 363 The structure of ILIST is updated as side effect if new elements
 364 are generated by the returned iterator which were not yet
 365 created in ILIST."
 366   (iterator-make
 367    (while (not (ilist-empty-p ilist))
 368      (prog1 (iter-yield (ilist-car ilist))
 369        (cl-callf ilist-cdr ilist)))))
 370
 371 (defun ilist-mapcar (function ilist)
 372   "Apply FUNCTION to each element of ILIST, and make an ilist of the results.
 373 The result is an ilist just as long as ILIST."
 374   (iterator-to-ilist
 375    (iterator-map function (ilist-to-iterator ilist))))
 376
 377 (defun ilist (&rest objects)
 378   "Return a newly created ilist with specified arguments as elements."
 379   (nconc objects ilist-null))
 380
 381 (defun list-to-ilist (list)
 382   "Convert LIST into an ilist.
 383 The result is an ilist containing the same elements as LIST in
 384 the same order.  This is a destructive operation modifying LIST."
 385   (nconc list ilist-null))
 386
 387 (defun ilist-to-list (ilist)
 388   "Return a list of all elements of ILIST.
 389 All elements of ILIST are generated as side effect."
 390   (let ((elts '()))
 391     (while (not (ilist-empty-p ilist))
 392       (push (ilist-car ilist) elts)
 393       (cl-callf ilist-cdr ilist))
 394     (nreverse elts)))
 395
 396 (defun ilist-concatenate (&rest ilists)
 397   "Concatenate the ILISTS into a new ilist and return the result.
 398 New elements in the argument ilists are generated when being
 399 referenced in the concatenated ilist.  Apart from that, the
 400 argument ilists are not modified."
 401   (iterator-to-ilist
 402    (apply #'iterator-concatenate
 403           (mapcar #'ilist-to-iterator ilists))))
 404
 405 (define-error 'empty-ilist "Empty ilist")
 406
 407 (defun ilist-setcar (ilist object)
 408   "Set the first element of ILIST to OBJECT.
 409 Error if ILIST is empty.  Return OBJECT."
 410   (if (ilist-empty-p ilist)
 411       (signal 'empty-ilist nil)
 412     (setcar ilist object)))
 413
 414 (defun ilist-setcdr (ilist newcdr)
 415   "Set the `ilist-cdr' of ILIST to NEWCDR.
 416 Error if ILIST is empty.  Return NEWCDR."
 417   (if (ilist-empty-p ilist)
 418       (signal 'empty-ilist nil)
 419     (setcdr ilist newcdr)))
 420
 421
 422 (provide 'iterators)
 423
 424 ;;; iterators.el ends here