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 sorry theorem append_length (l1 l2 : NList) : length (append l1 l2) = length l1 + length l2 := by sorry end NList -- # Poly: Polymorphism and Higher-Order Functions inductive MyList (α : Type) : Type where | nil : MyList α | cons (x : α) (l : MyList α) : MyList α -- 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) #check MyList.nil #check MyList.cons 3 MyList.nil #check MyList.nil #check MyList.cons -- 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') 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