DEV Community

Panda Quests
Panda Quests

Posted on

In recursion, what is the difference between a isorecursive types and equirecursive types?

Top comments (4)

Collapse
 
rad_val_ profile image
Valentin Radu • Edited

Type recursion is a way to define structures that have fields or members of the same type as self, like a binary tree node:

class Tree {
    Tree leftChild, rightChild; int data;
}

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)

Hope it helps!

Collapse
 
pandaquests profile image
Panda Quests

Ah, thanks

Collapse
 
pentacular profile image
pentacular

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.

Collapse
 
pandaquests profile image
Panda Quests

I'll do Thanks.