From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Michael Heerdegen Newsgroups: gmane.emacs.devel Subject: Re: master f6b5db6: Add support for generators Date: Sat, 21 Mar 2015 06:52:20 +0100 Message-ID: <871tkidhij.fsf@web.de> References: <20150302234252.19883.48595@vcs.savannah.gnu.org> <874mq0z504.fsf@web.de> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: ger.gmane.org 1426917164 24602 80.91.229.3 (21 Mar 2015 05:52:44 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 21 Mar 2015 05:52:44 +0000 (UTC) Cc: Stefan Monnier To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat Mar 21 06:52:37 2015 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1YZCKp-00080n-5M for ged-emacs-devel@m.gmane.org; Sat, 21 Mar 2015 06:52:35 +0100 Original-Received: from localhost ([::1]:46729 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YZCKo-00070u-JU for ged-emacs-devel@m.gmane.org; Sat, 21 Mar 2015 01:52:34 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:38672) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YZCKk-0006zz-Ir for emacs-devel@gnu.org; Sat, 21 Mar 2015 01:52:31 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YZCKg-0001Fh-IK for emacs-devel@gnu.org; Sat, 21 Mar 2015 01:52:30 -0400 Original-Received: from mout.web.de ([212.227.17.12]:51648) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YZCKg-0001FP-7z for emacs-devel@gnu.org; Sat, 21 Mar 2015 01:52:26 -0400 Original-Received: from drachen.dragon ([92.74.177.235]) by smtp.web.de (mrweb103) with ESMTPSA (Nemesis) id 0M0yeJ-1ZNB5W2pjj-00v5lC; Sat, 21 Mar 2015 06:52:22 +0100 In-Reply-To: <874mq0z504.fsf@web.de> (Michael Heerdegen's message of "Thu, 05 Mar 2015 01:01:47 +0100") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.0.50 (gnu/linux) X-Provags-ID: V03:K0:WyQx5qrsQeKJKQfoOUsKFTPnka7G4o+w6tPOxxKR2PCkqaZBMS1 PmRoXYMGDPz3A7/Fc0bwpVF2gt42UdtFjCNd984Ezdj96TLf74ZAw7H3F1TGIOyPuAT3Ie7 a97UZYAqiawxYLshffqNtNATh5p02B3aYJRZJDBXYoJ1mY7GQJ5sqR6sjc53QBQ3/rxxtZ4 8OH2hiOrBcvnUelfyp5ag== X-UI-Out-Filterresults: notjunk:1; X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [generic] X-Received-From: 212.227.17.12 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:184070 Archived-At: --=-=-= Content-Type: text/plain Michael Heerdegen writes: > I would now also like to work on including my higher-level functions if > there are no objections. Ok, this is how the thing now looks like: https://github.com/michael-heerdegen/iterators.el the file is also attached. This is now a library of higher level stuff for the iterator objects created by Daniel's generators that were previously included into Emacs. What I had been named "cache" in the last version - that was a dynamic cache for the elements returned by an iterator implemented as a delayed list based on delayed conses - has been reimplemented and is now named "ilist" - IteratorLIST. These are delayed lists as well, but built from normal conses, that (can) reference an iterator to produce "more elements" on request. I chose this approach because I think it suits much better the nature of Emacs Lisp. You can convert from/to lists and iterators, and some functions to work with ilists are included as well. Dunno yet how useful this stuff is, at least I need it personally. We could put this to Gnu Elpa if Emacs Dev is interested; else, I'll put it on Melpa. Thanks, Michael. --=-=-= Content-Type: application/emacs-lisp Content-Disposition: attachment; filename=iterators.el Content-Transfer-Encoding: quoted-printable ;;; iterators.el --- Functions for working with iterators -*- lexical-bind= ing: t -*- ;; Copyright (C) 2015 Michael Heerdegen ;; Author: Michael Heerdegen ;; Maintainer: Michael Heerdegen ;; Created: Mar 18 2015 ;; Keywords: extensions, elisp ;; Version: 0.1 ;; Package-Requires: ((cl-lib "0")) ;; This file is not part of GNU Emacs. ;; GNU Emacs is free software: you can redistribute it and/or modify ;; it under the terms of the GNU General Public License as published by ;; the Free Software Foundation, either version 3 of the License, or ;; (at your option) any later version. ;; GNU Emacs is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;; GNU General Public License for more details. ;; You should have received a copy of the GNU General Public License ;; along with GNU Emacs. If not, see . ;;; Commentary: ;; ;; This package extends "generator.el" with higher-level functions. ;;; Code: (require 'cl-lib) (require 'generator) ;; Basic stuff (defmacro iterator-make (&rest body) "Create an anonymous iterator. This is equivalent to (funcall (iter-lambda () BODY...))" `(funcall (iter-lambda () ,@body))) ;; Special simple iterators (defun iterator-from-elts (&rest elements) "Return an iterator generating the ELEMENTS." (iterator-make (while elements (iter-yield (pop elements))))) (defun iterator-cycle-elts (&rest elements) "Return an iterator cycling through the ELEMENTS. Unlike `iterator-from-elts', after the last of the ELEMENTS has been generated, the resulting iterator will generate all ELEMENTS again ad finitum." (if (null elements) (iterator-from-elts) (setcdr (last elements) elements) (iterator-make (while t (iter-yield (pop elements)))))) (defun iterator--cons (val iterator) (iterator-make (iter-yield val) (iter-yield-from iterator))) (defun iterator-iterate-function (function value) "Return an iterator of repeated applications of FUNCTION to VALUE. The sequence of returned elements is starting with VALUE. Any successive element will be found by calling FUNCTION on the preceding element." (iterator--cons value (iterator-make (while t (iter-yield (setq value (funcall function value))))))) (defun iterator-number-range (&optional start end inc) "Return an iterator of a number range. START denotes the first number and defaults to 0. The second, optional argument END specifies the upper limit (exclusively). If nil, the returned iterator is infinite. INC is the increment used between the numbers and defaults to 1." (let* ((inc (or inc +1)) (start (or start 0)) (i start)) (if end (let ((comp (if (> inc 0) #'< #'>))) (iterator-make (while (funcall comp i end) (iter-yield (prog1 i (cl-incf i inc)))))) (iterator-make (while t (iter-yield (prog1 i (cl-incf i)))))))) ;; Operations on iterators, transducers (defun iterator-filter (predicate iterator) "Return an iterator filtering ITERATOR with PREDICATE. This new iterator will return elements in the same order as ITERATOR, but only those that fulfill PREDICATE, a function that accepts one argument." (iterator-make (while t (let ((el (iter-next iterator))) (while (not (funcall predicate el)) (setq el (iter-next iterator))) (iter-yield el))))) (defun iterator-delq (elt iterator) "Return an iterator of the elements of ITERATOR not `eq' to ELT." (iterator-filter (lambda (el) (not (eq el elt))) iterator)) (defun iterator-concatenate (&rest iterators) "Concatenate the ITERATORS. Return a new iterator that returns the elements generated by each iterator in ITERATORS, in order. The ITERATORS are each invoked to completion, in order." (iterator-make (let (current) (while (setq current (pop iterators)) (iter-yield-from current))))) (defun iterator-map (function &rest iterators) "Return an iterator mapping FUNCTION across ITERATORS. If there are several ITERATORS, FUNCTION is called with that many arguments. The resulting iterator will produce elements as long as the shortest iterator does." (iterator-make (while t (iter-yield (apply function (mapcar #'iter-next iterators)))))) (defun iterator-take-while (predicate iterator) "Return an iterator representing a \"do-while\" loop. It will invoke ITERATOR to produce elements as long they fulfill PREDICATE and stop then." (iterator-make (let (el) (while (funcall predicate (setq el (iter-next iterator))) (iter-yield el))))) (defun iterator-take-until (predicate iterator) "Return an iterator representing an \"until-do\" loop. It will invoke ITERATOR to produce elements until one fulfills PREDICATE. It will stop after returning this element." (iterator-make (let (el) (while (not (funcall predicate (setq el (iter-next iterator)))) (iter-yield el)) (iter-yield el)))) (defun iterator-take (n iterator) "Return an iterator of the first N elements of ITERATOR. This iterator generates at most the first N elements generated by ITERATOR, in order." (iterator-make (while (>=3D (cl-decf n) 0) (iter-yield (iter-next iterator))))) (defun iterator-scan (function init iterator) "Return an iterator of successive reduced values. If the elements generated by iterator i are i_1, i_2, ..., the elements s_1, s_2, ... of the iterator returned by \(iterator-scan f init i\) are defined recursively by s_1 =3D init s_(n+1) =3D (funcall f s_n i_n) as long as i_n exists. Example: (iterator-scan #'* 1 (iterator-number-range 1)) returns an iterator of the factorials." (let ((res init)) (iterator--cons res (iterator-map (lambda (el) (setq res (funcall function res el))) iterator)))) ;; Iteration (defun iterator-flush (iterator) "Request all elements from ITERATOR, for side effects only." (condition-case nil (while t (iter-next iterator)) (iter-end-of-sequence nil))) ;; Processing elements (defun iterator-reduce (function init iterator) "Reduce two-argument FUNCTION across ITERATOR starting with INIT. This is the same value as the expression (iter-last (iterator-scan function init iterator)) would return." (let ((res init)) (iterator-flush (iterator-map (lambda (el) (setq res (funcall function = res el))) iterator)) res)) (defun iterator-to-list (iterator) "Convert ITERATOR into a list. Run ITERATOR until it runs out of elements and return a list of the generated elements." (nreverse (iterator-reduce (lambda (x y) (cons y x)) () iterator))) (defun iterator-last (iterator) "Request all elements from ITERATOR and return the last one." (let ((el (iter-next iterator))) (condition-case nil (while t (setq el (iter-next iterator))) (iter-end-of-sequence el)))) (defun iterator-count (iterator) "Request all elements from ITERATOR and return their count." (iterator-reduce (lambda (s _el) (1+ s)) 0 iterator)) (defun iterator-some (predicate &rest iterators) "Return non-nil if PREDICATE is true for any element of ITER or ITERs. If so, return the true (non-nil) value returned by PREDICATE. \n(fn PREDICATE ITER...)" (catch 'success (iterator-flush (apply #'iterator-map (lambda (&rest elts) (let (res) (when (setq res (apply predicat= e elts)) (throw 'success res)))) iterators)) nil)) (defun iterator-every (predicate &rest iterators) "Return non-nil if PREDICATE is true for every element of ITER or ITERs. \n(fn PREDICATE ITER...)" (not (apply #'iterator-some (lambda (&rest args) (not (apply predicate ar= gs))) iterators))) (defun iterator-max (iterator &optional function) "Return an element of finite ITERATOR maximizing FUNCTION. Request all elements from ITERATOR and pass them to FUNCTION, a one-argument function that must return a number. Return an element for which FUNCTION was maximal. Raise an error if ITERATOR produced no elements. FUNCTION defaults to `identity'. Example: if ITERATOR is an iterator of lists, this would return a longest generated list: (iterator-max iterator #'length)." (let ((first (iter-next iterator)) (function (or function #'identity))) (iterator-reduce (lambda (x y) (if (< (funcall function x) (funcall function y)) y x)) first iterator))) (defun iterator-min (iterator &optional function) "Return an element of ITERATOR that minimizes FUNCTION. Request all elements from ITERATOR and pass them to FUNCTION, a one-argument function that must return a number. Return an element for which FUNCTION was minimal. Raise an error if ITERATOR produced no elements. FUNCTION defaults to `identity'." (let ((function (or function #'identity))) (iterator-max iterator (lambda (x) (- (funcall function x)))))) (defun iterator-mapconcat (function iterator separator) "Apply FUNCTION to each element of ITERATOR, and concat the results as st= rings. In between of each pair of results, stick in SEPARATOR. This is like `mapconcat', but for iterators." (let ((first (iter-next iterator))) (iterator-reduce (lambda (x y) (concat x separator y)) (funcall function first) (iterator-map function iterator)))) ;;; ILists - "Delayed" lists via iterators (defconst ilist--last-link-tag 'ilist--last-link-tag) (defun iterator-to-ilist (iterator) "Return an ilist using ITERATOR to produce elements." (cons ilist--last-link-tag iterator)) (defmacro ilist-make (expr) "Return an ilist calling an iterator using EXPR to produce elements." `(iterator-to-ilist (iterator-make ,expr))) (defconst ilist-null (cons ilist--last-link-tag nil) "A distinguished empty ilist.") (defun ilistp (object) "Return t if OBJECT is an ilist, that is, a cons cell or nil. Otherwise, return nil." (listp object)) (defun ilist-car (ilist) "Return the first element of ILIST. Error if arg is not nil and not a cons cell." (if (eq (car ilist) ilist--last-link-tag) (let ((iterator (cdr ilist)) new-el) (if (null iterator) nil (condition-case nil (prog1 (setq new-el (iter-next iterator)) (setcar ilist new-el) (setcdr ilist (cons ilist--last-link-tag iterator))) (iter-end-of-sequence (setcdr ilist nil) nil)))) (car ilist))) (defun ilist-empty-p (ilist) "Return t if ILIST is empty." (ignore (ilist-car ilist)) (null (cdr ilist))) (defun ilist-cdr (ilist) "Return the `ilist-cdr' of ILIST. Error if arg is not nil and not a cons cell." (if (ilist-empty-p ilist) ilist (cdr ilist))) (defun ilist-cons (el ilist) "Return a new ilist with EL as `ilist-car' ILIST as `ilist-cdr'." (cons el ilist)) (defun ilist-nthcdr (n ilist) "Take `ilist-cdr' N times on ILIST, return the result." (cl-dotimes (_ n) (cl-callf ilist-cdr ilist)) ilist) (defun ilist-nth (n ilist) "Return the Nth element of ILIST. N counts from zero. If ILIST is not that long, nil is returned." (ilist-car (ilist-nthcdr n ilist))) (defun ilist-to-iterator (ilist) "Return an iterator generating the elements of ILIST. The structure of ILIST is updated as side effect if new elements are generated by the returned iterator which were not yet created in ILIST." (iterator-make (while (not (ilist-empty-p ilist)) (prog1 (iter-yield (ilist-car ilist)) (cl-callf ilist-cdr ilist))))) (defun ilist-mapcar (function ilist) "Apply FUNCTION to each element of ILIST, and make an ilist of the result= s. The result is an ilist just as long as ILIST." (iterator-to-ilist (iterator-map function (ilist-to-iterator ilist)))) (defun ilist (&rest objects) "Return a newly created ilist with specified arguments as elements." (nconc objects ilist-null)) (defun list-to-ilist (list) "Convert LIST into an ilist. The result is an ilist containing the same elements as LIST in the same order. This is a destructive operation modifying LIST." (nconc list ilist-null)) (defun ilist-to-list (ilist) "Return a list of all elements of ILIST. All elements of ILIST are generated as side effect." (let ((elts '())) (while (not (ilist-empty-p ilist)) (push (ilist-car ilist) elts) (cl-callf ilist-cdr ilist)) (nreverse elts))) (defun ilist-concatenate (&rest ilists) "Concatenate the ILISTS into a new ilist and return the result. New elements in the argument ilists are generated when being referenced in the concatenated ilist. Apart from that, the argument ilists are not modified." (iterator-to-ilist (apply #'iterator-concatenate (mapcar #'ilist-to-iterator ilists)))) (define-error 'empty-ilist "Empty ilist") (defun ilist-setcar (ilist object) "Set the first element of ILIST to OBJECT. Error if ILIST is empty. Returns OBJECT." (if (ilist-empty-p ilist) (signal 'empty-ilist nil) (setcar ilist object))) (defun ilist-setcdr (ilist newcdr) "Set the `ilist-cdr' of ILIST to NEWCDR. Error if ILIST is empty. Returns NEWCDR." (if (ilist-empty-p ilist) (signal 'empty-ilist nil) (setcdr ilist newcdr))) (provide 'iterators) ;;; iterators.el ends here --=-=-=--