Infinite Data Types: Streams
Table of Contents
- 1. Introduction
- 2. Deconstructing a stream :
hdandtl - 3. Unrolling a stream:
s-takeands-drop - 4. Streams as traces of autonomous systems
- 5. The empty stream
- 6. Converting lists to streams
- 7. Stream zip and map
- 8. Streams as traces of non-autonomous state transition systems
- 9. Other Progressions
- 10. Power Series
- 11. Convolution
- 12. Bibliographic notes
\( %% Your math definitions here % \newcommand{\alphaequiv}{{\underset{\raise 0.7em\alpha}{=}}} \newcommand{\yields}{\Rightarrow} \newcommand{\derives}{\overset{*}{\yields}} \newcommand{\alphaequiv}{=_{\alpha}} \newcommand{\tto}[2]{{\overset{#1}{\underset{#2}{\longrightarrow}}}} \newcommand{\transitsto}[2]{{\overset{#1}{\underset{#2}{\longrightarrow}}}} \newcommand{\xtransitsto}[2]{{\underset{#2}{\xrightarrow{#1}}}} \newcommand{\xtransitsfrom}[2]{{\underset{#2}{\xleftarrow{#1}}}} \newcommand{\xto}[2]{{\xtransitsto{#1}{#2}}} \newcommand{\xfrom}[2]{{\xtransitsfrom{#1}{#2}}} \newcommand{\xreaches}[2]{{\underset{#2}{\xtwoheadrightarrow{#1}}}} \newcommand{\reaches}[2]{{\underset{#2}{\xtwoheadrightarrow{#1}}}} %\newcommand{\reaches}[2]{{\overset{#1}{\underset{#2}{\twoheadrightarrow}}}} %\newcommand{\goesto}[2]{\transitsto{#1}{#2}} %\newcommand{\betareducesto}{{\underset{\beta}{\rightarrow}}} \newcommand{\betareducesto}{\rightarrow_{\beta}} %\newcommand{\etareducesto}{{\underset{\eta}{\rightarrow}}} \newcommand{\etareducesto}{\rightarrow_{\eta}} %\newcommand{\betaetareducesto}{{\underset{\beta\ \eta}{\rightarrow}}} \newcommand{\betaetareducesto}{\rightarrow_{\beta\eta}} \newcommand{\preducesto}{\rhd} \newcommand{\psimplifiesto}{\stackrel{\scriptstyle{*}}{\rhd}} \newcommand{\lreducesto}{\rightsquigarrow} \newcommand{\lsimplifiesto}{\stackrel{\scriptstyle{*}}{\lreducesto}} \newcommand{\rewritesto}{\hookrightarrow} \newcommand{\goesto}[1]{\stackrel{#1}{\rightarrow}} \newcommand{\xgoesto}[1]{\xrightarrow{#1}} \newcommand{\reducesto}{\stackrel{}{\rightarrow}} \newcommand{\simplifiesto}{\stackrel{\scriptstyle{*}}{\rightarrow}} \newcommand{\connected}[1]{\stackrel{#1}{\leftrightarrow}} \newcommand{\joins}{\downarrow} \newcommand{\evaluatesto}{\Longrightarrow} %\newcommand{\lit}[1]{\hbox{\sf{#1}}} \newcommand{\lit}[1]{{\sf{#1}}} \newcommand{\true}{\lit{true}} \newcommand{\false}{\lit{false}} \def\Z{\mbox{${\mathbb Z}$}} \def\N{\mbox{${\mathbb N}$}} \def\P{\mbox{${\mathbb P}$}} \def\R{\mbox{${\mathbb R}$}} \newcommand{\Rp}{{\mathbb{R}}^+} \def\Bool{\mbox{${\mathbb B}$}} \def\sA{\mbox{${\cal A}$}} \def\sB{\mbox{${\cal B}$}} \def\sC{\mbox{${\cal C}$}} \def\sD{\mbox{${\cal D}$}} \def\sF{\mbox{${\cal F}$}} \def\sG{\mbox{${\cal G}$}} \def\sL{\mbox{${\cal L}$}} \def\sP{\mbox{${\cal P}$}} \def\sM{\mbox{${\cal M}$}} \def\sN{\mbox{${\cal N}$}} \def\sR{\mbox{${\cal R}$}} \def\sS{\mbox{${\cal S}$}} \def\sO{\mbox{${\cal O}$}} \def\sT{\mbox{${\cal T}$}} \def\sU{\mbox{${\cal U}$}} \def\th{\mbox{$\widetilde{h}$}} \def\tg{\mbox{$\widetilde{g}$}} \def\tP{\mbox{$\widetilde{P}$}} \def\norm{\mbox{$\parallel$}} \def\osum{${{\bigcirc}}\!\!\!\!{\rm s}~$} \def\pf{\noindent {\bf Proof}~~} \def\exec{\mathit{exec}} \def\Act{\mathit{A\!ct}} \def\Traces{\mathit{Traces}} \def\Spec{\mathit{Spec}} \def\uns{\mathit{unless}} \def\ens{\mathit{ensures}} \def\lto{\mathit{leads\!\!-\!\!to}} \def\a{\alpha} \def\b{\beta} \def\c{\gamma} \def\d{\delta} \def\sP{\mbox{${\cal P}$}} \def\sM{\mbox{${\cal M}$}} \def\sA{\mbox{${\cal A}$}} \def\sB{\mbox{${\cal B}$}} \def\sC{\mbox{${\cal C}$}} \def\sI{\mbox{${\cal I}$}} \def\sS{\mbox{${\cal S}$}} \def\sD{\mbox{${\cal D}$}} \def\sF{\mbox{${\cal F}$}} \def\sG{\mbox{${\cal G}$}} \def\sR{\mbox{${\cal R}$}} \def\tg{\mbox{$\widetilde{g}$}} \def\ta{\mbox{$\widetilde{a}$}} \def\tb{\mbox{$\widetilde{b}$}} \def\tc{\mbox{$\widetilde{c}$}} \def\tx{\mbox{$\widetilde{x}$}} \def\ty{\mbox{$\widetilde{y}$}} \def\tz{\mbox{$\widetilde{z}$}} \def\tI{\mbox{$\widetilde{I}$}} \def\norm{\mbox{$\parallel$}} \def\sL{\mbox{${\cal L}$}} \def\sM{\mbox{${\cal M}$}} \def\sN{\mbox{${\cal N}$}} \def\th{\mbox{$\widetilde{h}$}} \def\tg{\mbox{$\widetilde{g}$}} \def\tP{\mbox{$\widetilde{P}$}} \def\norm{\mbox{$\parallel$}} \def\to{\rightarrow} \def\ov{\overline} \def\gets{\leftarrow} \def\too{\longrightarrow} \def\To{\Rightarrow} \def\points{\mapsto} %\def\yields{\mapsto^{*}} \def\un{\underline} \def\vep{$\varepsilon$} \def\ep{$\epsilon$} \def\tri{$\bigtriangleup$} \def\Fi{$F^{\infty}$} \def\Di{\Delta^{\infty}} \def\ebox\Box \def\emp{\emptyset} \def\leadsto{\rightharpoondown^{*}} \newcommand{\benum}{\begin{enumerate}} \newcommand{\eenum}{\end{enumerate}} \newcommand{\bdes}{\begin{description}} \newcommand{\edes}{\end{description}} \newcommand{\bt}{\begin{theorem}} \newcommand{\et}{\end{theorem}} \newcommand{\bl}{\begin{lemma}} \newcommand{\el}{\end{lemma}} %\newcommand{\bp}{\begin{prop}} %\newcommand{\ep}{\end{prop}} \newcommand{\bd}{\begin{defn}} \newcommand{\ed}{\end{defn}} \newcommand{\brem}{\begin{remark}} \newcommand{\erem}{\end{remark}} \newcommand{\bxr}{\begin{exercise}} \newcommand{\exr}{\end{exercise}} \newcommand{\bxm}{\begin{example}} \newcommand{\exm}{\end{example}} \newcommand{\beqa}{\begin{eqnarray*}} \newcommand{\eeqa}{\end{eqnarray*}} \newcommand{\bc}{\begin{center}} \newcommand{\ec}{\end{center}} \newcommand{\bcent}{\begin{center}} \newcommand{\ecent}{\end{center}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \newcommand{\bcor}{\begin{corollary}} \newcommand{\ecor}{\end{corollary}} \newcommand{\bds}{\begin{defns}} \newcommand{\eds}{\end{defns}} \newcommand{\brems}{\begin{remarks}} \newcommand{\erems}{\end{remarks}} \newcommand{\bxrs}{\begin{exercises}} \newcommand{\exrs}{\end{exercises}} \newcommand{\bxms}{\begin{examples}} \newcommand{\exms}{\end{examples}} \newcommand{\bfig}{\begin{figure}} \newcommand{\efig}{\end{figure}} \newcommand{\set}[1]{\{#1\}} \newcommand{\pair}[1]{\langle #1\rangle} \newcommand{\tuple}[1]{\langle #1\rangle} \newcommand{\union}{\cup} \newcommand{\Union}{\bigcup} \newcommand{\intersection}{\cap} \newcommand{\Intersection}{\bigcap} \newcommand{\B}{\textbf{B}} %\newcommand{\be}[2]{\begin{equation} \label{#1} \tag{#2} \end{equation}} \newcommand{\abs}[1]{{\lvert}#1{\rvert}} \newcommand{\id}[1]{\mathit{#1}} \newcommand{\pfun}{\rightharpoonup} %\newcommand{\ra}[1]{\kern-1.5ex\xrightarrow{\ \ #1\ \ }\phantom{}\kern-1.5ex} %\newcommand{\ras}[1]{\kern-1.5ex\xrightarrow{\ \ \smash{#1}\ \ }\phantom{}\kern-1.5ex} \newcommand{\da}[1]{\bigg\downarrow\raise.5ex\rlap{\scriptstyle#1}} \newcommand{\ua}[1]{\bigg\uparrow\raise.5ex\rlap{\scriptstyle#1}} % \newcommand{\lift}[1]{#1_{\bot}} \newcommand{\signal}[1]{\tilde{#1}} \newcommand{\ida}{\stackrel{{\sf def}}{=}} \newcommand{\eqn}{\doteq} \newcommand{\deduce}[1]{\sststile{#1}{}} %% \theoremstyle{plain}%default %% \newtheorem{thm}{Theorem}[section] %% \newtheorem{lem}[thm]{Lemma} %% \newtheorem{cor}[thm]{Corollary} %% % %% \theoremstyle{definition} %% \newtheorem{defn}[thm]{Definition} %% % %% \theoremstyle{remark} %% \newtheorem{remark}[thm]{Remark} %% \newtheorem{exercise}[thm]{Exercise} %% See http://u.cs.biu.ac.il/~tsaban/Pdf/LaTeXCommonErrs.pdf %% \newtheorem{prop}[thm]{Proposition} \newcommand{\less}[1]{#1_{<}} \newcommand{\pfn}{\rightharpoonup} \newcommand{\ffn}{\stackrel{{\sf fin}}{\rightharpoonup}} \newcommand{\stkout}[1]{\ifmmode\text{\sout{\ensuremath{#1}}}\else\sout{#1}\fi} % \DeclareMathSymbol{\shortminus}{\mathbin}{AMSa}{"39} \newcommand{\mbf}[1]{\mathbf{#1}} \)
1 Introduction
So far, we have studied lists, which are inductively defined and finite sequences. Infinite sequences, or streams, however, are also very useful. They appear in a variety of applications as traces, progressions, power series, and signals in signal processing, to name a few.
Here are examples of streams:
- \(\id{ones}\)
[1 1 1 ...], the constant stream of 1's.
- \(\id{nats}\)
[0 1 2 3 ...], the stream of naturals.
- \(\id{harmonics}\)
[1 1/2 1/3 1/4 1/5 ...], the stream of harmonic numbers.
- \(\id{facts}\)
[1 1 2 6 24 ...], the stream of factorials
- \(\id{primes}\)
[2 3 5 7 11 ...], the stream of prime numbers.
- \(\id{evens}\)
[0 2 4 6 ...], the stream of evens
- \(\id{trace}(f,a)\)
- \([a\quad f(a)\quad f^{2}(a)\quad \ldots ]\), the trace generated by a function \(f\) on a value \(a\).
There are several ways to model a stream, and we will
explore many of them in this chapter. A stream may be
thought of as a function from naturals to elements of a
domain. But there is another way to think of them: as
infinite sequences. Like a list, a stream is a pair built
using cons, except that the 2nd element (cdr) of the
pair is also a stream, so a stream never ends. Since
streams are like lists, one would expect to have recursive
programs work on lists. But with streams there is no base
case! "How will the recursion ever terminate if you try to
compute with them?", you might ask. It won't, if you try to
compute all the elements of the stream, because the number
of elements in a stream is infinite. However, the stream
can 'reveal' itself one element at a time. You can take
the first few elements of a stream and put them in a list,
or you could drop the first few elements of a stream and
end up with the remaining stream. But you can never get to
the last element, because there is none.
Instead, streams satisfy recurrence equations. Consider
ones, the stream of 1's: \([1\quad 1\quad \ldots]\). It
satisfies the equation.
\[ ones = [1\quad \textbf{.}\quad ones]\]
Here, '.' represents the pairing of a value and a stream
using the elementary pairing operator cons. Equations
such as the one above, where there is no base case involved,
are called co-recursive equations.
Directly translating the co-recursive definition into Racket, however, does not work:
(define ones (cons 1 ones)) ; ones: undefined; ; cannot reference undefined identifier
cons is a function and it tries to evaluate its arguments,
but ones isn't bound yet.
The solution to this problem is another illustration of how functions (closures) may be used to represent data:
(define ones (lambda () (cons 1 ones)))
The earlier error now disappears, because the occurrences of
ones in the body is protected from evaluation via the
closure.
Thus a stream is simply a thunk, i.e., a closure of no arguments. Invoking the closure results in a value and a stream.
(check-pred pair? (ones) "ones-1") (check-eq? (car (ones)) 1 "ones-2") (check-eq? (cdr (ones)) ones "ones-3")
The process of creating a thunk can be abstracted away at
the cost of introducing a new keyword scons which creates
the stream thunk.
(Exercise: explain why scons needs to be a keyword and not
a function.)
(define-syntax scons (syntax-rules () [(scons v s) (lambda () (cons v s))]))
The stream of 1's could now be defined in terms of
scons.
(define 1s (scons 1 1s))
Notice how this definition closely mirrors the co-recursive definition of \(\id{ones}\) presented above.
In the rest of this section, we explore co-recursive definition of different streams.
2 Deconstructing a stream : hd and tl
Mathematically, a stream is a pair of two elements, the first being anything, the second a stream.
Programmatically, a stream is represented as a thunk that
when evaluated returns a pair with a head and a tail, which
is a stream. For a stream \(s\), we will write \(s_0\) for the
head (the zeroth index) and \(s'\) for the tail. In Scheme,
we define hd and tl as the two selectors.
;;; hd: (streamof A) -> A A denotes a type variable (define hd (lambda (s) (car (s)))) ;;; tl: (streamof A) -> (streamof A) (define tl (lambda (s) (cdr (s)))) (define (unpair s) (values (hd s) (tl s)))
3 Unrolling a stream: s-take and s-drop
;;; sref stands for stream-reference ;;; sref nat? -> (streamof A) -> A (define sref (lambda: (n s) (: (nat-reduce (lambda (s n) (tl s)) hd) s n))) (define s0 (sref 0)) (define s1 (sref 1)) (define s2 (sref 2)) (define s3 (sref 3)) ;;; unrolls the a list of the first i elements of a stream and passes ;;; the resultant list and the remaining stream to a continuation k. ;;; unroll: [nat? (streamof A) [(listof A) (streamof A) -> any/c]] -> any/c (define unroll ;; first order (lambda (i s k) (letrec ([loop (lambda (i ls s) (cond [(= i 0) (k ls s)] [else (loop (sub1 i) (cons (hd s) ls) (tl s))]))]) (loop i '() s)))) ;;; s-take: nat? -> (streamof A) -> (listof A) (define s-take (lambda: (n s) (unroll n s (lambda (ls s) (reverse ls))))) (check-equal? (: s-take 0 ones) '() "s-take 0 ones") (check-equal? (: s-take 5 ones) '(1 1 1 1 1) "s-take 5 ones") ;;; Given a natural n and a stream s (curried), returns (tl^n s). ;;; nat? -> (streamof A) -> (streamof A) (define s-drop (lambda: (n s) (unroll n s (lambda (ls s) s)))) (define d0 (s-drop 0)) (define d1 (s-drop 1)) (define d2 (s-drop 2)) (define d3 (s-drop 3)) (define der s-drop) ;; stream derivative (define der1 (s-drop 1)) (define der2 (s-drop 2)) (check-eq? (: s-drop 0 ones) ones "s-drop 0 ones") (check-equal? (hd (: s-drop 1 ones)) 1 "hd of s-drop 0 ones") ;;; A higher-order version of unroll. The state is a pair consisting ;;; of alist of values encountered so far and a stream. (define unroll-ho (lambda (n s k) (: (nat-reduce (lambda (lss n) ;; lss is a list consisting of list of values and a stream. (match-let ([(list ls s) lss]) (list (cons (hd s) ls) (tl s)))) (lambda (lss) (apply k lss))) (list '() s) n))) ;;; s-take: nat? -> (streamof A) -> (listof A) (define s-take-ho (lambda: (n s) (unroll-ho n s (lambda (ls s) (reverse ls))))) (check-equal? (: s-take-ho 0 ones) '() "s-take-ho 0 ones") (check-equal? (: s-take-ho 2 ones) '(1 1) "s-take-ho 2 ones") ;;; Given a natural n and a stream s (curried), returns (tl^n s). ;;; nat? -> (streamof A) -> (streamof A) (define s-drop-ho (lambda: (n s) (unroll-ho n s (lambda (ls s) s)))) (check-eq? (: s-drop-ho 0 ones) ones "s-drop-ho 0 ones") (check-equal? (hd (: s-drop-ho 1 ones)) 1 "hd of s-drop-ho 0 ones")
4 Streams as traces of autonomous systems
The output trace of an autonomous state transition system
\[\pair{X, Y, f:X\rightarrow X, h:X\rightarrow Y}\]
starting at state \(x_0\) is the stream:
\[ [x_0\quad h(f(x_0))\quad h(f^{2}(x_0))\ldots ]\]
This fact may be exploited to define streams as traces of particular autonomous state transition systems.
;;; stream-generate: [f: X->X h: X->Y x0: X] -> (stream-of Y) (define stream-generate (lambda (f h x0) (letrec ([stream-from (lambda (x) (scons (h x) (stream-from (f x))))]) (stream-from x0)))) ;;; nat-stream-generate: [nat? -> Y] -> (stream-of Y) (define nat-stream-generate (lambda (h) (stream-generate add1 h 0))) ;;; nats = [0 1 2 3 ...] ;;; nats: (stream-of nat?) (define nats (nat-stream-generate id)) ;;; +ves = [1 2 3 4 ...] ;;; +ves: (stream-of positive?) (define +ves (nat-stream-generate add1)) ;;; harmonics = [1 1/2 1/3 1/4 ...] ;;; harmonics: (stream-of rational?) (define harmonics (stream-generate add1 (lambda (n) (/ 1 n)) 1)) ;;; evens = [0 2 4 6 ...] ;;; evens: (stream-of nat?) (define evens (nat-stream-generate (lambda (n) (* 2 n)))) ;;; odds = [1 3 5 7 ...] ;;; odds: (stream-of nat?) (define odds (nat-stream-generate (lambda (n) (add1 (* 2 n))))) ;;; (cs v) = [v v v ...] (define cs (lambda (v) (nat-stream-generate (lambda (n) v)))) (define zeroes (cs 0)) (define trues (cs #t)) (define falses (cs #f)) (define voids (cs (void)))
4.1 Trace
strace (stream trace) takes an element \(a:A\) and a
function \(f:A\rightarrow A\) and computes the stream
\([a\quad f(a)\quad f^{2}(a)\quad \ldots]\).
(define (strace f a) (stream-generate f id a)) (check-equal? (: s-take 3 (strace (lambda (x) (cons 'a x)) '())) '(() (a) (a a)) "iterate cons-a nil") ;;; (trace add1 0) is nats (check-equal? (: s-take 5 (strace add1 0)) '(0 1 2 3 4) "iterate add1 0")
5 The empty stream
The empty stream raises an error if any attempt is made to access its components.
(define empty-stream (lambda () (error 'empty-stream "attempt to deconstruct an empty-stream"))) (define empty-stream? (lambda (thing) (eq? thing empty-stream)))
6 Converting lists to streams
;;; finite-stream : any/c -> (listof A) -> (streamof A) (define finite-stream (lambda (ls) (letrec ([loop (lambda (ls s) (cond [(null? ls) s] [#t (loop (rest ls) (scons (first ls) s))]))]) (loop (reverse ls) empty-stream)))) (check-equal? '(a b c) (: s-take 3 (finite-stream '(a b c))) "s-take 3 stream '(a b c) ") (check-exn exn:fail? (lambda () (: s-take 4 (finite-stream '(a b c))) "s-take 4 stream '(a b c)"))
7 Stream zip and map
Most of the stream programming can be captured by a few operators and those derived from them.
7.1 Stream zip and map
We start with stream zip szip, which takes a stream of
functions and streams of arguments, and applies the
functions to the arguments index-wise. Stream map smap is
obtained as a special case by promoting a function to a
constant stream of that function.
;;; [f0 f1 f2 ...] ;;; [a0 a1 a2 ...] ;;; [b0 b1 b2 ...] ;;; [(f0 a0 b0) (f1 a1 b1) ...] ;;; (s@ fs as ...) ;;; (s@: fs s) ;;; szip: (streamof [A ... ->B]) -> [(streamof A) ...] -> (streamof B) (define (szip fs) (lambda ss (scons (apply (hd fs) (map hd ss)) (apply (szip (tl fs)) (map tl ss))))) ;;; smap: [A ... -> B] -> [(streamof A) ...] -> (streamof B) (define (smap f) (szip (cs f))) ;;; s+ : (streamof number?) ... -> (streamof number?) (define s+ (smap +)) ;;; s* : (streamof number?) ... -> (streamof number?) (define s* (smap *)) (check-equal? (: s-take 0 (s+ nats nats)) '() "s+ nats nats s-take 0") (check-equal? (: s-take 5 (s+ nats nats)) '(0 2 4 6 8) "s+ nats nats s-take 5")
8 Streams as traces of non-autonomous state transition systems
A general (non-autonomous) state transition system has a state transition function \(f\) that maps inputs (\(U\)) and states (\(X\)) to states.
\[S = \pair{X, U, f:[U,\ X]\rightarrow X, Y, h:X\rightarrow Y}\]
The state trace of such a system starting in state \(x0\) subjected to the input stream \(u\) may be defined via the recursive equation
\[ t = [t_0\quad .\quad \id{smap}(f)(u,t)] \]
The output trace is simply \(\id{smap}(h)(t)\).
;;; ;;; t0 = e ;;; t1 = (f u0 t0) ; t0--u0--> t1 ;;; t2 = (f u1 t1) = (f u1 (f u0 t0)) ; t0--u0-->t1--u1-->t2 ;;; t3 = (f u2 t2) = (f u2 (f u1 (f u0 t0))) ;;; (t (1+ n)) = (f (s n) (t n)) ;;; [t0 t1 t2 t3 ...] ;;; [u0 u1 u2 u3 ...] ;;; [f f f f f ...] ;;; [t1 t2 t3 t4 ...] ;;; [t0 t1 t2 t3 ...] = [t0 (f u0 t0) (f u1 t1) ...] ;;; stream-trace : [f: [U X] -> X -> (stream-of U) -> X -> (stream-of X)] (define stream-trace (lambda: (f h u x) (letrec ([t (scons x ((smap f) u t))]) (: smap h t))))
;;; sum the preceding elements of a stream. (define (ssum s) (: stream-trace + id s 0)) ;;; multiply the preceding elements of a stream. ;;; Equivalent to factorial. (define (sprod s) (: stream-trace * id s 1)) (check-equal? (: s-take 3 (ssum ones)) '(0 1 2) "ssums-1") (check-equal? (: s-take 4 (sprod ones)) '(1 1 1 1) "sprod-1") (check-equal? (: s-take 5 (sprod +ves)) '(1 1 2 6 24) "sprod-2")
9 Other Progressions
9.1 Arithmetic Progression
The arithmetic progression of \(x\) is the stream \([0\quad x\quad 2x\quad 3x\quad \ldots]\). It satisfies the recurrence \(p = [0\ \textbf{.}\ \overline{x} + p]\). This co-recursive equation translates directly to a program:
;;; ap : number? -> (streamof number?) (define (ap x) (let ([cx (cs x)]) (rec p (scons 0 (s+ cx p)))))
Note the use of the keyword rec. (rec p e) is short
for (letrec ([p e]) p).
We could also have defined it using stream-trace:
(define (ap-ho x) (let ([cx (cs x)]) (: stream-trace + id cx 0)))
9.2 Geometric Progression
The geometric progression of \(x\) is the stream \([1\quad x\quad x^2\quad x^3\quad \ldots]\). It satisfies the recurrence \(p = [1\ \bf{.}\ \overline{x} * p]\). Again, the translation to Scheme is easy:
;;; gp : number? -> (streamof number?) ;;; the sequence [1 x x^2 x^3 ...] ;;; p = [1 x x2 x3 ...] ;;; xs = [x x x x ...] ;;; (s* xs p) = [x x2 x3 x4 ...] ;;; p = (cons 1 (s* xs p)) (define gp (lambda (x) (let ([sx (cs x)]) ;;; p = [1 . sx * p] (rec p (scons 1 (s* sx p))))))
9.3 Factorial as a progression
The progression \([0!\quad 1!\quad 2!\quad \ldots]\) describes the progression of factorials. The recurrence it satisfies and the program to which immediately translates are given below:
;;; facs = [0! 1! 2! 3! ...] ;;; +ves = [1 2 3 4 ...] ;;; (s* +ves facs) = [1! 2! 3! 4! ...] ;;; facs = [1 . (s* +ves facs)] ;;; facs : (stream-of nat?) (define facs (scons 1 (s* +ves facs)))
9.4 Fibonacci
The Hemachandra-Fibonacci series \(F(n) = F(n-1) + F(n-2), n\geq 2\) can be easily modeled using streams.
;;; fib = [0 1 1 2 3 5 8 ...] ;;; fib' = [1 1 2 3 5 8 13 ...] ;;; fib'' = [1 2 3 5 8 13 21 ...] ;;; fib = [0 . fib'] ;;; fib' = [1 . fib''] ;;; fib'' = fib + fib' (define fibs (letrec ([fib (scons 0 fib1)] [fib1 (scons 1 fib2)] [fib2 (s+ fib fib1)]) fib)) (check-equal? (: s-take 6 fibs) '(0 1 1 2 3 5) "fibs-1")
9.5 Partial Sums
Given a numerical series \(s = [a_0\quad a_1\quad a_2\quad \ldots]\), the series \(p\) of partial sums of \(s\) is
\[[0\quad a_0\quad a_0+a_1\quad a_0+a_1+a_2\quad \ldots]\]
s = [a0 a1 a2 a3 ...] p = [0 a0 a0+a1 a0+a1+a2 ...] p+s = [a0 a0+a1 a0+a1+a2 ... ] [0 . p+s] = [0 a0 a0+a1 a0+a1+a2 ...] p = [0 . p+s]
The series \(p\) satisfies the recurrence \[p = [0\ .\ p+s]\]
;;; psums : (streamof number?) -> (streamof number?) (define (psums s) (rec p (scons 0 (s+ p s)))) (check-equal? (: s-take 6 (psums nats)) '(0 0 1 3 6 10) "psums-1")
10 Power Series
A power series is an infinite monomial of the form
\[ a_0\ +\ a_1x\ +\ a_2x^2\ + \ldots\]
The coefficients of a power series form a stream.
\[ a_0\quad \ a_1\quad \ a_2\quad \ldots\]
10.1 Integration
Note that the power series \(a_0\ +\ a_1x\ +\ a_2x^2\ +
\ldots\), when integrated, yields the power series \(c + a_0x\
+\ a_1x/2\ +\ a_2x^2/3\ + \ldots\), where \(c\) is an
integration constant. This is encoded as the stream
\([c\quad a_0\quad a_1/2\quad a_2/3\quad \ldots]\), or
equivalently \([c\quad \textbf{.}\quad h * p]\), where \(p\) is
the original power series, and \(h\) is the harmonic series.
A "proof" and the implementation of the integral is given
below. Note that the function p-integral computes the
indefinite integral modulo the constant \(c\).
;;; p = [a_0 a_1 a_2 a_3 ...] ;;; h = [1/1 1/2 1/3 ...] ;;; p*h = [a_0/1 a_1/2 a_2/3 ...] ;;; [c . p*h] = [c a_0/1 a_1/2 a_2/3 ...] ;;; p = [a_0 a_1 a_2 a_3 ...] ;;; integral p = [c a_0/1 a_1/2 a_2/3 ...] ;;; p-integral of a power series returns the indefinite ;;; integral modulo the integration constant ;;; p-integral : power-series? -> (streamof number?) (define (p-integral p) (s* harmonics p))
10.2 Exponential
The exponential \(e^{x}\) is the power series
\[x^{0}/0!\ +\ x^{1}/1!\ +\ x^2/2!\ + \ldots\]
The integral of \(e^{x}\) is \(e^{x} + c\). Choosing \(x=0\) allows us to infer \(c=1\) and we have \(e^{x} = 1 + \int e^{x}dx\).
;;; power series ;;; ;;; e^{x} = 1 + x + x^{2}/2! + x^{3}/3! + .... ;;; power series ;;; ;;; e^{x} = 1 + x + x^2/2! + x^3/3! + .... ;;; int e^{x} = c + x + x^2/2 + x^3/3! + ... ;;; = c + x + x^2/2! + x^3/3! + ... ;;; taking x = 0 yields c = 1. ;;; e = [1/0! 1/1! 1/2! 1/3! ...] ;;; h = [1/1 1/2 1/3 1/4 ...] ;;; e*h = [1/1! 1/2! 1/3! 1/4! ...] ;;; [1. e*h] = [1/0! 1/1! 1/2! 1/3! 1/4! ...] ;;; pe is the power series of e = [1/0! 1/1! 1/2! 1/3! ...] ;;; pe : power-series? (define (pe) (cons 1 (p-integral pe)))
From now, we consider number streams and their properties.
11 Convolution
Convolution is a common operation found in signal processing, statistics, and linear systems.
Consider two two-way infinite streams \(x\) and \(h\). The convolution \(x*\!*h\) is a two-way infinite stream \(y\) such that
\[y(n) = \sum_{m=-\infty}^{+\infty}h(n-m) * x(m)\]
To understand convolution, consider all pairs of indices \(j,k\) such that \(j+k=i\). Then \(y(i) = \sum\{h(j)x(k) | j+k=i\}\).
For one-way finite streams, i.e., lists, assuming \(x\) and \(h\) are of length \(M\) and \(N\), respectively, the convolution is a list of length \(N+M\). The convolution may be computed in time \(O(N*M)\) time using the identity \(y(j+k) = \sum\{h(j)* x(k)\ |\ j: dom(h), k:dom(x)\}\)
For one-way streams, the computation of convolution may be stated co-recursively as follows:
x = [0 1 2 3 4 5 …]
h = [0 1 2 3 4 5 …]
y = [(00) (01 10) (02 11 20) (03 12 21 30) (04 13 22 31 40) …]
[s0 s1 s2 s3 …] ** [t0 t1 t2 t3 …]) may be computed by observing
s0t'' = [ s0t2 s0t3 s0t4 ...]
s'**t' = [ s1t1 (s1t2 + s2t1) (s1t3 + s2t2 + s3t1) ...]
s''t0 = [ s2t0 s3t0 s3t0 ...]
-----------------------------------------------------------------------
s**t = [s0t0 s0t1+s1t0 (s0t2+s1t1+s2t0) (s0t3+s1t2+s2t1+s3t0) ...]
= [s0t0 . s0t1+s1t0 . s0t''+ s'**t' + s''t0]
;;; +: B ... -> C ;;; *: A A -> B ;;; (convolute + *): (stream-of A) (stream-of A) -> (stream-of C) (define (convolute + *) (rec p (lambda (s t) (let* ([s0 (hd s)] [t0 (hd t)] [ds (tl s)] [dt (tl t)] [s1 (hd ds)] [t1 (hd dt)] [dds (tl ds)] [ddt (tl dt)]) (scons (+ (* s0 t0)) (scons (+ (* s0 t1) (* s1 t0)) ((smap +) (: smap (lambda (x) (* s0 x)) ddt) (p ds dt) (: smap (lambda (x) (* x t0)) dds))))))))
Some useful convolutions are:
(define ** (convolute + *)) (define power-product (convolute list cons)) (check-equal? (: s-take 5 (power-product nats nats)) '(((0 . 0)) ((0 . 1) (1 . 0)) ((0 . 2) ((1 . 1)) (2 . 0)) ((0 . 3) ((1 . 2) (2 . 1)) (3 . 0)) ((0 . 4) ((1 . 3) ((2 . 2)) (3 . 1)) (4 . 0))) "power-product nats nats")
12 Bibliographic notes
Streams form the basis of what we call Reactive Programming today. Abelson and Sussman's SICP book\cite{sicp-1984} in Section 3.5 of the book. Streams are a natural data structure in lazy functional languages like Haskell and Clean. Racket also supports streams. From a mathematical point of view, streams are best studied as co-algebras with stream bisimulation as the fundamental reasoning principle. Papers by Niqui and Rutten\cite{niqui-rutten-2013} and Hinze\cite{Hin10Rea} offer a more advanced and modern treatment on streams.