[PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Hello,

here is a patch that adds some missing stream operations.


---
 packages/stream/stream.el             | 59 +++++++++++++++++++++++++++++++++++
 packages/stream/tests/stream-tests.el | 32 +++++++++++++++++++
 2 files changed, 91 insertions(+)

diff --git a/packages/stream/stream.el b/packages/stream/stream.el
index 22cecac..7728338 100644
--- a/packages/stream/stream.el
+++ b/packages/stream/stream.el
@@ -333,6 +333,65 @@ calling this function."
 (cl-defmethod seq-copy ((stream stream))
   "Return a shallow copy of STREAM."
   (stream-delay stream))
+\f
+
+;;; More stream operations
+
+(defun stream-scan (function init stream)
+  "Return a stream of successive reduced values for STREAM.
+
+If the elements of a stream s are s_1, s_2, ..., the elements
+S_1, S_2, ... of the stream returned by \(stream-scan f init s\)
+are defined recursively by
+
+  S_1     = init
+  S_(n+1) = (funcall f S_n s_n)
+
+as long as s_n exists.
+
+Example:
+
+   (stream-scan #'* 1 (stream-range 1))
+
+returns a stream of the factorials."
+  (let ((res init))
+    (stream-cons
+     res
+     (seq-map (lambda (el) (setq res (funcall function res el)))
+              stream))))
+
+(defun stream-flush (stream)
+  "Request all elements from STREAM in order for side effects only."
+  (while (not (stream-empty-p stream))
+    (cl-callf stream-rest stream)))
+
+(defun stream-iterate-function (function value)
+  "Return a stream of repeated applications of FUNCTION to VALUE.
+The returned stream starts with VALUE.  Any successive element
+will be found by calling FUNCTION on the preceding element."
+  (stream-cons
+   value
+   (stream-iterate-function function (funcall function value))))
+
+(defun stream-reduce (function init stream)
+  "Reduce two-argument FUNCTION across STREAM starting with INIT."
+  (let ((res init))
+    (stream-flush (seq-map (lambda (el) (setq res (funcall function res el))) stream))
+    res))
+
+(defun stream-concatenate (stream-of-streams)
+  "Concatenate all streams in STREAM-OF-STREAMS and return the result.
+All elements in STREAM-OF-STREAMS must be streams.  The result is
+a stream."
+  (stream-reduce #'stream-append (stream-empty) stream-of-streams))
+
+(defun stream-mapconcat (function stream separator)
+  "Apply FUNCTION to each element of STREAM and concat the results as strings.
+In between of each pair of results, stick in SEPARATOR.  This is
+like `mapconcat', but for streams."
+  (if (stream-empty-p stream) ""
+    (let ((mapped (seq-map function stream)))
+      (stream-reduce (lambda (x y) (concat x separator y)) (stream-first mapped) (stream-rest mapped)))))
 
 (defun stream-of-directory-files-1 (directory &optional nosort recurse follow-links)
   "Helper for `stream-of-directory-files'."
diff --git a/packages/stream/tests/stream-tests.el b/packages/stream/tests/stream-tests.el
index 23a54b5..360a405 100644
--- a/packages/stream/tests/stream-tests.el
+++ b/packages/stream/tests/stream-tests.el
@@ -242,5 +242,37 @@
     (should (= 2 (stream-first str)))
     (should (null (stream-pop stream-empty)))))
 
+(ert-deftest stream-scan-test ()
+  (should (eq (seq-elt (stream-scan #'* 1 (stream-range 1)) 4) 24)))
+
+(ert-deftest stream-flush-test ()
+  (should (let* ((times 0)
+                 (count (lambda () (cl-incf times))))
+            (letrec ((make-test-stream (lambda () (stream-cons (progn (funcall count) nil)
+                                                          (funcall make-test-stream)))))
+              (stream-flush (seq-take (funcall make-test-stream) 5))
+              (eq times 5)))))
+
+(ert-deftest stream-iterate-function-test ()
+  (should (equal (list 0 1 2) (seq-into-sequence (seq-take (stream-iterate-function #'1+ 0) 3)))))
+
+(ert-deftest stream-reduce ()
+  (should (eq (stream-reduce #'* 1 (seq-take (stream-range 1) 4)) 24)))
+
+(ert-deftest stream-concatenate-test ()
+  (should (equal (seq-into-sequence
+                  (stream-concatenate
+                   (stream (list (stream (list 1 2 3))
+                                 (stream (list))
+                                 (stream (list 4))
+                                 (stream (list 5 6 7 8 9))))))
+                 (list 1 2 3 4 5 6 7 8 9))))
+
+(ert-deftest stream-mapconcat-test ()
+  (should (equal (stream-mapconcat #'capitalize (stream (list))             ",") ""))
+  (should (equal (stream-mapconcat #'capitalize (stream (list "a"))         ",") "A"))
+  (should (equal (stream-mapconcat #'capitalize (stream (list "a" "b"))     ",") "A,B"))
+  (should (equal (stream-mapconcat #'capitalize (stream (list "a" "b" "c")) ",") "A,B,C")))
+
 (provide 'stream-tests)
 ;;; stream-tests.el ends here
-- 
2.8.1



Thanks,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

[-- Attachment #1: Type: text/plain, Size: 201 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> here is a patch that adds some missing stream operations.

Resending the patch as attachment (probably the preferable way).


Thanks,

Michael.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-some-more-basic-stream-operations.patch --]
[-- Type: text/x-diff, Size: 4839 bytes --]

From 60ae524edf7fb39791f50582a213c8601bbfb1be Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
Date: Thu, 2 Jun 2016 02:42:43 +0200
Subject: [PATCH] Add some more basic stream operations

---
 packages/stream/stream.el             | 59 +++++++++++++++++++++++++++++++++++
 packages/stream/tests/stream-tests.el | 32 +++++++++++++++++++
 2 files changed, 91 insertions(+)

diff --git a/packages/stream/stream.el b/packages/stream/stream.el
index 22cecac..7728338 100644
--- a/packages/stream/stream.el
+++ b/packages/stream/stream.el
@@ -333,6 +333,65 @@ calling this function."
 (cl-defmethod seq-copy ((stream stream))
   "Return a shallow copy of STREAM."
   (stream-delay stream))
+\f
+
+;;; More stream operations
+
+(defun stream-scan (function init stream)
+  "Return a stream of successive reduced values for STREAM.
+
+If the elements of a stream s are s_1, s_2, ..., the elements
+S_1, S_2, ... of the stream returned by \(stream-scan f init s\)
+are defined recursively by
+
+  S_1     = init
+  S_(n+1) = (funcall f S_n s_n)
+
+as long as s_n exists.
+
+Example:
+
+   (stream-scan #'* 1 (stream-range 1))
+
+returns a stream of the factorials."
+  (let ((res init))
+    (stream-cons
+     res
+     (seq-map (lambda (el) (setq res (funcall function res el)))
+              stream))))
+
+(defun stream-flush (stream)
+  "Request all elements from STREAM in order for side effects only."
+  (while (not (stream-empty-p stream))
+    (cl-callf stream-rest stream)))
+
+(defun stream-iterate-function (function value)
+  "Return a stream of repeated applications of FUNCTION to VALUE.
+The returned stream starts with VALUE.  Any successive element
+will be found by calling FUNCTION on the preceding element."
+  (stream-cons
+   value
+   (stream-iterate-function function (funcall function value))))
+
+(defun stream-reduce (function init stream)
+  "Reduce two-argument FUNCTION across STREAM starting with INIT."
+  (let ((res init))
+    (stream-flush (seq-map (lambda (el) (setq res (funcall function res el))) stream))
+    res))
+
+(defun stream-concatenate (stream-of-streams)
+  "Concatenate all streams in STREAM-OF-STREAMS and return the result.
+All elements in STREAM-OF-STREAMS must be streams.  The result is
+a stream."
+  (stream-reduce #'stream-append (stream-empty) stream-of-streams))
+
+(defun stream-mapconcat (function stream separator)
+  "Apply FUNCTION to each element of STREAM and concat the results as strings.
+In between of each pair of results, stick in SEPARATOR.  This is
+like `mapconcat', but for streams."
+  (if (stream-empty-p stream) ""
+    (let ((mapped (seq-map function stream)))
+      (stream-reduce (lambda (x y) (concat x separator y)) (stream-first mapped) (stream-rest mapped)))))
 
 (defun stream-of-directory-files-1 (directory &optional nosort recurse follow-links)
   "Helper for `stream-of-directory-files'."
diff --git a/packages/stream/tests/stream-tests.el b/packages/stream/tests/stream-tests.el
index 23a54b5..360a405 100644
--- a/packages/stream/tests/stream-tests.el
+++ b/packages/stream/tests/stream-tests.el
@@ -242,5 +242,37 @@
     (should (= 2 (stream-first str)))
     (should (null (stream-pop stream-empty)))))
 
+(ert-deftest stream-scan-test ()
+  (should (eq (seq-elt (stream-scan #'* 1 (stream-range 1)) 4) 24)))
+
+(ert-deftest stream-flush-test ()
+  (should (let* ((times 0)
+                 (count (lambda () (cl-incf times))))
+            (letrec ((make-test-stream (lambda () (stream-cons (progn (funcall count) nil)
+                                                          (funcall make-test-stream)))))
+              (stream-flush (seq-take (funcall make-test-stream) 5))
+              (eq times 5)))))
+
+(ert-deftest stream-iterate-function-test ()
+  (should (equal (list 0 1 2) (seq-into-sequence (seq-take (stream-iterate-function #'1+ 0) 3)))))
+
+(ert-deftest stream-reduce ()
+  (should (eq (stream-reduce #'* 1 (seq-take (stream-range 1) 4)) 24)))
+
+(ert-deftest stream-concatenate-test ()
+  (should (equal (seq-into-sequence
+                  (stream-concatenate
+                   (stream (list (stream (list 1 2 3))
+                                 (stream (list))
+                                 (stream (list 4))
+                                 (stream (list 5 6 7 8 9))))))
+                 (list 1 2 3 4 5 6 7 8 9))))
+
+(ert-deftest stream-mapconcat-test ()
+  (should (equal (stream-mapconcat #'capitalize (stream (list))             ",") ""))
+  (should (equal (stream-mapconcat #'capitalize (stream (list "a"))         ",") "A"))
+  (should (equal (stream-mapconcat #'capitalize (stream (list "a" "b"))     ",") "A,B"))
+  (should (equal (stream-mapconcat #'capitalize (stream (list "a" "b" "c")) ",") "A,B,C")))
+
 (provide 'stream-tests)
 ;;; stream-tests.el ends here
-- 
2.8.1

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 347 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

Hi Michael,

> +(defun stream-scan (function init stream)
> +  "Return a stream of successive reduced values for STREAM.

Why not using `seq-reduce'?

> +(defun stream-mapconcat (function stream separator)

Would `seq-mapconcat' with a stream-specific implementation make sense?

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> > +(defun stream-scan (function init stream)
> > +  "Return a stream of successive reduced values for STREAM.
>
> Why not using `seq-reduce'?

To implement this, or as a replacement?  Note this is not just reduce,
it returns a stream.  This is useful in its own.

OTOH, I think I should indeed make `stream-reduce' an implementation of
`seq-reduce' for streams.


> > +(defun stream-mapconcat (function stream separator)
>
> Would `seq-mapconcat' with a stream-specific implementation make sense?

Yes, I think so, I'll update my patch.


Thanks,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

[-- Attachment #1: Type: text/plain, Size: 561 bytes --]

Nicolas Petton <nicolas@petton.fr> writes:

> > +(defun stream-scan (function init stream)
> > +  "Return a stream of successive reduced values for STREAM.
>
> Why not using `seq-reduce'?
>
> > +(defun stream-mapconcat (function stream separator)
>
> Would `seq-mapconcat' with a stream-specific implementation make sense?

I updated the patch.  `stream-scan' is useful and not redundant.
`stream-reduce' was indeed redundant, as the generic `seq-reduce'
already works for streams, so I removed it.

And for now, I excluded `stream-mapconcat' from the patch.



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-some-more-basic-stream-operations.patch --]
[-- Type: text/x-diff, Size: 3669 bytes --]

From 8b3326ff7251ba402002dfcbb9272f59547f09ab Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
Date: Thu, 2 Jun 2016 02:42:43 +0200
Subject: [PATCH] Add some more basic stream operations

---
 packages/stream/stream.el             | 45 +++++++++++++++++++++++++++++++++++
 packages/stream/tests/stream-tests.el | 23 ++++++++++++++++++
 2 files changed, 68 insertions(+)

diff --git a/packages/stream/stream.el b/packages/stream/stream.el
index 22cecac..62eb3b6 100644
--- a/packages/stream/stream.el
+++ b/packages/stream/stream.el
@@ -333,6 +333,51 @@ calling this function."
 (cl-defmethod seq-copy ((stream stream))
   "Return a shallow copy of STREAM."
   (stream-delay stream))
+\f
+
+;;; More stream operations
+
+(defun stream-scan (function init stream)
+  "Return a stream of successive reduced values for STREAM.
+
+If the elements of a stream s are s_1, s_2, ..., the elements
+S_1, S_2, ... of the stream returned by \(stream-scan f init s\)
+are defined recursively by
+
+  S_1     = init
+  S_(n+1) = (funcall f S_n s_n)
+
+as long as s_n exists.
+
+Example:
+
+   (stream-scan #'* 1 (stream-range 1))
+
+returns a stream of the factorials."
+  (let ((res init))
+    (stream-cons
+     res
+     (seq-map (lambda (el) (setq res (funcall function res el)))
+              stream))))
+
+(defun stream-flush (stream)
+  "Request all elements from STREAM in order for side effects only."
+  (while (not (stream-empty-p stream))
+    (cl-callf stream-rest stream)))
+
+(defun stream-iterate-function (function value)
+  "Return a stream of repeated applications of FUNCTION to VALUE.
+The returned stream starts with VALUE.  Any successive element
+will be found by calling FUNCTION on the preceding element."
+  (stream-cons
+   value
+   (stream-iterate-function function (funcall function value))))
+
+(defun stream-concatenate (stream-of-streams)
+  "Concatenate all streams in STREAM-OF-STREAMS and return the result.
+All elements in STREAM-OF-STREAMS must be streams.  The result is
+a stream."
+  (seq-reduce #'stream-append stream-of-streams (stream-empty)))
 
 (defun stream-of-directory-files-1 (directory &optional nosort recurse follow-links)
   "Helper for `stream-of-directory-files'."
diff --git a/packages/stream/tests/stream-tests.el b/packages/stream/tests/stream-tests.el
index 23a54b5..16b5756 100644
--- a/packages/stream/tests/stream-tests.el
+++ b/packages/stream/tests/stream-tests.el
@@ -242,5 +242,28 @@
     (should (= 2 (stream-first str)))
     (should (null (stream-pop stream-empty)))))
 
+(ert-deftest stream-scan-test ()
+  (should (eq (seq-elt (stream-scan #'* 1 (stream-range 1)) 4) 24)))
+
+(ert-deftest stream-flush-test ()
+  (should (let* ((times 0)
+                 (count (lambda () (cl-incf times))))
+            (letrec ((make-test-stream (lambda () (stream-cons (progn (funcall count) nil)
+                                                          (funcall make-test-stream)))))
+              (stream-flush (seq-take (funcall make-test-stream) 5))
+              (eq times 5)))))
+
+(ert-deftest stream-iterate-function-test ()
+  (should (equal (list 0 1 2) (seq-into-sequence (seq-take (stream-iterate-function #'1+ 0) 3)))))
+
+(ert-deftest stream-concatenate-test ()
+  (should (equal (seq-into-sequence
+                  (stream-concatenate
+                   (stream (list (stream (list 1 2 3))
+                                 (stream (list))
+                                 (stream (list 4))
+                                 (stream (list 5 6 7 8 9))))))
+                 (list 1 2 3 4 5 6 7 8 9))))
+
 (provide 'stream-tests)
 ;;; stream-tests.el ends here
-- 
2.8.1


[-- Attachment #3: Type: text/plain, Size: 21 bytes --]



Regards,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 486 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> I updated the patch.

Thanks!

> `stream-scan' is useful and not redundant.

Yes, I get it now.  However I'm still a bit confused by its name.

> `stream-reduce' was indeed redundant, as the generic `seq-reduce'
> already works for streams, so I removed it.

Your implementation in your previous patch was however lazy, right?
Would it make sense to add a specific implementation of `seq-reduce' for
streams that'd be lazy?

Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> > `stream-scan' is useful and not redundant.

> Yes, I get it now.  However I'm still a bit confused by its name.

The name is borrowed from Haskell.  Other suggestions welcome.


> > `stream-reduce' was indeed redundant, as the generic `seq-reduce'
> > already works for streams, so I removed it.
>
> Your implementation in your previous patch was however lazy, right?
> Would it make sense to add a specific implementation of `seq-reduce'
> for streams that'd be lazy?

I don't understand what that means: how can "reduce" be lazy at all?  It
needs to generate all stream elements to compute the requested value,
and that at call time.


Regards,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 513 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Nicolas Petton <nicolas@petton.fr> writes:
>
>> > `stream-scan' is useful and not redundant.
>
>> Yes, I get it now.  However I'm still a bit confused by its name.
>
> The name is borrowed from Haskell.  Other suggestions welcome.

I don't have any :)

> I don't understand what that means: how can "reduce" be lazy at all?  It
> needs to generate all stream elements to compute the requested value,
> and that at call time.

Of course, you're right!

Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 172 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Hello,
>
> here is a patch that adds some missing stream operations.

It looks good, feel free to install it.

Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Davis Herring]

> The name is borrowed from Haskell.  Other suggestions welcome.

Mathematica calls it FoldList -- but it's strict, so that's not a strong 
correlate.

Davis

-- 
This product is sold by volume, not by mass.  If it appears too dense or 
too sparse, it is because mass-energy conversion has occurred during 
shipping.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Davis Herring <herring@lanl.gov> writes:

> > The name is borrowed from Haskell.  Other suggestions welcome.
>
> Mathematica calls it FoldList -- but it's strict, so that's not a
> strong correlate.

`stream-fold-stream' would make sense, "a stream of folds".  Or even
`stream-of-partial-folds' or something like that, but that's already
quite longish...


Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Yuri Khan]

On Thu, Jun 9, 2016 at 9:06 PM, Michael Heerdegen
<michael_heerdegen@web.de> wrote:

> I don't understand what that means: how can "reduce" be lazy at all?  It
> needs to generate all stream elements to compute the requested value,
> and that at call time.

If the reduction function has an absorbing element, “reduce” can be
lazy with respect to all elements after the absorbing element has been
reached.

Examples:

* Over integers or finite reals, (reduce * '(3 14 15 0 …)) = 0 no
matter what “…” is.
* Over IEEE 754 floats, 0 is not an absorbing element wrt
multiplication, but NaN is.
* (reduce and '(t t t nil …)) is nil.
* (reduce or '(nil nil nil t …)) is t.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Yuri Khan <yuri.v.khan@gmail.com> writes:

> If the reduction function has an absorbing element, “reduce” can be
> lazy with respect to all elements after the absorbing element has been
> reached.

Do you think we should implement something like this for `seq-reduce'?


Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Yuri Khan]

On Fri, Jun 10, 2016 at 1:41 AM, Michael Heerdegen
<michael_heerdegen@web.de> wrote:

>> If the reduction function has an absorbing element, “reduce” can be
>> lazy with respect to all elements after the absorbing element has been
>> reached.
>
> Do you think we should implement something like this for `seq-reduce'?

There are trade-offs.

A left fold which forces the intermediate result before recurring has
good space complexity, but can only be lazy in the values of the
elements, not their number.

A right fold can be lazy in the number of elements, but in the general
case, when applied to a long list, will build a deep evaluation tree.

https://wiki.haskell.org/Foldr_Foldl_Foldl'

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Yuri Khan <yuri.v.khan@gmail.com> writes:

> A left fold which forces the intermediate result before recurring has
> good space complexity, but can only be lazy in the values of the
> elements, not their number.

AFAIK we only have left fold in seq.el (a right fold wouldn't make sense
for infinite streams anyway).  Every calculation is turned into a loop
where possible, since Emacs Lisp sucks at recursion.

If we had `seq-take-until', one could use that to stop folding at an
absorbing element, like in

#+begin_src emacs-lisp
(seq-reduce
 #'*
 (seq-take-until
  (lambda (x) (not (zerop x)))
  (stream-range -3)) ;-3, -2, -1, 0, 1, 2,...
 1)

==> 0
#+end_src

Would it make sense to add an `seq-take-until' for convenience?


> https://wiki.haskell.org/Foldr_Foldl_Foldl'

Note for readers from the future: the quote at the end is part of the
url.


Regards,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Yuri Khan]

On Fri, Jun 10, 2016 at 9:57 PM, Michael Heerdegen
<michael_heerdegen@web.de> wrote:

> Would it make sense to add an `seq-take-until' for convenience?

seq-take-until might be a fitting addition to seq-take-while.
seq-drop-until, for completeness?

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Yuri Khan <yuri.v.khan@gmail.com> writes:

> > Would it make sense to add an `seq-take-until' for convenience?
>
> seq-take-until might be a fitting addition to seq-take-while.
> seq-drop-until, for completeness?

Probably.  @Nicolas: what do you think, and should I create a patch?

BTW, I've uploaded the patch we talked about, but have not yet bumped
the version.


Thanks, Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> > I updated the patch.

Hmm, seems my implementation of `stream-concatenate' is too recursive
"when executed":

#+begin_src emacs-lisp
(seq-into-sequence
 (stream-concatenate
  (seq-map
   (lambda (n) (stream (list n)))
   (stream (number-sequence 1 500)))))

stream-empty-p: Lisp nesting exceeds `max-lisp-eval-depth'
#+end_src

The standard approach seems to work in this case OTOH, e.g. with (don't
forget to eval the example with lexical-binding turned on!):

#+begin_src emacs-lisp
(defun stream-concatenate (stream-of-streams)
  (while (and (not (stream-empty-p stream-of-streams))
              (stream-empty-p (stream-first stream-of-streams)))
    (cl-callf stream-rest stream-of-streams))
  (if (stream-empty-p stream-of-streams)
      (stream-empty)
    (stream-cons
     (stream-first (stream-first stream-of-streams))
     (stream-concatenate
      (stream-cons (stream-rest (stream-first stream-of-streams))
                   (stream-rest stream-of-streams))))))
(progn
  (seq-into-sequence
   (stream-concatenate
    (seq-map
     (lambda (n) (stream (list n)))
     (stream (number-sequence 1 50000)))))
  nil ;Don't display the result, please
  )
==> nil
#+end_src

So I guess we should replace the current implementation.


Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Markus Triska]

Michael Heerdegen <michael_heerdegen@web.de> writes:

>> > `stream-scan' is useful and not redundant.
>
>> Yes, I get it now.  However I'm still a bit confused by its name.
>
> The name is borrowed from Haskell.  Other suggestions welcome.

stream-scanl

SWI-Prolog defines such a predicate on lists and calls it "scanl".

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Markus Triska <triska@metalevel.at> writes:

> stream-scanl
>
> SWI-Prolog defines such a predicate on lists and calls it "scanl".

So the term "scan" more spread than I feared.

But isn't the "l" redundant in the case of stream.el since there is no
"scanr" (and would not even make sense)?


Thanks,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 265 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> So the term "scan" more spread than I feared.
>
> But isn't the "l" redundant in the case of stream.el since there is no
> "scanr" (and would not even make sense)?

I'd keep "scan" in this case.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Markus Triska]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> But isn't the "l" redundant in the case of stream.el since there is no
> "scanr" (and would not even make sense)?

Still, it's a scan from the left, and there may well be a "scanl" some
day also in Emacs, and then we'd have "scanl" and "stream-scan" (?)

All the best,
Markus

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Hmm, seems my implementation of `stream-concatenate' is too recursive
> "when executed":
>
> #+begin_src emacs-lisp
> (seq-into-sequence
>  (stream-concatenate
>   (seq-map
>    (lambda (n) (stream (list n)))
>    (stream (number-sequence 1 500)))))
>
> stream-empty-p: Lisp nesting exceeds `max-lisp-eval-depth'
> #+end_src

Yes, because with the current definition

#+begin_src emacs-lisp
(defun stream-concatenate (stream-of-streams)
  "Concatenate all streams in STREAM-OF-STREAMS and return the result.
All elements in STREAM-OF-STREAMS must be streams.  The result is
a stream."
  (seq-reduce #'stream-append stream-of-streams (stream-empty)))
#+end_src

when S=s1,s2,s3,..., then

  (stream-concatenate S)

will return s a stream that will find its elements like

  (stream-append s1 (stream-append s2 (stream-append s3 ...)...))

which can be of arbitrary depth.

Will suggest a patch soon.


Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

[-- Attachment #1: Type: text/plain, Size: 361 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Will suggest a patch soon.

Ok, I've not found a better solution than in my first patch, but I think
it was ok (solved the problem, and speed seems to be ok too).

So I only fixed that its implementation of `stream-concatenate' was only
partly delayed.  And this is the result...ok to install?  Thanks.



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Avoid-recursive-stream-append-in-stream-concatenate.patch --]
[-- Type: text/x-diff, Size: 1698 bytes --]

From 6eab42aca0276eb2a534c32a272532d023163824 Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
Date: Sun, 17 Jul 2016 00:41:13 +0200
Subject: [PATCH] Avoid recursive stream-append in stream-concatenate

This fix prevents exceeding `max-lisp-eval-depth' for streams returned
by stream-concatenate.
---
 packages/stream/stream.el | 14 ++++++++++++--
 1 file changed, 12 insertions(+), 2 deletions(-)

diff --git a/packages/stream/stream.el b/packages/stream/stream.el
index 8b71a1b..853251e 100644
--- a/packages/stream/stream.el
+++ b/packages/stream/stream.el
@@ -4,7 +4,7 @@
 
 ;; Author: Nicolas Petton <nicolas@petton.fr>
 ;; Keywords: stream, laziness, sequences
-;; Version: 2.2.0
+;; Version: 2.2.1
 ;; Package-Requires: ((emacs "25"))
 ;; Package: stream
 
@@ -377,7 +377,17 @@ will be found by calling FUNCTION on the preceding element."
   "Concatenate all streams in STREAM-OF-STREAMS and return the result.
 All elements in STREAM-OF-STREAMS must be streams.  The result is
 a stream."
-  (seq-reduce #'stream-append stream-of-streams (stream-empty)))
+  (stream-make
+   (while (and (not (stream-empty-p stream-of-streams))
+               (stream-empty-p (stream-first stream-of-streams)))
+     (cl-callf stream-rest stream-of-streams))
+   (if (stream-empty-p stream-of-streams)
+       nil
+     (cons
+      (stream-first (stream-first stream-of-streams))
+      (stream-concatenate
+       (stream-cons (stream-rest (stream-first stream-of-streams))
+                    (stream-rest stream-of-streams)))))))
 
 (defun stream-of-directory-files-1 (directory &optional nosort recurse follow-links)
   "Helper for `stream-of-directory-files'."
-- 
2.8.1


[-- Attachment #3: Type: text/plain, Size: 21 bytes --]



Regards,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 418 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Ok, I've not found a better solution than in my first patch, but I think
> it was ok (solved the problem, and speed seems to be ok too).
>
> So I only fixed that its implementation of `stream-concatenate' was only
> partly delayed.  And this is the result...ok to install?  Thanks.

Yes (assuming that all tests are green), thank you! 

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> Yes (assuming that all tests are green) [...]

Sure - and I've also worked with the patched version for quite a while
now.

Installed.


Thanks,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Yuri Khan <yuri.v.khan@gmail.com> writes:

> > Would it make sense to add an `seq-take-until' for convenience?
>
> seq-take-until might be a fitting addition to seq-take-while.
> seq-drop-until, for completeness?

Hmm, isn't `seq-drop-until' redundant - because it's the same as
`seq-drop-while' with negated predicate?

For example, if stream

  S = 0, 0, ..., 0, 1, 2, 3, ...

then naturally would

  (seq-drop-while #'zerop S) == 1, 2, ...
                             == (seq-drop-until
                                  (lambda (n) (not (zerop n)))
                                   S)

`seq-take-until' is obviously not redundant in the same way.  So, why is
the symmetry broken?  I think the problem is the wording:
`seq-drop-until' is simply not the natural counterpart of
`seq-drop-while'.

We would want a function seq-X so that

  (seq-X #'zerop S) == 0, 1, 2, ...

I think that this function would be useful (I already needed it).  But
what word sequence X would describe these semantics (how should we call
the function)?


Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Yuri Khan]

On Sat, Sep 17, 2016 at 6:52 AM, Michael Heerdegen
<michael_heerdegen@web.de> wrote:

> For example, if stream
>
>   S = 0, 0, ..., 0, 1, 2, 3, ...
>
> We would want a function seq-X so that
>
>   (seq-X #'zerop S) == 0, 1, 2, ...
>
> I think that this function would be useful (I already needed it).  But
> what word sequence X would describe these semantics (how should we call
> the function)?

You’re right, drop-until is not a good match for this semantics. By
the way, how would you describe the required behavior without going
operational (mirroring the implementation)?

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Yuri Khan <yuri.v.khan@gmail.com> writes:

> You’re right, drop-until is not a good match for this semantics. By
> the way, how would you describe the required behavior without going
> operational (mirroring the implementation)?

If you asking the question implies that you find the semantics not
trivially clear, maybe the following simpler (even superior) approach
would be much better: Add an optional integer type argument to
`seq-drop-while' and `seq-take-while' that allows to shift the index by
the specified amount (as far as possible):

#+begin_src emacs-lisp
(cl-defgeneric seq-drop-while (pred sequence &optional less)
  (seq-drop sequence (- (seq--count-successive pred sequence) (or less 0))))

(cl-defgeneric seq-take-while (pred sequence &optional more)
  (seq-take sequence (+ (seq--count-successive pred sequence) (or more 0))))
#+end_src


Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Yuri Khan]

On Sun, Sep 25, 2016 at 10:38 PM, Michael Heerdegen
<michael_heerdegen@web.de> wrote:

> If you asking the question implies that you find the semantics not
> trivially clear

Yes. Naming things is listed as the second hardest problem in computer
science, and having a concise explanation of the semantics helps with
that greatly.

> maybe the following simpler (even superior) approach
> would be much better: Add an optional integer type argument to
> `seq-drop-while' and `seq-take-while' that allows to shift the index by
> the specified amount (as far as possible):
>
> #+begin_src emacs-lisp
> (cl-defgeneric seq-drop-while (pred sequence &optional less)
>   (seq-drop sequence (- (seq--count-successive pred sequence) (or less 0))))
>
> (cl-defgeneric seq-take-while (pred sequence &optional more)
>   (seq-take sequence (+ (seq--count-successive pred sequence) (or more 0))))
> #+end_src

Let me see if I can formulate the semantics here. I will work from
cases first and then try to describe the intended behavior in a single
sentence.

seq-drop-while

* Easiest happy case: A finite number, no fewer than LESS, of initial
elements satisfy PRED. They are counted, then LESS subtracted,
yielding a non-negative count of elements to drop.

* Fewer than LESS (possibly zero) initial elements satisfy PRED. They
are counted, then LESS subtracted, yielding a negative drop count.
Presumably then seq-drop returns the original sequence.

* The sequence is infinite and its every successive element satisfies
PRED. Then the above implementation diverges, trying to count to
infinity.

My guess at intended semantics: Return the subsequence of SEQUENCE
obtained by dropping all but the last LESS initial elements that
satisfy PRED. (This does not explain the negative drop count case.)


seq-take-while

* A finite number (possibly zero) of initial elements satisfy PRED,
and after that follow at least MORE elements.

* A finite number (possibly zero) of initial elements satisfy PRED,
and after that follow fewer than MORE (possibly zero) elements.
Presumably, seq-take will return the original sequence.

* The sequence is infinite and its every successive element satisfies
PRED. The counting implementation will again diverge.

My guess: Return the initial subsequence of SEQUENCE whose elements
satisfy PRED, followed by at most MORE more successive elements.
(Another implementation can be devised that handles the infinite
case.)


Looking back at the thread, I recall that this exploration started
from my conjecture that detecting the presence of an absorbing element
could make reduction lazy wrt all following elements. The possibility
is fun to explore, but I am now thinking that was not such a useful
idea.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[John Wiegley]

>>>>> "MH" == Michael Heerdegen <michael_heerdegen@web.de> writes:

HM> #+begin_src emacs-lisp
MH> (cl-defgeneric seq-drop-while (pred sequence &optional less)
MH>   (seq-drop sequence (- (seq--count-successive pred sequence) (or less 0))))

HM> (cl-defgeneric seq-take-while (pred sequence &optional more)
MH>   (seq-take sequence (+ (seq--count-successive pred sequence) (or more 0))))
HM> #+end_src

I had no idea Org/Gnus were integrated lately to display these source code
blocks using syntax highlighting, but it's quite nice for reading. :)  Thanks
for using this sort of markup.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Yuri Khan <yuri.v.khan@gmail.com> writes:

> [...describing the semantics...]

Exactly my thoughts.

> Looking back at the thread, I recall that this exploration started
> from my conjecture that detecting the presence of an absorbing element
> could make reduction lazy wrt all following elements. The possibility
> is fun to explore, but I am now thinking that was not such a useful
> idea.

Nonetheless I think providing something like that is necessary, because
it's a required functionality.

Hmm, what would you think of a function that returns the index of the
first element of a sequence that fulfills a certain predicate (actually,
there is already something similar, `seq-position', but that is meant to
find the index of an element equal to a given one)?  That would, in some
sense, be the smallest common divider of what we discussed.


Regards,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Yuri Khan]

On Wed, Sep 28, 2016 at 8:07 AM, Michael Heerdegen
<michael_heerdegen@web.de> wrote:

> Hmm, what would you think of a function that returns the index of the
> first element of a sequence that fulfills a certain predicate (actually,
> there is already something similar, `seq-position', but that is meant to
> find the index of an element equal to a given one)?  That would, in some
> sense, be the smallest common divider of what we discussed.

That is a good complement to seq-position (and might be named seq-position-if).

However, these are also strict in all elements up to and including the
one being sought, and may not terminate. As an example, if you want a
subsequence starting at the first odd number or at index 1000,
whichever is earlier, (seq-drop (min 1000 (seq-position-if 'odd S)) S)
will not do the right thing.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 236 bytes --]

Yuri Khan <yuri.v.khan@gmail.com> writes:

Hi Yuri,

> That is a good complement to seq-position (and might be named
> seq-position-if).

I like the idea, but not the name.  I'd go with something like
`seq-find-position'.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Yuri Khan <yuri.v.khan@gmail.com> writes:

> > [...] be the smallest common divider of what we discussed.

Oops, "greatest" of course, this wasn't meant ironically, it was just
late, ok?


> That is a good complement to seq-position (and might be named
> seq-position-if).

> However, these are also strict in all elements up to and including the
> one being sought, and may not terminate.

I only partly understand your objection (what do you mean with "strict
in all elements"?).

IMO, termination in every case is not a requirement, else, we would not
have `while'.  Formulating algorithms to use streams is just a way to
describe loops.  So I don't see why it would be a problem when stream
primitives potentially don't terminate.

> As an example, if you want a subsequence starting at the first odd
> number or at index 1000, whichever is earlier, (seq-drop (min 1000
> (seq-position-if 'odd S)) S) will not do the right thing.

Would adding an optional argument that allows to specify an upper limit
for the indexes the function looks at cover (all of) your concerns?


Regards,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Yuri Khan]

On Thu, Sep 29, 2016 at 1:27 AM, Michael Heerdegen
<michael_heerdegen@web.de> wrote:

> I only partly understand your objection (what do you mean with "strict
> in all elements"?).
>
> IMO, termination in every case is not a requirement, else, we would not
> have `while'.  Formulating algorithms to use streams is just a way to
> describe loops.  So I don't see why it would be a problem when stream
> primitives potentially don't terminate.

In lazy computations, an algorithm is said to be strict (or eager)
with respect to its argument if it forces the computation of that
argument’s value.

Streams are in essence lazy lists. As such, they bring a new
possibility to the table: while a list is limited by the available
memory, a stream is potentially infinite. Solving algorithmic problems
in terms of lists requires reasoning about termination. Yes, this is
the same as with loops — it’s just that loops force such reasoning
while with streams the issue is easy to overlook.

>> As an example, if you want a subsequence starting at the first odd
>> number or at index 1000, whichever is earlier, (seq-drop (min 1000
>> (seq-position-if 'odd S)) S) will not do the right thing.
>
> Would adding an optional argument that allows to specify an upper limit
> for the indexes the function looks at cover (all of) your concerns?

That was just an example. Real users will have other needs. If given a
primitive that returns an index of something, they will try solving
their problems in terms of that index. It is an interface that is easy
to use incorrectly.

But please do not let my theoretical concerns stop you from
implementing useful things. A working implementation is the surest way
of gaining collective experience about a tool.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

[-- Attachment #1: Type: text/plain, Size: 2337 bytes --]

Hi everybody!

I want to revive this discussion.  I needed something like this for
el-search, so I gave it a second thought.

> >> As an example, if you want a subsequence starting at the first odd
> >> number or at index 1000, whichever is earlier, (seq-drop (min 1000
> >> (seq-position-if 'odd S)) S) will not do the right thing.
> >
> > Would adding an optional argument that allows to specify an upper limit
> > for the indexes the function looks at cover (all of) your concerns?
>
> That was just an example. Real users will have other needs. If given a
> primitive that returns an index of something, they will try solving
> their problems in terms of that index. It is an interface that is easy
> to use incorrectly.
>
> But please do not let my theoretical concerns stop you from
> implementing useful things. A working implementation is the surest way
> of gaining collective experience about a tool.

I tried to cope with our problems by using abstraction and higher order
functions (so far, only implemented for streams - see below).

We talked about pairs of function (take-until, drop-until), and a
problem was that the semantics were always a bit vague or hard to define
(is a border element in or out?, etc).  A difficulty with the discussed
concepts was that it was not easily possible to step back to cut a
stream before a certain element when we already had skipped that element
etc.

That brought me to the following idea:

The underlying basic "operation" is to divide a stream into two parts.
Such a division is non-ambiguously described by specifying the second
part, the rest-stream.  Any function dividing a stream into two parts
can be described by another function F stream -> rest, that takes a
stream, and returns a rest.  Such functions F are the input of my
low-level functions.

A subsequent application of divide operations leads to a partition of a
stream into a stream of substreams, which I also implemented.

I also implemented two more higher-level functions for stream
dividing/partitioning that hopefully should cover most of the use cases
of seq-drop-while et alter.  For the cases that should not be covered,
you can use the lower level functions with an appropriate function F as
described above.  Sounds complicated, but it's just a sum of trivial
pieces.

And this is how that looks.  WDYT?


[-- Attachment #2: stream-divide.el --]
[-- Type: application/emacs-lisp, Size: 2323 bytes --]

[-- Attachment #3: Type: text/plain, Size: 21 bytes --]



Regards,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> > > Would adding an optional argument that allows to specify an upper
> > > limit for the indexes the function looks at cover (all of) your
> > > concerns?

BTW, with the suggested approach, you can use a counter to specify a
break condition, like here, were I want to calculate the stream of
natural numbers up to a place where two subsequent elements have a
difference that is not less than 2 (which never happens), but where I
say I want to have at most 25 elements:

#+begin_src emacs-lisp
(seq-into-sequence
 (car
  (stream-divide
   (let (the-naturals) (setq the-naturals (stream-cons 1 (seq-map #'1+ the-naturals))))
   (let ((counter 0))
     (lambda (this next)
       (and (< (cl-incf counter) 25)
            (< (- next this) 2)))))))
==> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25)
#+end_src

(be sure to eval with lexical-binding -> t).


Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 315 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Hi everybody!

Hi Michael,


> And this is how that looks.  WDYT?
>
> (defun stream-divide-with-get-rest-fun (stream get-rest-fun)

Is this function public on purpose?

> (defun stream-partition-with-get-rest-fun (stream get-rest-fun)

Same question :)

Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 472 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 793 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> BTW, with the suggested approach, you can use a counter to specify a
> break condition, like here, were I want to calculate the stream of
> natural numbers up to a place where two subsequent elements have a
> difference that is not less than 2 (which never happens), but where I
> say I want to have at most 25 elements:
>
> #+begin_src emacs-lisp
> (seq-into-sequence
>  (car
>   (stream-divide
>    (let (the-naturals) (setq the-naturals (stream-cons 1 (seq-map #'1+ the-naturals))))
>    (let ((counter 0))
>      (lambda (this next)
>        (and (< (cl-incf counter) 25)
>             (< (- next this) 2)))))))
> ==> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25)
> #+end_src

That's really neat!

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 472 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> > And this is how that looks.  WDYT?
> >
> > (defun stream-divide-with-get-rest-fun (stream get-rest-fun)
>
> Is this function public on purpose?
>
> > (defun stream-partition-with-get-rest-fun (stream get-rest-fun)
>
> Same question :)

Yes, it's public on purpose.  They have ugly names (maybe we find better
ones?), but they are useful per se as the more general tool.  I think
they are also quite nice to use, because the creation of streams is
factored out, and you can pass the essence of the calculation as a
function argument.

And `stream-divide' and `stream-partition' no doubt don't cover all use
cases one can think of.  Looking at two subsequent elements at the same
time as in `stream-divide' gives you flexibility, but the first part of
`stream-divide' will always have at least one element.  This will not
fit in some cases.

Here is another use case where I think `stream-divide-with-get-rest-fun'
suits better: I want to have the last 3 Fibonacci number less than 1000.
This is how I would do it:

#+begin_src emacs-lisp
;; -*- lexical-binding: t -*-
(let ((count 3) fibs)
  (setq fibs (stream-make (cons 1 (stream-scan #'+ 1 fibs))))
  (seq-into-sequence
   (seq-take
    (cadr
     (stream-divide-with-get-rest-fun
      fibs
      (lambda (stream)
        (let ((rest stream))
          (dotimes (_ count) (stream-pop stream))
          (while (< (stream-pop stream) 1000)
            (stream-pop rest))
          rest))))
    count)))
#+end_src

You could also do the same with `stream-divide', but it would rather
look more complicated.


Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Yes, it's public on purpose [...]

Ok...what do we do now with this stuff?  I could provide a patch if you
want.  If you are not sure if my approach is the best solution and are
reluctant to accept a patch for "stream.el", we could also start a new
file "stream-x.el" where we collect additional stuff we are a bit unsure
about at the moment.


Thanks,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 184 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Yes, it's public on purpose.  They have ugly names

Indeed, I don't like the names, but I don't have better names either.

Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 472 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 454 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> If you are not sure if my approach is the best solution and are
> reluctant to accept a patch for "stream.el", we could also start a new
> file "stream-x.el" where we collect additional stuff we are a bit unsure
> about at the moment.

Yes, that seems like a fair trade-off.  Feel free to add stream-x.el.
It's not that I don't like your additions, but I'm not sure about some
names.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 472 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> Yes, that seems like a fair trade-off.  Feel free to add stream-x.el.

But we still want to add the new file to the "stream" package - correct?


Thanks,

Michael.

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

[-- Attachment #1: Type: text/plain, Size: 264 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> 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.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-file-stream-x.el-to-the-stream-package.patch --]
[-- Type: text/x-diff, Size: 5883 bytes --]

From 2c073c2aa3c2373c5a5f71d8565b79732e4a6a87 Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
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 <michael_heerdegen@web.de>
+;; Maintainer: Michael Heerdegen <michael_heerdegen@web.de>
+;; 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 <http://www.gnu.org/licenses/>.
+
+
+;;; 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

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 249 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Ok, find the final patch I intend to install attached.  Shall I bump the
> version of the stream package as well?

Looks good to me.  I'd also bump the version of stream as well.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 472 bytes --]

Re: [PATCH] Gnu Elpa: stream.el: Add some more basic stream operations

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> Looks good to me.  I'd also bump the version of stream as well.

Ok, done, and bumped version to 2.2.4.


Regards,

Michael.