From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Michael Heerdegen Newsgroups: gmane.emacs.devel Subject: Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations Date: Fri, 21 Apr 2017 04:34:27 +0200 Message-ID: <87pog6lc98.fsf@drachen> References: <87twhbmwbx.fsf@web.de> <87mvmuxuyo.fsf@web.de> <8760tixi99.fsf@web.de> <87twh1kpem.fsf@web.de> <87y42r4d3a.fsf@web.de> <878tug9eh3.fsf@web.de> <87a8es6dcq.fsf@web.de> <87bmz7517d.fsf@web.de> <87shmw76cm.fsf@drachen> <8737evltxs.fsf@petton.fr> <87efyf1ezj.fsf@drachen> <87mvcmk3en.fsf@drachen> <877f3iq2rp.fsf@petton.fr> <87o9wtb5n6.fsf@drachen> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: blaine.gmane.org 1492742124 6386 195.159.176.226 (21 Apr 2017 02:35:24 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 21 Apr 2017 02:35:24 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux) Cc: Emacs developers To: Nicolas Petton Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Apr 21 04:35:17 2017 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1d1OPk-0001Ua-TY for ged-emacs-devel@m.gmane.org; Fri, 21 Apr 2017 04:35:17 +0200 Original-Received: from localhost ([::1]:56792 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d1OPq-0001fh-JD for ged-emacs-devel@m.gmane.org; Thu, 20 Apr 2017 22:35:22 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:46022) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d1OP9-0001fZ-Se for emacs-devel@gnu.org; Thu, 20 Apr 2017 22:34:41 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1d1OP6-0004q9-Oy for emacs-devel@gnu.org; Thu, 20 Apr 2017 22:34:39 -0400 Original-Received: from mout.web.de ([212.227.15.4]:64019) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1d1OP6-0004o2-Dm for emacs-devel@gnu.org; Thu, 20 Apr 2017 22:34:36 -0400 Original-Received: from drachen.dragon ([92.208.180.93]) by smtp.web.de (mrweb002 [213.165.67.108]) with ESMTPSA (Nemesis) id 0M2us2-1cCJ9E0agA-00sbpL; Fri, 21 Apr 2017 04:34:22 +0200 In-Reply-To: <87o9wtb5n6.fsf@drachen> (Michael Heerdegen's message of "Wed, 22 Mar 2017 18:09:01 +0100") X-Provags-ID: V03:K0:zenTiQCV0QMMUimDnd6LmGtonmk4I68i4NCjfcJvBf4lqDdzAkG wau7SaIT7YPlfArvXQjNjj4fl75i5ZZVSs6kNwJM1LyRthXL7csFJNZVagcW8aecycOAvgV 49TtQGVoAYeUmsO2pHZAV5wad2Sf2ml2JPjZxJ64F5Hljng59zc5HW1PCLUaylzQrf5D/MX hE7JOAJ03l92sksZQC2Mg== X-UI-Out-Filterresults: notjunk:1;V01:K0:f6VeHnsN3pY=:Eu5kimhuUAm0S+Mou1W449 zTLixOU0Mu/HJbXjeJN+n5A1O9Qs8XpnOOJi1N2Cs8HAX/xBNUe2JUW9B4Rihilp5pIHz5qk2 wsbI0hXTjVRmUpUfa91imFp28o3yZZwXWgWBTncQbHbTc0ue+SL3+JL+bZq28OfYSRAK5xsri hZ4s61hrRV+E/lhGUVHdUf75QNYmrLvbJoy5FEh8Rv1Vnij6tVl8L10UdErYH/8fOEHBi0pCA eWIIsZ6/bdKpOi7K7Pp0HL5QWg5w/RxSodxxgpXtenHF3dbLwAJBFSgvZ/tuNi0dbx31Hr6DX KD1KdmYj/KfQVtTawx/VKFiuvuGdXacYzUfkQkvUCfQ5VQkZ9i8o35Ofu9dJiRmhWzyx2R0nX tlwmw9feqbv92cAsP2//2eQxnLbF2vNKaALMZN5rzhK7aEJjlLUYgKUBHyRPSojFgZe65xK2j gjhxELqAK4qSGGky3cqk0VRsDWlXqI8yH7N1vwMfD9E/R3UHv5+roCbq9gAsuPOljTGfYp1c7 1po2Ez0s3SqbiukDv2qVEK29dqxWxSSSgoyC62K3LoH25oS5ZfIjnK+4dLwgkFtjwSATb7TMN c+crw64uKDAviW4613UOaI8gBCTWSVCl8hc3BYqhRbHHUefaT/xGJqV/Bg4BsTcHp2yHo6dyl 2f5I97iore4RoLAabdxlAi0Sa2zsZN0xk4SSX6pYop8AdF6Rnvd+sWHmOZgxihh5f9f2Z8+cu Rg41mqV0hqgl5rILvzL9agCMCTLjaovaxcf5GSHRi1kJgJpCFNFdw7HeNIo= X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 212.227.15.4 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 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" Xref: news.gmane.org gmane.emacs.devel:214169 Archived-At: --=-=-= Content-Type: text/plain Michael Heerdegen writes: > But we still want to add the new file to the "stream" package - correct? Ok, find the final patch I intend to install attached. Shall I bump the version of the stream package as well? Regards, Michael. --=-=-= Content-Type: text/x-diff Content-Disposition: attachment; filename=0001-Add-file-stream-x.el-to-the-stream-package.patch >From 2c073c2aa3c2373c5a5f71d8565b79732e4a6a87 Mon Sep 17 00:00:00 2001 From: Michael Heerdegen Date: Fri, 21 Apr 2017 04:14:15 +0200 Subject: [PATCH] Add file "stream-x.el" to the stream package --- packages/stream/stream-x.el | 150 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 150 insertions(+) create mode 100644 packages/stream/stream-x.el diff --git a/packages/stream/stream-x.el b/packages/stream/stream-x.el new file mode 100644 index 000000000..2f97102ba --- /dev/null +++ b/packages/stream/stream-x.el @@ -0,0 +1,150 @@ +;;; stream-x.el --- Additional functions for working with streams -*- lexical-binding: t -*- + +;; Copyright (C) 2017 Free Software Foundation, Inc + +;; Author: Michael Heerdegen +;; Maintainer: Michael Heerdegen +;; Created: 2017_03_22 +;; Keywords: stream, laziness, sequences + + +;; 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 file contains additional functions for working with streams. + + +;;; Code: + +(require 'stream) + + +(defun stream-substream-before (stream rest) + "Return a stream of the elements of STREAM before REST. + +REST is a rest of STREAM: it must either be `eq' to STREAM or to +one of the subsequent calls of `stream-rest' on STREAM. The +return value is a newly created stream containing the first +elements of STREAM with REST cut off. + +When REST appears multiple times as a rest of STREAM, a stream +with the minimal number of elements is returned." + (stream-make + (if (eq stream rest) + nil + (cons (stream-first stream) + (stream-substream-before (stream-rest stream) rest))))) + +(defun stream-divide-with-get-rest-fun (stream get-rest-fun) + "Divide STREAM into two parts according to GET-REST-FUN. + +The return value is a list (S R) where R is the result of +(funcall get-rest-fun STREAM) and S a stream of minimal length so +that (stream-append S R) is equivalent to STREAM. + +Calling GET-REST-FUN on STREAM must be `eq' to one of +STREAM, (stream-rest STREAM), (stream-rest (stream-rest STREAM)), +..." + (let ((rest (funcall get-rest-fun stream))) + (list (stream-substream-before stream rest) rest))) + +(defun stream-divide (stream predicate) + "Divide STREAM between the first pair of elements for that PREDICATE fails. + +When STREAM generates the elements S_1, S_2, ..., call +(PREDICATE S_i, S_i+1) for i=1,2,... until the first index i=k is +found so that (funcall PREDICATE S_k S_k+1) returns nil. + +The return value is a list of two streams (HEAD REST) where +HEAD generates the elements S_1, ... S_k and REST is the rest of STREAM +generating the remaining elements S_k+1, ... + +Example: + + (mapcar #'seq-into-sequence + (stream-divide + (stream (list 1 2 3 5 6 7 9 10 11 23)) + (lambda (this next) (< (- next this) 2)))) +==> ((1 2 3) + (5 6 7 9 10 11 23)) + + +If STREAM is finite and no index k with (funcall PREDICATE S_k S_k+1) ==> +nil is found, return (STREAM E) where E is an empty stream. When +STREAM is infinite and no such index is found, this function will not +terminate. + +See `stream-divide-with-get-rest-fun' for a generalization of this function." + (stream-divide-with-get-rest-fun stream (stream-divide--get-rest-fun predicate))) + +(defun stream-divide--get-rest-fun (pred) + (lambda (s) + (unless (stream-empty-p s) + (while (let ((this (stream-pop s))) + (unless (stream-empty-p s) + (funcall pred this (stream-first s)))))) + s)) + +(defun stream-partition (stream predicate) + "Partition STREAM into bunches where PREDICATE returns non-nil for subsequent elements. + +The return value is a stream S: S_1, S_2, ... of streams S_i of +maximal length so that (stream-concatenate S) is equivalent to STREAM +and for any pair of subsequent elements E, F in any S_i +(PREDICATE E F) evals to a non-nil value. + +Often, but not necessarily, PREDICATE is an equivalence predicate. + +Example: + + (seq-into-sequence + (seq-map #'seq-into-sequence + (stream-partition + (stream (list 1 2 3 5 6 7 9 10 15 23)) + (lambda (x y) (< (- y x) 2))))) + ==> ((1 2 3) + (5 6 7) + (9 10) + (15) + (23)) + +See `stream-partition-with-get-rest-fun' for a generalization of this function." + (stream-partition-with-get-rest-fun stream (stream-divide--get-rest-fun predicate))) + +(defun stream-partition-with-get-rest-fun (stream get-rest-fun) + "Call `stream-divide-with-get-rest-fun' on stream ad finitum. +The return value is a (not necessarily finite) stream S of +streams S_i where (stream-concatenate S) is equivalent to STREAM, + + (S_1 R_1) := (stream-divide-with-get-rest-fun STREAM get-rest-fun) + +and + + (S_i+1 R_i+1) := (stream-divide-with-get-rest-fun R_i get-rest-fun) + +as long as R_i is not empty." + (stream-make + (if (stream-empty-p stream) nil + (let ((divided (stream-divide-with-get-rest-fun stream get-rest-fun))) + (cons (car divided) + (stream-partition-with-get-rest-fun (cadr divided) get-rest-fun)))))) + + +(provide 'stream-x) + +;;; stream-x.el ends here -- 2.11.0 --=-=-=--