;;; stream.el --- Implementation of streams -*- lexical-binding: t -*-
-;; Copyright (C) 2015 Free Software Foundation, Inc.
+;; Copyright (C) 2016 Free Software Foundation, Inc.
;; Author: Nicolas Petton <nicolas@petton.fr>
;; Keywords: stream, laziness, sequences
-;; Version: 2.0.1
+;; Version: 2.2.0
;; Package-Requires: ((emacs "25"))
;; Package: stream
(defmacro stream-make (&rest body)
"Return a stream built from BODY.
-BODY must return nil or a cons cell, which cdr is itself a
+BODY must return nil or a cons cell whose cdr is itself a
stream."
(declare (debug t))
`(list ',stream--identifier (thunk-delay ,@body)))
(cl-defmethod stream ((buffer buffer) &optional pos)
"Return a stream of the characters of the buffer BUFFER.
-BUFFER-OR-NAME may be a buffer or a string (buffer name).
+BUFFER may be a buffer or a string (buffer name).
The sequence starts at POS if non-nil, 1 otherwise."
(with-current-buffer buffer
(unless pos (setq pos (point-min)))
(char-after (point)))))
(stream buffer (1+ pos)))))
+(declare-function iter-next "generator")
+
+(defun stream-from-iterator (iterator)
+ "Return a stream generating new elements through ITERATOR.
+ITERATOR is an iterator object in terms of the \"generator\"
+package."
+ (stream-make
+ (condition-case nil
+ (cons (iter-next iterator) (stream-from-iterator iterator))
+ (iter-end-of-sequence nil))))
+
+(defun stream-regexp (buffer regexp)
+ (stream-make
+ (let (match)
+ (with-current-buffer buffer
+ (setq match (re-search-forward regexp nil t)))
+ (when match
+ (cons (match-data) (stream-regexp buffer regexp))))))
+
(defun stream-range (&optional start end step)
"Return a stream of the integers from START to END, stepping by STEP.
If START is nil, it defaults to 0. If STEP is nil, it defaults to
(eq (car stream) stream--identifier)))
(defun stream-empty ()
- "Return an empty stream."
+ "Return a new empty stream."
(list stream--identifier (thunk-delay nil)))
(defun stream-empty-p (stream)
"Return a stream of all but the first element of STREAM."
(or (cdr (thunk-force (cadr stream)))
(stream-empty)))
+
+(defun stream-append (&rest streams)
+ "Concatenate the STREAMS.
+Requesting elements from the resulting stream will request the
+elements in the STREAMS in order."
+ (if (null streams)
+ (stream-empty)
+ (stream-make
+ (let ((first (pop streams)))
+ (while (and (stream-empty-p first) streams)
+ (setq first (pop streams)))
+ (if (stream-empty-p first)
+ nil
+ (cons (stream-first first)
+ (if streams (apply #'stream-append (stream-rest first) streams)
+ (stream-rest first))))))))
+
+(defmacro stream-pop (stream)
+ "Return the first element of STREAM and set the value of STREAM to its rest."
+ (unless (symbolp stream)
+ (error "STREAM must be a symbol"))
+ `(prog1
+ (stream-first ,stream)
+ (setq ,stream (stream-rest ,stream))))
\f
;;; cl-generic support for streams
-(defvar stream--generalizer
- (cl-generic-make-generalizer
- 11
- (lambda (name)
- `(when (streamp ,name)
- 'stream))
- (lambda (tag)
- (when (eq tag 'stream)
- '(stream)))))
+(cl-generic-define-generalizer stream--generalizer
+ 11
+ (lambda (name)
+ `(when (streamp ,name)
+ 'stream))
+ (lambda (tag)
+ (when (eq tag 'stream)
+ '(stream))))
(cl-defmethod cl-generic-generalizers ((_specializer (eql stream)))
"Support for `stream' specializers."
;;; Implementation of seq.el generic functions
-(cl-defmethod seq-p ((_stream stream))
+(cl-defmethod seqp ((_stream stream))
t)
(cl-defmethod seq-elt ((stream stream) n)
(seq-take (seq-drop stream start) (- end start)))
(cl-defmethod seq-into-sequence ((stream stream))
- "Convert STREAM into a sequence"
+ "Convert STREAM into a sequence."
(let ((list))
(seq-doseq (elt stream)
(push elt list))
(stream-rest stream)))))
(cl-defmethod seq-map (function (stream stream))
- "Return a stream.
-The elements of the produced sequence consist of the application
-of FUNCTION to each element of STREAM."
- (if (stream-empty-p stream)
- stream
- (stream-cons
- (funcall function (stream-first stream))
- (seq-map function (stream-rest stream)))))
+ "Return a stream representing the mapping of FUNCTION over STREAM.
+The elements of the produced stream are the results of the
+applications of FUNCTION on each element of STREAM in succession."
+ (stream-make
+ (when (not (stream-empty-p stream))
+ (cons (funcall function (stream-first stream))
+ (seq-map function (stream-rest stream))))))
(cl-defmethod seq-do (function (stream stream))
"Evaluate FUNCTION for each element of STREAM eagerly, and return nil.
-`seq-do' should never be used on infinite streams."
+`seq-do' should never be used on infinite streams without some
+kind of nonlocal exit."
(while (not (stream-empty-p stream))
(funcall function (stream-first stream))
(setq stream (stream-rest stream))))
(cons (stream-first stream)
(seq-filter pred (stream-rest stream)))))))
+(defmacro stream-delay (expr)
+ "Return a new stream to be obtained by evaluating EXPR.
+EXPR will be evaluated once when an element of the resulting
+stream is requested for the first time, and must return a stream.
+EXPR will be evaluated in the lexical environment present when
+calling this function."
+ (let ((stream (make-symbol "stream")))
+ `(stream-make (let ((,stream ,expr))
+ (if (stream-empty-p ,stream)
+ nil
+ (cons (stream-first ,stream)
+ (stream-rest ,stream)))))))
+
(cl-defmethod seq-copy ((stream stream))
"Return a shallow copy of STREAM."
- (stream-cons (stream-first stream)
- (stream-rest 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'."
+ (stream-delay
+ (if (file-accessible-directory-p directory)
+ (let (files dirs (reverse-fun (if nosort #'identity #'nreverse)))
+ (dolist (file (directory-files directory t nil nosort))
+ (let ((is-dir (file-directory-p file)))
+ (unless (and is-dir
+ (member (file-name-nondirectory (directory-file-name file))
+ '("." "..")))
+ (push file files)
+ (when (and is-dir
+ (or follow-links (not (file-symlink-p file)))
+ (if (functionp recurse) (funcall recurse file) recurse))
+ (push file dirs)))))
+ (apply #'stream-append
+ (stream (funcall reverse-fun files))
+ (mapcar
+ (lambda (dir) (stream-of-directory-files-1 dir nosort recurse follow-links))
+ (funcall reverse-fun dirs))))
+ (stream-empty))))
+
+(defun stream-of-directory-files (directory &optional full nosort recurse follow-links filter)
+ "Return a stream of names of files in DIRECTORY.
+Call `directory-files' to list file names in DIRECTORY and make
+the result a stream. Don't include files named \".\" or \"..\".
+The arguments FULL and NOSORT are directly passed to
+`directory-files'.
+
+Third optional argument RECURSE non-nil means recurse on
+subdirectories. If RECURSE is a function, it should be a
+predicate accepting one argument, an absolute file name of a
+directory, and return non-nil when the returned stream should
+recurse into that directory. Any other non-nil value means
+recurse into every readable subdirectory.
+
+Even with recurse non-nil, don't descent into directories by
+following symlinks unless FOLLOW-LINKS is non-nil.
+
+If FILTER is non-nil, it should be a predicate accepting one
+argument, an absolute file name. It is used to limit the
+resulting stream to the files fulfilling this predicate."
+ (let* ((stream (stream-of-directory-files-1 directory nosort recurse follow-links))
+ (filtered-stream (if filter (seq-filter filter stream) stream)))
+ (if full filtered-stream
+ (seq-map (lambda (file) (file-relative-name file directory)) filtered-stream))))
(provide 'stream)
;;; stream.el ends here