Type recursion is a way to define structures that have fields or members of the same type as self, like a binary tree node:
classTree{TreeleftChild,rightChild;intdata;}
You're probably more familiar with equirecursive types, since there're used in most OOP languages out there. There's quite a bit of theory around this, but in a nutshell: equirecursive types are considered the same type (or equal type) no matter the recursive level they are at. In the example above the type of leftChild is the same as the type of leftChild.leftChild or leftChild.leftChild.rightChild and so on.
On the other hand, with isorecursive types, leftChild and leftChild.leftChild types would be considered different types, but isomorphic since you could cast between them using special language constructs (usually called fold and unfold, or similar)
Top comments (4)
Type recursion is a way to define structures that have fields or members of the same type as self, like a binary tree node:
You're probably more familiar with equirecursive types, since there're used in most OOP languages out there. There's quite a bit of theory around this, but in a nutshell: equirecursive types are considered the same type (or equal type) no matter the recursive level they are at. In the example above the type of
leftChild
is the same as the type ofleftChild.leftChild
orleftChild.leftChild.rightChild
and so on.On the other hand, with isorecursive types,
leftChild
andleftChild.leftChild
types would be considered different types, but isomorphic since you could cast between them using special language constructs (usually calledfold
andunfold
, or similar)Hope it helps!
Ah, thanks
Equirecursive types are equal when they accept the same set of potential objects.
Isorecursive types are equal when they satisfy the same structural requirements.
I think this will require some considerable research on your part to fully understand, but hopefully this will help somewhat.
I'll do Thanks.