patternMinor
Which inductive schemes can encode the following Agda definition?
Viewed 0 times
definitioncantheagdafollowingwhichencodeinductiveschemes
Problem
Which induction schemes (e.g. induction-recursion by Dybjer and Setzer, "Irish" induction-recursion by McBride or induction-induction by Forsberg and Setzer or perhaps some simpler ones) allow one to encode the following Agda definition
I can think of some tricks to reformulate
Edit: As follows from András Kovács's answer, this particular definition can be reformulated as an inductive family. Here is how to do it:
data A : Set where
a : Maybe (List A) → AI can think of some tricks to reformulate
List in this definition so that induction-recursion becomes applicable, but are there any schemes that would allow me to first say what a list is and then refer to this information to say what A is the way it's done in Agda?Edit: As follows from András Kovács's answer, this particular definition can be reformulated as an inductive family. Here is how to do it:
data Three : Set where one two three : Three
data AG : Three → Set where
a' : AG three → AG one
nil' : AG two
cons' : AG one → AG two → AG two
nothing' : AG three
just' : AG two → AG three
A = AG one
ListA = AG two
MaybeListA = AG three
a : MaybeListA → A
a = a'
nil : ListA
nil = nil'
cons : A → ListA → ListA
cons = cons'
nothing : MaybeListA
nothing = nothing'
just : ListA → MaybeListA
just = just'Solution
No scheme that I know of directly encodes that type. Sometimes it's called a "nested" inductive definition. The complication here is that
In other words, the consistency of
Agda does look into all the external definitions and tries to determine the variance of type parameters. While I don't know a reference for a direct formal specification of this, an easy way to reformulate nested definitions as non-nested is to include the external type operators into a mutual inductive signature. For example:
This is an ordinary mutual inductive type, which is covered (modulo cosmetic details) by Dybjer's inductive families.
Maybe and List are type constructors which are external to the signature, and we have to formalize strict positivity for external type operators in general, if we want to allow such definitions. In other words, the consistency of
A depends on the definition on Maybe and List. Some external type operators are not positive, as in:data Neg (A : Set) : Set where
neg : (A -> Bool) -> Neg A
data B : Set where
b : Neg B -> BAgda does look into all the external definitions and tries to determine the variance of type parameters. While I don't know a reference for a direct formal specification of this, an easy way to reformulate nested definitions as non-nested is to include the external type operators into a mutual inductive signature. For example:
data A : Set
data ListA : Set
data MaybeListA : Set
data A where
a : MaybeListA -> A
data ListA where
nil : ListA
cons : A -> ListA -> ListA
data MaybeListA where
nothing : MaybeListA
just : ListA -> MaybeListAThis is an ordinary mutual inductive type, which is covered (modulo cosmetic details) by Dybjer's inductive families.
Code Snippets
data Neg (A : Set) : Set where
neg : (A -> Bool) -> Neg A
data B : Set where
b : Neg B -> Bdata A : Set
data ListA : Set
data MaybeListA : Set
data A where
a : MaybeListA -> A
data ListA where
nil : ListA
cons : A -> ListA -> ListA
data MaybeListA where
nothing : MaybeListA
just : ListA -> MaybeListAContext
StackExchange Computer Science Q#120836, answer score: 4
Revisions (0)
No revisions yet.