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

classic Classic list List threaded Threaded
48 messages Options
123
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[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))
+
+
+;;; 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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Michael Heerdegen
Michael Heerdegen <[hidden email]> writes:

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

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


Thanks,

Michael.


0001-Add-some-more-basic-stream-operations.patch (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Nicolas Petton-2
In reply to this post by Michael Heerdegen
Michael Heerdegen <[hidden email]> 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

signature.asc (523 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Michael Heerdegen
Nicolas Petton <[hidden email]> 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.


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Michael Heerdegen
In reply to this post by Nicolas Petton-2
Nicolas Petton <[hidden email]> 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.



From 8b3326ff7251ba402002dfcbb9272f59547f09ab Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <[hidden email]>
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))
+
+
+;;; 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




Regards,

Michael.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Nicolas Petton-2
Michael Heerdegen <[hidden email]> 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

signature.asc (523 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Michael Heerdegen
Nicolas Petton <[hidden email]> 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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Nicolas Petton-2
Michael Heerdegen <[hidden email]> writes:

> Nicolas Petton <[hidden email]> 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

signature.asc (523 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Nicolas Petton-2
In reply to this post by Michael Heerdegen
Michael Heerdegen <[hidden email]> writes:

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

It looks good, feel free to install it.

Nico

signature.asc (523 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Davis Herring
In reply to this post by Michael Heerdegen
> 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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Michael Heerdegen
Davis Herring <[hidden email]> 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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Yuri Khan-2
In reply to this post by Michael Heerdegen
On Thu, Jun 9, 2016 at 9:06 PM, Michael Heerdegen
<[hidden email]> 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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Michael Heerdegen
Yuri Khan <[hidden email]> 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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Yuri Khan-2
On Fri, Jun 10, 2016 at 1:41 AM, Michael Heerdegen
<[hidden email]> 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'

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Michael Heerdegen
Yuri Khan <[hidden email]> 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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Yuri Khan-2
On Fri, Jun 10, 2016 at 9:57 PM, Michael Heerdegen
<[hidden email]> 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?

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Michael Heerdegen
Yuri Khan <[hidden email]> 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.


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Michael Heerdegen
In reply to this post by Nicolas Petton-2
Nicolas Petton <[hidden email]> 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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Markus Triska-4
In reply to this post by Michael Heerdegen
Michael Heerdegen <[hidden email]> 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".


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Michael Heerdegen
Markus Triska <[hidden email]> 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.


123
Loading...