1 (* ========================================================================= *) |
|
2 (* A POSSIBLY-INFINITE STREAM DATATYPE FOR ML *) |
|
3 (* Copyright (c) 2001-2006 Joe Hurd, distributed under the BSD License *) |
|
4 (* ========================================================================= *) |
|
5 |
|
6 structure Stream :> Stream = |
|
7 struct |
|
8 |
|
9 val K = Useful.K; |
|
10 |
|
11 val pair = Useful.pair; |
|
12 |
|
13 val funpow = Useful.funpow; |
|
14 |
|
15 (* ------------------------------------------------------------------------- *) |
|
16 (* The datatype declaration encapsulates all the primitive operations *) |
|
17 (* ------------------------------------------------------------------------- *) |
|
18 |
|
19 datatype 'a stream = |
|
20 NIL |
|
21 | CONS of 'a * (unit -> 'a stream); |
|
22 |
|
23 (* ------------------------------------------------------------------------- *) |
|
24 (* Stream constructors *) |
|
25 (* ------------------------------------------------------------------------- *) |
|
26 |
|
27 fun repeat x = let fun rep () = CONS (x,rep) in rep () end; |
|
28 |
|
29 fun count n = CONS (n, fn () => count (n + 1)); |
|
30 |
|
31 fun funpows f x = CONS (x, fn () => funpows f (f x)); |
|
32 |
|
33 (* ------------------------------------------------------------------------- *) |
|
34 (* Stream versions of standard list operations: these should all terminate *) |
|
35 (* ------------------------------------------------------------------------- *) |
|
36 |
|
37 fun cons h t = CONS (h,t); |
|
38 |
|
39 fun null NIL = true | null (CONS _) = false; |
|
40 |
|
41 fun hd NIL = raise Empty |
|
42 | hd (CONS (h,_)) = h; |
|
43 |
|
44 fun tl NIL = raise Empty |
|
45 | tl (CONS (_,t)) = t (); |
|
46 |
|
47 fun hdTl s = (hd s, tl s); |
|
48 |
|
49 fun singleton s = CONS (s, K NIL); |
|
50 |
|
51 fun append NIL s = s () |
|
52 | append (CONS (h,t)) s = CONS (h, fn () => append (t ()) s); |
|
53 |
|
54 fun map f = |
|
55 let |
|
56 fun m NIL = NIL |
|
57 | m (CONS (h, t)) = CONS (f h, fn () => m (t ())) |
|
58 in |
|
59 m |
|
60 end; |
|
61 |
|
62 fun maps f = |
|
63 let |
|
64 fun mm _ NIL = NIL |
|
65 | mm s (CONS (x, xs)) = |
|
66 let |
|
67 val (y, s') = f x s |
|
68 in |
|
69 CONS (y, fn () => mm s' (xs ())) |
|
70 end |
|
71 in |
|
72 mm |
|
73 end; |
|
74 |
|
75 fun zipwith f = |
|
76 let |
|
77 fun z NIL _ = NIL |
|
78 | z _ NIL = NIL |
|
79 | z (CONS (x,xs)) (CONS (y,ys)) = |
|
80 CONS (f x y, fn () => z (xs ()) (ys ())) |
|
81 in |
|
82 z |
|
83 end; |
|
84 |
|
85 fun zip s t = zipwith pair s t; |
|
86 |
|
87 fun take 0 _ = NIL |
|
88 | take n NIL = raise Subscript |
|
89 | take 1 (CONS (x,_)) = CONS (x, K NIL) |
|
90 | take n (CONS (x,xs)) = CONS (x, fn () => take (n - 1) (xs ())); |
|
91 |
|
92 fun drop n s = funpow n tl s handle Empty => raise Subscript; |
|
93 |
|
94 (* ------------------------------------------------------------------------- *) |
|
95 (* Stream versions of standard list operations: these might not terminate *) |
|
96 (* ------------------------------------------------------------------------- *) |
|
97 |
|
98 local |
|
99 fun len n NIL = n |
|
100 | len n (CONS (_,t)) = len (n + 1) (t ()); |
|
101 in |
|
102 fun length s = len 0 s; |
|
103 end; |
|
104 |
|
105 fun exists pred = |
|
106 let |
|
107 fun f NIL = false |
|
108 | f (CONS (h,t)) = pred h orelse f (t ()) |
|
109 in |
|
110 f |
|
111 end; |
|
112 |
|
113 fun all pred = not o exists (not o pred); |
|
114 |
|
115 fun filter p NIL = NIL |
|
116 | filter p (CONS (x,xs)) = |
|
117 if p x then CONS (x, fn () => filter p (xs ())) else filter p (xs ()); |
|
118 |
|
119 fun foldl f = |
|
120 let |
|
121 fun fold b NIL = b |
|
122 | fold b (CONS (h,t)) = fold (f (h,b)) (t ()) |
|
123 in |
|
124 fold |
|
125 end; |
|
126 |
|
127 fun concat NIL = NIL |
|
128 | concat (CONS (NIL, ss)) = concat (ss ()) |
|
129 | concat (CONS (CONS (x, xs), ss)) = |
|
130 CONS (x, fn () => concat (CONS (xs (), ss))); |
|
131 |
|
132 fun mapPartial f = |
|
133 let |
|
134 fun mp NIL = NIL |
|
135 | mp (CONS (h,t)) = |
|
136 case f h of |
|
137 NONE => mp (t ()) |
|
138 | SOME h' => CONS (h', fn () => mp (t ())) |
|
139 in |
|
140 mp |
|
141 end; |
|
142 |
|
143 fun mapsPartial f = |
|
144 let |
|
145 fun mm _ NIL = NIL |
|
146 | mm s (CONS (x, xs)) = |
|
147 let |
|
148 val (yo, s') = f x s |
|
149 val t = mm s' o xs |
|
150 in |
|
151 case yo of NONE => t () | SOME y => CONS (y, t) |
|
152 end |
|
153 in |
|
154 mm |
|
155 end; |
|
156 |
|
157 (* ------------------------------------------------------------------------- *) |
|
158 (* Stream operations *) |
|
159 (* ------------------------------------------------------------------------- *) |
|
160 |
|
161 fun memoize NIL = NIL |
|
162 | memoize (CONS (h,t)) = CONS (h, Lazy.memoize (fn () => memoize (t ()))); |
|
163 |
|
164 local |
|
165 fun toLst res NIL = rev res |
|
166 | toLst res (CONS (x, xs)) = toLst (x :: res) (xs ()); |
|
167 in |
|
168 fun toList s = toLst [] s; |
|
169 end; |
|
170 |
|
171 fun fromList [] = NIL |
|
172 | fromList (x :: xs) = CONS (x, fn () => fromList xs); |
|
173 |
|
174 fun toString s = implode (toList s); |
|
175 |
|
176 fun fromString s = fromList (explode s); |
|
177 |
|
178 fun toTextFile {filename = f} s = |
|
179 let |
|
180 val (h,close) = |
|
181 if f = "-" then (TextIO.stdOut, K ()) |
|
182 else (TextIO.openOut f, TextIO.closeOut) |
|
183 |
|
184 fun toFile NIL = () |
|
185 | toFile (CONS (x,y)) = (TextIO.output (h,x); toFile (y ())) |
|
186 |
|
187 val () = toFile s |
|
188 in |
|
189 close h |
|
190 end; |
|
191 |
|
192 fun fromTextFile {filename = f} = |
|
193 let |
|
194 val (h,close) = |
|
195 if f = "-" then (TextIO.stdIn, K ()) |
|
196 else (TextIO.openIn f, TextIO.closeIn) |
|
197 |
|
198 fun strm () = |
|
199 case TextIO.inputLine h of |
|
200 NONE => (close h; NIL) |
|
201 | SOME s => CONS (s,strm) |
|
202 in |
|
203 memoize (strm ()) |
|
204 end; |
|
205 |
|
206 end |
|