-- 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


-- -}
-- -}
-- -}
-- -}