Documentation

Init.Data.List.Impl

Tail recursive implementations for List definitions. #

Many of the proofs require theorems about Array, so these are in a separate file to minimize imports.

If you import Init.Data.List.Basic but do not import this file, then at runtime you will get non-tail recursive versions of the following definitions.

Basic List operations. #

The following operations are already tail-recursive, and do not need @[csimp] replacements: get, foldl, beq, isEqv, reverse, elem (and hence contains), drop, dropWhile, partition, isPrefixOf, isPrefixOf?, find?, findSome?, lookup, any (and hence or), all (and hence and) , range, eraseDups, eraseReps, span, splitBy.

The following operations are still missing @[csimp] replacements: concat, zipWithAll.

The following operations are not recursive to begin with (or are defined in terms of recursive primitives): isEmpty, isSuffixOf, isSuffixOf?, rotateLeft, rotateRight, insert, zip, enum, min?, max?, and removeAll.

The following operations were already given @[csimp] replacements in Init/Data/List/Basic.lean: length, map, filter, replicate, leftPad, unzip, range', iota, intersperse.

The following operations are given @[csimp] replacements below: set, filterMap, foldr, append, bind, join, take, takeWhile, dropLast, replace, modify, erase, eraseIdx, zipWith, enumFrom, and intercalate.

set #

@[inline]
def List.setTR {α : Type u_1} (l : List α) (n : Nat) (a : α) :
List α

Tail recursive version of List.set.

Equations
Instances For
    def List.setTR.go {α : Type u_1} (l : List α) (a : α) :
    List αNatArray αList α

    Auxiliary for setTR: setTR.go l a xs n acc = acc.toList ++ set xs a, unless n ≥ l.length in which case it returns l

    Equations
    Instances For
      theorem List.set_eq_setTR.go (α : Type u_1) (l : List α) (a : α) (acc : Array α) (xs : List α) (n : Nat) :
      l = acc.toList ++ xsList.setTR.go l a xs n acc = acc.toList ++ xs.set n a

      filterMap #

      @[inline]
      def List.filterMapTR {α : Type u_1} {β : Type u_2} (f : αOption β) (l : List α) :
      List β

      Tail recursive version of filterMap.

      Equations
      Instances For
        @[specialize #[]]
        def List.filterMapTR.go {α : Type u_1} {β : Type u_2} (f : αOption β) :
        List αArray βList β

        Auxiliary for filterMap: filterMap.go f l = acc.toList ++ filterMap f l

        Equations
        Instances For
          theorem List.filterMap_eq_filterMapTR.go (α : Type u_2) (β : Type u_1) (f : αOption β) (as : List α) (acc : Array β) :
          List.filterMapTR.go f as acc = acc.toList ++ List.filterMap f as

          foldr #

          @[specialize #[]]
          def List.foldrTR {α : Type u_1} {β : Type u_2} (f : αββ) (init : β) (l : List α) :
          β

          Tail recursive version of List.foldr.

          Equations
          Instances For

            flatMap #

            @[inline]
            def List.flatMapTR {α : Type u_1} {β : Type u_2} (as : List α) (f : αList β) :
            List β

            Tail recursive version of List.flatMap.

            Equations
            Instances For
              @[specialize #[]]
              def List.flatMapTR.go {α : Type u_1} {β : Type u_2} (f : αList β) :
              List αArray βList β

              Auxiliary for flatMap: flatMap.go f as = acc.toList ++ bind f as

              Equations
              Instances For
                theorem List.flatMap_eq_flatMapTR.go (α : Type u_2) (β : Type u_1) (f : αList β) (as : List α) (acc : Array β) :
                List.flatMapTR.go f as acc = acc.toList ++ as.flatMap f

                flatten #

                @[inline]
                def List.flattenTR {α : Type u_1} (l : List (List α)) :
                List α

                Tail recursive version of List.flatten.

                Equations
                • l.flattenTR = l.flatMapTR id
                Instances For

                  Sublists #

                  take #

                  @[inline]
                  def List.takeTR {α : Type u_1} (n : Nat) (l : List α) :
                  List α

                  Tail recursive version of List.take.

                  Equations
                  Instances For
                    @[specialize #[]]
                    def List.takeTR.go {α : Type u_1} (l : List α) :
                    List αNatArray αList α

                    Auxiliary for take: take.go l xs n acc = acc.toList ++ take n xs, unless n ≥ xs.length in which case it returns l.

                    Equations
                    Instances For

                      takeWhile #

                      @[inline]
                      def List.takeWhileTR {α : Type u_1} (p : αBool) (l : List α) :
                      List α

                      Tail recursive version of List.takeWhile.

                      Equations
                      Instances For
                        @[specialize #[]]
                        def List.takeWhileTR.go {α : Type u_1} (p : αBool) (l : List α) :
                        List αArray αList α

                        Auxiliary for takeWhile: takeWhile.go p l xs acc = acc.toList ++ takeWhile p xs, unless no element satisfying p is found in xs in which case it returns l.

                        Equations
                        Instances For

                          dropLast #

                          @[inline]
                          def List.dropLastTR {α : Type u_1} (l : List α) :
                          List α

                          Tail recursive version of dropLast.

                          Equations
                          • l.dropLastTR = l.toArray.pop.toList
                          Instances For

                            Manipulating elements #

                            replace #

                            @[inline]
                            def List.replaceTR {α : Type u_1} [BEq α] (l : List α) (b : α) (c : α) :
                            List α

                            Tail recursive version of List.replace.

                            Equations
                            Instances For
                              @[specialize #[]]
                              def List.replaceTR.go {α : Type u_1} [BEq α] (l : List α) (b : α) (c : α) :
                              List αArray αList α

                              Auxiliary for replace: replace.go l b c xs acc = acc.toList ++ replace xs b c, unless b is not found in xs in which case it returns l.

                              Equations
                              Instances For

                                modify #

                                def List.modifyTR {α : Type u_1} (f : αα) (n : Nat) (l : List α) :
                                List α

                                Tail-recursive version of modify.

                                Equations
                                Instances For
                                  def List.modifyTR.go {α : Type u_1} (f : αα) :
                                  List αNatArray αList α

                                  Auxiliary for modifyTR: modifyTR.go f l n acc = acc.toList ++ modify f n l.

                                  Equations
                                  Instances For
                                    theorem List.modifyTR_go_eq :
                                    ∀ {α : Type u_1} {f : αα} {acc : Array α} (l : List α) (n : Nat), List.modifyTR.go f l n acc = acc.toList ++ List.modify f n l

                                    erase #

                                    @[inline]
                                    def List.eraseTR {α : Type u_1} [BEq α] (l : List α) (a : α) :
                                    List α

                                    Tail recursive version of List.erase.

                                    Equations
                                    Instances For
                                      def List.eraseTR.go {α : Type u_1} [BEq α] (l : List α) (a : α) :
                                      List αArray αList α

                                      Auxiliary for eraseTR: eraseTR.go l a xs acc = acc.toList ++ erase xs a, unless a is not present in which case it returns l

                                      Equations
                                      Instances For
                                        @[inline]
                                        def List.erasePTR {α : Type u_1} (p : αBool) (l : List α) :
                                        List α

                                        Tail-recursive version of eraseP.

                                        Equations
                                        Instances For
                                          @[specialize #[]]
                                          def List.erasePTR.go {α : Type u_1} (p : αBool) (l : List α) :
                                          List αArray αList α

                                          Auxiliary for erasePTR: erasePTR.go p l xs acc = acc.toList ++ eraseP p xs, unless xs does not contain any elements satisfying p, where it returns l.

                                          Equations
                                          Instances For
                                            theorem List.eraseP_eq_erasePTR.go (α : Type u_1) (p : αBool) (l : List α) (acc : Array α) (xs : List α) :
                                            l = acc.toList ++ xsList.erasePTR.go p l xs acc = acc.toList ++ List.eraseP p xs

                                            eraseIdx #

                                            @[inline]
                                            def List.eraseIdxTR {α : Type u_1} (l : List α) (n : Nat) :
                                            List α

                                            Tail recursive version of List.eraseIdx.

                                            Equations
                                            Instances For
                                              def List.eraseIdxTR.go {α : Type u_1} (l : List α) :
                                              List αNatArray αList α

                                              Auxiliary for eraseIdxTR: eraseIdxTR.go l n xs acc = acc.toList ++ eraseIdx xs a, unless a is not present in which case it returns l

                                              Equations
                                              Instances For

                                                Zippers #

                                                zipWith #

                                                @[inline]
                                                def List.zipWithTR {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : αβγ) (as : List α) (bs : List β) :
                                                List γ

                                                Tail recursive version of List.zipWith.

                                                Equations
                                                Instances For
                                                  def List.zipWithTR.go {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : αβγ) :
                                                  List αList βArray γList γ

                                                  Auxiliary for zipWith: zipWith.go f as bs acc = acc.toList ++ zipWith f as bs

                                                  Equations
                                                  Instances For
                                                    theorem List.zipWith_eq_zipWithTR.go (α : Type u_3) (β : Type u_2) (γ : Type u_1) (f : αβγ) (as : List α) (bs : List β) (acc : Array γ) :
                                                    List.zipWithTR.go f as bs acc = acc.toList ++ List.zipWith f as bs

                                                    Ranges and enumeration #

                                                    enumFrom #

                                                    def List.enumFromTR {α : Type u_1} (n : Nat) (l : List α) :
                                                    List (Nat × α)

                                                    Tail recursive version of List.enumFrom.

                                                    Equations
                                                    • One or more equations did not get rendered due to their size.
                                                    Instances For
                                                      theorem List.enumFrom_eq_enumFromTR.go (α : Type u_1) (l : List α) (n : Nat) :
                                                      let f := fun (a : α) (x : Nat × List (Nat × α)) => match x with | (n, acc) => (n - 1, (n - 1, a) :: acc); List.foldr f (n + l.length, []) l = (n, List.enumFrom n l)

                                                      Other list operations #

                                                      intercalate #

                                                      def List.intercalateTR {α : Type u_1} (sep : List α) :
                                                      List (List α)List α

                                                      Tail recursive version of List.intercalate.

                                                      Equations
                                                      • sep.intercalateTR [] = []
                                                      • sep.intercalateTR [x_1] = x_1
                                                      • sep.intercalateTR (x_1 :: xs) = List.intercalateTR.go sep.toArray x_1 xs #[]
                                                      Instances For
                                                        def List.intercalateTR.go {α : Type u_1} (sep : Array α) :
                                                        List αList (List α)Array αList α

                                                        Auxiliary for intercalateTR: intercalateTR.go sep x xs acc = acc.toList ++ intercalate sep.toList (x::xs)

                                                        Equations
                                                        Instances For
                                                          theorem List.intercalate_eq_intercalateTR.go (α : Type u_1) (sep : List α) {acc : Array α} {x : List α} (xs : List (List α)) :
                                                          List.intercalateTR.go sep.toArray x xs acc = acc.toList ++ (List.intersperse sep (x :: xs)).flatten