Skip to content

Instantly share code, notes, and snippets.

@EduardoRFS
Last active December 17, 2023 00:44
Show Gist options
  • Save EduardoRFS/140ed885cbfcd02a1d8fa00a789a38cc to your computer and use it in GitHub Desktop.
Save EduardoRFS/140ed885cbfcd02a1d8fa00a789a38cc to your computer and use it in GitHub Desktop.
```rust
// rules
// Those rules are fully church-style
Γ, x : A |- B : Type
---------------------------
Γ |- @self(x : A). B : Type
Γ, x : A |- M : B[x := @fix(x : A). M] Γ |- A ≂ @self(x : A). B
----------------------------------------------------------------
Γ |- @fix(x : A). M : @self(x : A). B
Γ |- M : @self(x : A). B
--------------------------
Γ |- @unroll M : B[x := M]
/*
3 general steps
Describe the type indexed by the constructors of the type
Make the type family itself
Close the family on the constructors
The following code assumes implicit unroll
*/
// shape of family, induction-induction required
T_P_Unit : Type;
T_p_unit : (P_Unit : T_P_Unit) -> Type;
T_P_Unit = @self(P_Unit : T_P_Unit). (p_unit : T_p_unit P_Unit) -> Type;
T_p_unit P_Unit = @self(p_unit : T_p_unit P_Unit). P_Unit p_unit;
// proto Unit
P_Unit : T_Unit;
p_unit : T_p_unit P_unit;
P_Unit p_unit = @self(u : P_Unit p_unit).
(P : P_Unit p_unit -> Type) -> P p_unit -> P u;
p_unit = @fix(p_unit). P => (x : P p_unit) => x;
// closing
Unit = P_Unit p_unit;
unit : Unit = p_unit;
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment