import LF.Induction import LF.UsingLean import LF.SFLCompat inductive NList : Type where | nil | cons (n : Nat) (l : NList) namespace NList def reverse (l : NList) : NList := match l with | nil => nil | cons n l' => cons n (reverse l') def length (l : NList) : Nat := match l with | nil => 0 | cons _ l' => 1 + length l' def append (l1 l2 : NList) : NList := match l1 with | nil => l2 | cons n l' => cons n (append l' l2) theorem append_nil (l : NList) : append l nil = l := by induction l with | nil => rfl | cons n l' ih => dsimp [append] rw [ih] theorem append_length (l1 l2 : NList) : length (append l1 l2) = length l1 + length l2 := by induction l1 with | nil => dsimp [append, length] rw [Nat.zero_add] | cons n l' ih => dsimp [append, length] rw [ih] rw [Nat.add_assoc] end NList -- # Poly: Polymorphism and Higher-Order Functions inductive MyList (α : Type) : Type where | nil : MyList α | cons (x : α) (l : MyList α) : MyList α -- This is exactly like the definition of `Natlist` from the previous chapter, -- except that the `Nat` argument to the `cons` constructor has been replaced -- by an arbitrary type `α`, a type parameter `α` has been added to the header -- on the first line, and the occurrences of `Natlist` in the types of the -- constructors have been replaced by `MyList α`. We can now write -- `MyList Nat` instead of a dedicated nat-list type. -- What sort of thing is `MyList` itself? A good way to think about it is as a -- *type constructor* — that is, a function from `Type`s to `Type`s. For any -- particular type `α`, the type `MyList α` is the inductively defined type of -- lists whose elements are of type `α`. #check (MyList) -- MyList : Type → Type -- The `α` in the definition of `MyList` automatically becomes a parameter to -- the constructors `nil` and `cons` — that is, `nil` and `cons` are now -- polymorphic constructors. In Lean, the type parameter is *implicit* by -- default: Lean will infer it from context. For example, `MyList.nil` is the -- empty list, and Lean figures out the element type from how it is used. #check MyList.nil -- MyList.nil {α : Type} : MyList α -- Similarly, `MyList.cons` adds an element of type `Nat` to a list of type -- `MyList Nat`. Here is an example of forming a list containing just the -- natural number 3. #check MyList.cons 3 MyList.nil -- MyList.cons 3 MyList.nil : MyList Nat -- What is the full type of `MyList.nil`? We can read off the result type -- `MyList α` from the definition, but to state the full type we must also -- bind `α`. Since the type argument to the constructor is implicit, Lean -- writes its type as `{α : Type} → MyList α`. #check MyList.nil -- MyList.nil {α : Type} : MyList α -- Similarly, the type of `MyList.cons` includes the implicit type parameter: #check MyList.cons -- MyList.cons {α : Type} (x : α) (l : MyList α) : MyList α -- Having to supply a type argument for every single use of a list constructor -- would be rather burdensome. Fortunately, the type argument is implicit, so -- Lean will normally infer it from context. -- We can now go back and make polymorphic versions of all the list-processing -- functions that we wrote before. Here is `myRepeat`, for example: def myRepeat (α : Type) (x : α) (count : Nat) : MyList α := match count with | 0 => .nil | count' + 1 => .cons x (myRepeat α x count') -- Some simple facts about `myRepeat`: theorem myRepeat_zero (α : Type) (v : α) : myRepeat α v 0 = MyList.nil := rfl theorem myRepeat_succ (α : Type) (v : α) (count : Nat) : myRepeat α v (count + 1) = MyList.cons v (myRepeat α v count) := rfl -- We can use `myRepeat` by applying it first to a type and then to an element -- of this type (and a number): example : myRepeat Nat 4 2 = .cons 4 (.cons 4 .nil) := by rfl -- To use `myRepeat` to build other kinds of lists, we simply pass a different -- type and an element of that type: example : myRepeat Bool false 1 = .cons false .nil := by rfl def list123 : List Nat := [1, 2, 3] -- #### Type Annotation Inference -- Let's write the definition of `myRepeat` again, but this time we won't -- specify the type of the parameter `α`. Will Lean still accept it? def myRepeat' α (x : α) (count : Nat) : List α := match count with | 0 => .nil | count' + 1 => .cons x (myRepeat' α x count') -- Indeed it will. Lean infers that `α` is a type. The generated `u_1` is part -- of Lean's bookkeeping for treating types more generally. We will not need -- to interpret names like this for now — you can ignore them when they appear -- in Lean's output unless we explicitly call attention to them. #check myRepeat' -- myRepeat'.{u_1} (α : Type u_1) (x : α) (count : Nat) : List α -- Lean was able to use *type inference* to deduce what the type of `α` must -- be, based on how it is used. Since `α` is an argument to `List`, it must be -- a `Type`, since `List` expects a `Type` as its argument. -- This facility means we don't always have to write explicit type annotations -- everywhere, although explicit type annotations can still be quite useful as -- documentation, so we will continue to use them much of the time. -- #### Type Argument Synthesis -- To use a polymorphic function, we need to pass it one or more types in -- addition to its other arguments. For example, the recursive call in the -- body of the `myRepeat` function above must pass along the type `α`. But -- since the second argument to `myRepeat` is an element of `α`, it seems -- entirely obvious that the first argument can only be `α` — why should we -- have to write it explicitly? -- Fortunately, Lean permits us to avoid this kind of redundancy. In place of -- any type argument we can write a "hole" `_`, which can be read as "Please -- try to figure out for yourself what belongs here." More precisely, when -- Lean encounters a `_`, it will attempt to *unify* all locally available -- information — the type of the function being applied, the types of the -- other arguments, and the type expected by the context in which the -- application appears — to determine what concrete type should replace the -- `_`. -- Using holes, the `myRepeat'` function can be written like this: def myRepeat'' (α : Type) (x : α) (count : Nat) : List α := match count with | 0 => [] | count' + 1 => x :: myRepeat'' _ x count' -- Alternatively, we can declare an argument to be implicit when defining the -- function itself, by surrounding it in curly braces instead of parentheses. -- For example: def myRepeat''' {α : Type} (x : α) (count : Nat) : List α := match count with | 0 => [] | count' + 1 => x :: myRepeat''' x count' -- (Note that we didn't even have to provide a type argument to the recursive -- call to `myRepeat'''`. Indeed, it would be invalid to provide one, because -- Lean is not expecting it.) -- #### Supplying Type Arguments Explicitly -- One small problem with implicit arguments is that, once in a while, Lean -- does not have enough local information to determine a type argument; in -- such cases, we need to tell Lean the type explicitly. For example: -- This fails because Lean can't figure out the type of the empty list: -- `def mynil := []` — error: type not known We can fix this with an explicit -- type annotation: -- We can use the `@` prefix to supply the type argument explicitly. The `@` -- makes all implicit arguments of a function explicit: #check @List.nil def myNil' := @List.nil Nat