Source/Packages

Std.List

packages/foundation/standard/src/Std/List.alpha

428 lines21 declarations14.7 KiBSHA-256 1d350bdfe159

Complete file · line 159

List.alpha

Definition view
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.