Source/Packages

Std.List

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

428 lines21 declarations14.7 KiBSHA-256 1d350bdfe159

def · lines 382–428

stdListNaturalEqual

Full file
Structural equality of two lists of naturals: same length, same elements in the same order. The first list is eliminated into a FUNCTION of the second, so the recursion walks both spines together. A proof about two computed lists states this closed verdict rather than an equation between them: an equation between two lists built by the same builder is compared symbolically first (the builders' element functions, under a binder), which costs far more than computing them (Proof.CheckedHMMATile's instance 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.