-- Advanced Functional Programming course 2021 -- Chalmers TDA342 / GU DIT260 -- -- 2021-02-22 Guest lecture by Andreas Abel -- -- Introduction to Agda -- -- File 1: The Curry-Howard Isomorphism {-# OPTIONS --allow-unsolved-metas #-} module Prelude where postulate ANYTHING : ∀{ℓ}{A : Set ℓ} → A -- Natural numbers as our first example of -- an inductive data type. data ℕ : Set where -- C-u C-x = zero : ℕ -- \ b N suc : (n : ℕ) → ℕ -- To use decimal notation for numerals, like -- 2 instead of (suc (suc zero)), connect it -- to the built-in natural numbers. {-# BUILTIN NATURAL ℕ #-} five : ℕ five = 5 three : ℕ three = suc (suc (suc zero)) -- C-c C-n evaluate expression -- Lists are a parameterized inductive data type. data List (A : Set) : Set where [] : List A _∷_ : (x : A) (xs : List A) → List A -- C-\ : : infixr 6 _∷_ -- C-c C-l load -- C-c C-d check declaration variable n m : ℕ A : Set -- Vectors. data Vec (A : Set) : ℕ → Set where [] : Vec A zero _∷_ : {n : ℕ} (x : A) (xs : Vec A n) → Vec A (suc n) vec : Vec ℕ 2 -- C-c C-= -- C-c C-s vec = zero ∷ zero ∷ [] replicate : (n : ℕ) {A : Set} (_ : A) → Vec A n replicate zero a = [] replicate (suc n) a = a ∷ replicate n a Vecℕ : ℕ → Set Vecℕ = Vec ℕ length : Vec A n → ℕ length [] = 0 length (_∷_ {n = n} _ _) = suc n _+_ : (n m : ℕ) → ℕ zero + m = m suc n + m = suc (n + m) append : {n m : ℕ} → Vec A n → Vec A m → Vec A (n + m) append [] ys = ys append {n = suc n} {m = m} (x ∷ xs) ys = _∷_ {n = n + m} x (append xs ys) -- Disjoint sum type. data _⊎_ (S T : Set) : Set where -- \uplus inl : S → S ⊎ T inr : T → S ⊎ T infixr 4 _⊎_ -- The empty sum is the type with 0 alternatives, -- which is the empty type. -- By the Curry-Howard-Isomorphism, -- which views a proposition as the set/type of its proofs, -- it is also the absurd proposition. data False : Set where -- absurd : False -- absurd = absurd -- C-c C-r refine -- foo : ℕ → ℕ -- foo n = foo (suc n) -- ex falso quodlibet ⊥-elim : False → {A : Set} → A ⊥-elim () -- C-c C-c split -- C-c C-SPC give -- C-c C-, show hypotheses and goal -- C-c C-. show hypotheses and infers type -- Tuple types -- The generic record type with two fields -- where the type of the second depends on the value of the first -- is called Sigma-type (or dependent sum), in analogy to -- -- Σ ℕ A = Σ A(n) = A(0) + A(1) + ... -- n ∈ ℕ -- Σ A B = Σ B(x) -- x ∈ A -- data Σ (A : Set) (B : A → Set) : Set where -- _,_ : (x : A) (y : B x) → Σ A B record Σ (A : Set) (B : A → Set) : Set where -- \GS \Sigma constructor _,_ field fst : A snd : B fst open Σ -- Σ.fst Σ.snd infixr 5 _,_ myvec : Σ ℕ (λ n → Vec ℕ n) myvec = 2 , vec -- The non-dependent version is the ordinary Cartesian product. _×_ : (S T : Set) → Set S × T = Σ S λ _ → T infixr 5 _×_ -- The record type with no fields has exactly one inhabitant -- namely the empty tuple record{} -- By Curry-Howard, it corresponds to Truth, as -- no evidence is needed to construct this proposition. record True : Set where test : True test = record {} ¬_ : (A : Set) → Set ¬ A = A → False -- Example: distributivity A ∧ (B ∨ C) → (A ∧ B) ∨ (A ∧ C) dist : ∀{A B C : Set} → A × (B ⊎ C) → (A × B) ⊎ (A × C) dist (a , inl b) = inl (a , b) dist (a , inr c) = inr (a , c) _≡_ : (n m : ℕ) → Set zero ≡ zero = True zero ≡ suc m = False suc n ≡ zero = False suc n ≡ suc m = n ≡ m refl : (n : ℕ) → n ≡ n refl zero = record {} refl (suc n) = refl n splitℕ : ∀ n → (n ≡ 0) ⊎ Σ ℕ (λ m → n ≡ suc m) splitℕ zero = inl (record {}) splitℕ (suc n) = inr (n , refl n) -- Relations -- Type-theoretically, the type of relations 𝓟(A×A) is -- -- A × A → Prop -- -- which is -- -- A × A → Set -- -- by the Curry-Howard-Isomorphism -- and -- -- A → A → Set -- -- by currying. Rel : (A : Set) → Set₁ Rel A = A → A → Set -- Set : Set -- paradox -- Set : Set₁ : Set₂ : ... -- Less-or-equal on natural numbers _≤_ : Rel ℕ zero ≤ y = True suc x ≤ zero = False suc x ≤ suc y = x ≤ y -- C-c C-l load -- C-c C-c case split -- C-c C-, show goal and assumptions -- C-c C-. show goal and assumptions and current term -- C-c C-SPC give -- -} -- -} -- -} -- -}