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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
|
signature STREAM = sig
type 'element stream
val create:
(unit -> ('element * 'element stream) option)
-> 'element stream
val empty: unit -> 'element stream
val cons: 'element * 'element stream -> 'element stream
val unfold:
('seed -> ('fruit * 'seed) option)
-> 'seed
-> 'fruit stream
val getItem: 'element stream -> ('element * 'element stream) option
val isEmpty: 'element stream -> bool
val fold:
('element * 'accumulation -> 'accumulation)
-> 'accumulation
-> 'element stream
-> 'accumulation
val length: 'element stream -> int
val rev: 'element stream -> 'element stream
val map: ('input -> 'output) -> 'input stream -> 'output stream
val mapPartial:
('input -> 'output option)
-> 'input stream
-> 'output stream
val app: ('element -> unit) -> 'element stream -> unit
val toList: 'element stream -> 'element list
val fromList: 'element list -> 'element stream
val toVector: 'element stream -> 'element vector
val fromVector: 'element vector -> 'element stream
val fromVectorSlice: 'element VectorSlice.slice -> 'element stream
val toArray: 'element stream -> 'element array
val fromArray: 'element array -> 'element stream
val fromArraySlice: 'element ArraySlice.slice -> 'element stream
val fromString: string -> char stream
val fromSubstring: Substring.substring -> char stream
val toString: char stream -> string
val fromTextInstream: TextIO.instream -> char stream
val append: 'element stream * 'element stream -> 'element stream
val concat: 'element stream stream -> 'element stream
val hd: 'element stream -> 'element
val tl: 'element stream -> 'element stream
val find: ('element -> bool) -> 'element stream -> 'element option
val filter: ('element -> bool) -> 'element stream -> 'element stream
val exists: ('element -> bool) -> 'element stream -> bool
val all: ('element -> bool) -> 'element stream -> bool
val partition:
('element -> bool)
-> 'element stream
-> 'element stream * 'element stream
val take: ('element -> bool) -> 'element stream -> 'element stream
val drop: ('element -> bool) -> 'element stream -> 'element stream
val split:
('element -> bool)
-> 'element stream
-> 'element stream * 'element stream
val trim: 'element stream * int -> 'element stream
val tokens:
('element -> bool)
-> 'element stream
-> 'element stream stream
val fields:
('element -> bool)
-> 'element stream
-> 'element stream stream
end
structure Stream :> STREAM = struct
datatype 'element stream =
T of unit -> ('element * 'element stream) option
fun create function = T function
fun empty () = create (fn () => NONE)
fun cons headAndTail = create (fn () => SOME headAndTail)
fun unfold harvest seed = create (fn () =>
case harvest seed of
NONE => NONE
| SOME (fruit, seed) => SOME (
fruit
, unfold harvest seed
)
)
fun getItem (T function) = function ()
fun fromList list = unfold List.getItem list
fun toList stream = case getItem stream of
NONE => nil
| SOME (head, tail) => head :: toList tail
fun fold accumulate accumulation stream = case getItem stream of
NONE => accumulation
| SOME (head, tail) =>
fold accumulate (accumulate (head, accumulation)) tail
fun length stream = fold (fn (_, count) => count + 1) 0 stream
fun rev stream = fromList (fold op :: nil stream)
fun map transform stream = unfold (fn stream =>
case getItem stream of
NONE => NONE
| SOME (head, tail) => SOME (
transform head
, tail
)
) stream
fun app execute stream =
fold (fn (element, ()) => execute element) () stream
fun fromVectorSlice slice = unfold VectorSlice.getItem slice
fun fromVector vector = fromVectorSlice (VectorSlice.full vector)
fun fromArraySlice slice = unfold ArraySlice.getItem slice
fun fromArray array = fromArraySlice (ArraySlice.full array)
fun fromSubstring substring = unfold Substring.getc substring
fun fromString string = fromSubstring (Substring.full string)
local
fun withTabulate tabulate stream =
let
val position = ref stream
in
tabulate (
length stream
, fn _ => case getItem (!position) of
NONE => raise Fail "Stream"
| SOME (head, tail) => (
position := tail
; head
)
)
end
in
fun toVector stream = withTabulate Vector.tabulate stream
fun toArray stream = withTabulate Array.tabulate stream
fun toString stream = withTabulate CharVector.tabulate stream
end
fun fromTextInstream instream =
unfold TextIO.StreamIO.input1 (TextIO.getInstream instream)
fun append (first, second) = create (fn () =>
case getItem first of
NONE => getItem second
| SOME (head, tail) => SOME (
head
, append (tail, second)
)
)
fun concat streams = create (fn () =>
case getItem streams of
NONE => NONE
| SOME (head, tail) =>
getItem (append (head, concat tail))
)
fun hd stream = case getItem stream of
NONE => raise Empty
| SOME (head, _) => head
fun tl stream = case getItem stream of
NONE => raise Empty
| SOME (_, tail) => tail
fun last stream = hd (rev stream)
fun drop (stream, count) =
if count < 0 then raise Subscript
else if count = 0 then stream
else case getItem stream of
NONE => raise Subscript
| SOME (_, tail) => drop (tail, count - 1)
fun nth streamAndOffset = case getItem (drop streamAndOffset) of
NONE => raise Subscript
| SOME (head, _) => head
fun mapPartial transform stream = create (fn () =>
case getItem stream of
NONE => NONE
| SOME (head, tail) => case transform head of
NONE => getItem (mapPartial transform tail)
| SOME element => SOME (
element
, mapPartial transform tail
)
)
fun find test stream = case getItem stream of
NONE => NONE
| SOME (head, tail) =>
if test head then SOME head
else find test tail
fun filter test stream = unfold (fn stream =>
case getItem stream of
NONE => NONE
| someHeadAndTail as (SOME (head, tail)) =>
if test head then someHeadAndTail
else getItem (filter test tail)
) stream
fun exists test stream = case find test stream of
NONE => false
| SOME _ => true
fun all test stream = not (exists (not o test) stream)
fun partition test stream =
let
val withResult = map (fn element =>
(test element, element)
) stream
in (
mapPartial (fn (result, element) =>
if result then SOME element
else NONE
) withResult
, mapPartial (fn (result, element) =>
if result then NONE
else SOME element
) withResult
) end
fun take test stream = create (fn () =>
case getItem stream of
NONE => NONE
| SOME (head, tail) =>
if test head then SOME (head, take test tail)
else NONE
)
fun drop test stream = create (fn () =>
case getItem stream of
NONE => NONE
| someHeadAndTail as (SOME (head, tail)) =>
if test head then getItem (drop test tail)
else someHeadAndTail
)
fun split test stream = (take test stream, drop test stream)
fun trim (stream, count) =
if count <= 0 then stream
else create (fn () =>
case getItem stream of
NONE => NONE
| SOME (_, tail) =>
getItem (trim (tail, count - 1))
)
fun isEmpty stream = case getItem stream of
NONE => true
| SOME _ => false
fun tokens isSeparator stream = unfold (fn stream =>
let
val skipped = drop isSeparator stream
in
if isEmpty skipped then NONE
else SOME (split (not o isSeparator) skipped)
end
) stream
fun fields isSeparator stream = unfold (fn stream =>
if isEmpty stream then NONE
else SOME (
take (not o isSeparator) stream
, trim (drop (not o isSeparator) stream, 1)
)
) stream
end
|
