Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

In Agda is it possible to define a datatype that has equations?

I want to describe the integers:

data Integer : Set where
    Z : Integer
    Succ : Integer -> Integer
    Pred : Integer -> Integer
    ?? what else

The above does not define the Integers. We need Succ (Pred x) = x and Pred (Succ x) = x. However,

    spReduce : (m : Integer) -> Succ (Pred m) = m
    psReduce : (m : Integer) -> Pred (Succ m) = m

Can't be added to the data type. A better definition of the integers is most certainly,

data Integers : Set where
    Pos : Nat -> Integers
    Neg : Nat -> Integers

But I am curious if there is a way to add equations to a datatype.

like image 919
Jonathan Gallagher Avatar asked Mar 19 '23 01:03

Jonathan Gallagher


1 Answers

I'd go about it by defining a record:

record Integer (A : Set) : Set where
  constructor integer
  field
    z : A
    succ : A -> A
    pred : A -> A
    spInv : (x : A) -> succ (pred x) == x
    psInv : (x : A) -> pred (succ x) == x

This record can be used as a proof that a certain type A behaves like an Integer should.

like image 61
Sassa NF Avatar answered Mar 21 '23 20:03

Sassa NF