1module Std.List
2
3import Std.Foundation
4
5-- Structural lists (Language Platform PRD §28.2 Collections, LP-802).
6--
7-- This is the small structural sequence: cheap to build, cheap to walk, and
8-- shared rather than copied — appending to a list keeps the original intact
9-- because the tail is shared, which is the sharing property §28.4 requires.
10-- Iteration is deterministic by construction: a list has one order, the one
11-- it was built in.
12--
13-- Asymptotic contract (§28.4 requires it to be explicit):
14-- stdListCons O(1)
15-- stdListHead O(1)
16-- stdListLength O(n)
17-- stdListAppend O(n) in the left list, sharing the right one
18-- stdListReverse O(n)
19-- stdListMap O(n)
20-- stdListFold O(n)
21-- stdListFoldFromHead O(n)
22-- stdListZipWith O(min(n, m))
23-- stdListIndex O(i)
24family StdList : Type 0
25parameter erased stdListElement : Type 0
26constructor StdListEmpty
27constructor StdListCons
28field unrestricted stdListHeadValue : stdListElement
29recursive unrestricted stdListTailValue
30
31end-family
32
33-- The number of elements.
34def stdListLength =
35 (lambda erased element : Type 0 . unrestricted values : (family StdList element) .
36 eliminate
37 StdList
38 (lambda unrestricted current : (family StdList element) . Nat)
39 values
40 (branch StdListEmpty . 0)
41 (branch StdListCons head tail induction . succ induction))
42
43-- The first element, or the supplied default for an empty list.
44def stdListHeadOr =
45 (lambda erased element : Type 0 .
46 unrestricted fallback : element .
47 unrestricted values : (family StdList element) .
48 eliminate
49 StdList
50 (lambda unrestricted current : (family StdList element) . element)
51 values
52 (branch StdListEmpty . fallback)
53 (branch StdListCons head tail induction . head))
54
55-- The first element as an option, so the empty case is visible in the type.
56def stdListHead =
57 (lambda erased element : Type 0 . unrestricted values : (family StdList element) .
58 eliminate
59 StdList
60 (lambda unrestricted current : (family StdList element) . family StdOption element)
61 values
62 (branch StdListEmpty . constructor StdOption StdNone element)
63 (branch StdListCons head tail induction . constructor StdOption StdSome element head))
64
65-- Everything after the first element; the empty list has an empty tail.
66def stdListTail =
67 (lambda erased element : Type 0 . unrestricted values : (family StdList element) .
68 eliminate
69 StdList
70 (lambda unrestricted current : (family StdList element) . family StdList element)
71 values
72 (branch StdListEmpty . constructor StdList StdListEmpty element)
73 (branch StdListCons head tail induction . tail))
74
75-- Is the list empty?
76def stdListIsEmpty =
77 (lambda erased element : Type 0 . unrestricted values : (family StdList element) .
78 eliminate
79 StdList
80 (lambda unrestricted current : (family StdList element) . family StdBool)
81 values
82 (branch StdListEmpty . constructor StdBool StdTrue)
83 (branch StdListCons head tail induction . constructor StdBool StdFalse))
84
85-- The left list followed by the right one. The right list is SHARED, not
86-- copied: only the left spine is rebuilt.
87def stdListAppend =
88 (lambda erased element : Type 0 .
89 unrestricted left : (family StdList element) .
90 unrestricted right : (family StdList element) .
91 eliminate
92 StdList
93 (lambda unrestricted current : (family StdList element) . family StdList element)
94 left
95 (branch StdListEmpty . right)
96 (branch
97 StdListCons
98 head
99 tail
100 induction
101 .
102 constructor StdList StdListCons element head induction))
103
104-- The list in the opposite order.
105def stdListReverse =
106 (lambda erased element : Type 0 . unrestricted values : (family StdList element) .
107 app
108 (eliminate
109 StdList
110 (lambda unrestricted current : (family StdList element) .
111 pi unrestricted accumulator : (family StdList element) .
112 family StdList element)
113 values
114 (branch
115 StdListEmpty
116 .
117 lambda
118 unrestricted
119 accumulator
120 :
121 (family StdList element)
122 .
123 accumulator)
124 (branch
125 StdListCons
126 head
127 tail
128 induction
129 .
130 lambda
131 unrestricted
132 accumulator
133 :
134 (family StdList element)
135 .
136 induction (constructor StdList StdListCons element head accumulator)))
137 (constructor StdList StdListEmpty element))
138
139-- Every element transformed, in order.
140def stdListMap =
141 (lambda erased element : Type 0 .
142 erased target : Type 0 .
143 unrestricted transform : (pi unrestricted value : element . target) .
144 unrestricted values : (family StdList element) .
145 eliminate
146 StdList
147 (lambda unrestricted current : (family StdList element) . family StdList target)
148 values
149 (branch StdListEmpty . constructor StdList StdListEmpty target)
150 (branch
151 StdListCons
152 head
153 tail
154 induction
155 .
156 constructor StdList StdListCons target (transform head) induction))
157
158-- Fold from the right: `stdListFold f z [a, b] = f a (f b z)`.
159def stdListFold =
160 (lambda erased element : Type 0 .
161 erased accumulator : Type 0 .
162 unrestricted step : (pi unrestricted value : element . unrestricted carried : accumulator . accumulator) .
163 unrestricted initial : accumulator .
164 unrestricted values : (family StdList element) .
165 eliminate
166 StdList
167 (lambda unrestricted current : (family StdList element) . accumulator)
168 values
169 (branch StdListEmpty . initial)
170 (branch StdListCons head tail induction . step head induction))
171
172-- Fold from the head: `step (... (step (step initial x0) x1) ...) xn`.
173-- stdListFold visits the LAST element first (its step sees the folded tail);
174-- this visits the FIRST element first and threads the accumulator forward,
175-- which is the order a floating-point accumulation or a reverse-time pass over
176-- a newest-first history must respect (the results differ when the step does
177-- not associate, e.g. f32 addition). The list is eliminated into a function of
178-- the accumulator, so the recursion is still structural.
179def stdListFoldFromHead =
180 (lambda erased element : Type 0 .
181 erased accumulator : Type 0 .
182 unrestricted step : (pi unrestricted carried : accumulator . unrestricted value : element . accumulator) .
183 unrestricted initial : accumulator .
184 unrestricted values : (family StdList element) .
185 app
186 (eliminate
187 StdList
188 (lambda unrestricted current : (family StdList element) .
189 pi unrestricted carried : accumulator .
190 accumulator)
191 values
192 (branch StdListEmpty . lambda unrestricted carried : accumulator . carried)
193 (branch
194 StdListCons
195 head
196 tail
197 induction
198 .
199 lambda
200 unrestricted
201 carried
202 :
203 accumulator
204 .
205 induction (step carried head)))
206 initial)
207
208-- Combine two lists position by position, keeping their order; the result is
209-- as long as the SHORTER list (the rest of the longer one is dropped -- callers
210-- that need equal lengths must establish them). The left list is eliminated
211-- into a function of the right one, so both spines are walked together.
212def stdListZipWith =
213 (lambda erased left : Type 0 .
214 erased right : Type 0 .
215 erased result : Type 0 .
216 unrestricted combine : (pi unrestricted l : left . unrestricted r : right . result) .
217 unrestricted lefts : (family StdList left) .
218 unrestricted rights : (family StdList right) .
219 app
220 (eliminate
221 StdList
222 (lambda unrestricted current : (family StdList left) .
223 pi unrestricted others : (family StdList right) .
224 family StdList result)
225 lefts
226 (branch
227 StdListEmpty
228 .
229 lambda
230 unrestricted
231 others
232 :
233 (family StdList right)
234 .
235 constructor StdList StdListEmpty result)
236 (branch
237 StdListCons
238 head
239 tail
240 induction
241 .
242 lambda
243 unrestricted
244 others
245 :
246 (family StdList right)
247 .
248 eliminate
249 StdList
250 (lambda unrestricted inner : (family StdList right) . family StdList result)
251 others
252 (branch StdListEmpty . constructor StdList StdListEmpty result)
253 (branch
254 StdListCons
255 otherHead
256 otherTail
257 otherInduction
258 .
259 constructor StdList StdListCons result (combine head otherHead) (induction otherTail))))
260 rights)
261
262-- The first `count` elements (all of them when the list is shorter); the
263-- structural recursion is on the count, the list is eliminated one cell at a
264-- time under it (Language & Testing Evolution L5: shrinkers halve lists).
265def stdListTake =
266 (lambda erased element : Type 0 .
267 unrestricted count : Nat .
268 unrestricted values : (family StdList element) .
269 app
270 (nat-eliminate
271 (lambda unrestricted current : Nat . pi unrestricted remaining : (family StdList element) .
272 family StdList element)
273 (lambda unrestricted remaining : (family StdList element) .
274 constructor StdList StdListEmpty element)
275 (lambda unrestricted predecessor : Nat .
276 unrestricted induction : (pi unrestricted remaining : (family StdList element) . family StdList element) .
277 unrestricted remaining : (family StdList element) .
278 eliminate
279 StdList
280 (lambda unrestricted current : (family StdList element) . family StdList element)
281 remaining
282 (branch StdListEmpty . constructor StdList StdListEmpty element)
283 (branch
284 StdListCons
285 head
286 tail
287 tailInduction
288 .
289 constructor StdList StdListCons element head (induction tail)))
290 count)
291 values)
292
293-- Everything after the first `count` elements.
294def stdListDrop =
295 (lambda erased element : Type 0 .
296 unrestricted count : Nat .
297 unrestricted values : (family StdList element) .
298 app
299 (nat-eliminate
300 (lambda unrestricted current : Nat . pi unrestricted remaining : (family StdList element) .
301 family StdList element)
302 (lambda unrestricted remaining : (family StdList element) . remaining)
303 (lambda unrestricted predecessor : Nat .
304 unrestricted induction : (pi unrestricted remaining : (family StdList element) . family StdList element) .
305 unrestricted remaining : (family StdList element) .
306 eliminate
307 StdList
308 (lambda unrestricted current : (family StdList element) . family StdList element)
309 remaining
310 (branch StdListEmpty . constructor StdList StdListEmpty element)
311 (branch StdListCons head tail tailInduction . induction tail))
312 count)
313 values)
314
315-- The element at a position, as an option: an index past the end is absent,
316-- never an error and never a wrong element.
317def stdListIndex =
318 (lambda erased element : Type 0 .
319 unrestricted values : (family StdList element) .
320 unrestricted position : Nat .
321 app
322 (eliminate
323 StdList
324 (lambda unrestricted current : (family StdList element) . pi unrestricted remaining : Nat .
325 family StdOption element)
326 values
327 (branch
328 StdListEmpty
329 .
330 lambda
331 unrestricted
332 remaining
333 :
334 Nat
335 .
336 constructor StdOption StdNone element)
337 (branch
338 StdListCons
339 head
340 tail
341 induction
342 .
343 lambda
344 unrestricted
345 remaining
346 :
347 Nat
348 .
349 nat-eliminate
350 (lambda unrestricted current : Nat . family StdOption element)
351 (constructor StdOption StdSome element head)
352 (lambda unrestricted predecessor : Nat .
353 unrestricted inner : (family StdOption element) .
354 induction (nat-subtract remaining 1))
355 -- a branch on zero, not a recursion on `remaining`: a
356 -- strict evaluator would evaluate every smaller position's
357 -- lookup, doubling the cost with each position
358 (nat-less-than 0 remaining)))
359 position)
360
361-- A list of the naturals below a bound, in increasing order: `[0, 1, ..., n-1]`.
362def stdListNaturalsBelow =
363 (lambda unrestricted bound : Nat .
364 nat-eliminate
365 (lambda unrestricted current : Nat . family StdList Nat)
366 (constructor StdList StdListEmpty Nat)
367 (lambda unrestricted predecessor : Nat . unrestricted induction : (family StdList Nat) .
368 stdListAppend
369 Nat
370 induction
371 (constructor StdList StdListCons Nat predecessor (constructor StdList StdListEmpty Nat)))
372 bound)
373
374-- Structural equality of two lists of naturals: same length, same elements in
375-- the same order. The first list is eliminated into a FUNCTION of the second,
376-- so the recursion walks both spines together. A proof about two computed
377-- lists states this closed verdict rather than an equation between them: an
378-- equation between two lists built by the same builder is compared
379-- symbolically first (the builders' element functions, under a binder),
380-- which costs far more than computing them (Proof.CheckedHMMATile's instance
381-- words: 580 s against 34 s).
382def stdListNaturalEqual =
383 (lambda unrestricted expected : (family StdList Nat) .
384 unrestricted actual : (family StdList Nat) .
385 app
386 (eliminate
387 StdList
388 (lambda unrestricted current : (family StdList Nat) .
389 pi unrestricted other : (family StdList Nat) .
390 family StdBool)
391 expected
392 (branch
393 StdListEmpty
394 .
395 lambda
396 unrestricted
397 other
398 :
399 (family StdList Nat)
400 .
401 stdListIsEmpty Nat other)
402 (branch
403 StdListCons
404 head
405 tail
406 induction
407 .
408 lambda
409 unrestricted
410 other
411 :
412 (family StdList Nat)
413 .
414 eliminate
415 StdList
416 (lambda unrestricted current : (family StdList Nat) . family StdBool)
417 other
418 (branch StdListEmpty . constructor StdBool StdFalse)
419 (branch
420 StdListCons
421 otherHead
422 otherTail
423 otherInduction
424 .
425 stdBoolAnd
426 (stdOrderIsEqual (stdOrderCompareNatural head otherHead))
427 (induction otherTail))))
428 actual)The compiler supplied declaration spans and resolved links from this source snapshot. This page does not assert that this file belongs to a checked closure.