988:
958:– that is, those two type expressions are understood to denote the same type. In fact, most theories of equirecursive types go further and essentially specify that any two type expressions with the same "infinite expansion" are equivalent. As a result of these rules, equirecursive types contribute significantly more complexity to a type system than isorecursive types do. Algorithmic problems such as type checking and
1211:
in C, are replaced with their definition at compile time. (Type synonyms are not "real" types; they are just "aliases" for convenience of the programmer.) But if this is attempted with a recursive type, it will loop infinitely because no matter how many times the alias is substituted, it still refers
61:
An important application of recursion in computer science is in defining dynamic data structures such as Lists and Trees. Recursive data structures can dynamically grow to an arbitrarily large size in response to runtime requirements; in contrast, a static array's size requirements must be set at
241:(its children). This definition is elegant and easy to work with abstractly (such as when proving theorems about properties of trees), as it expresses a tree in simple terms: a list of one type, and a pair of two types.
962:
are more difficult for equirecursive types as well. Since direct comparison does not make sense on an equirecursive type, they can be converted into a canonical form in O(n log n) time, which can easily be compared.
196:
This indicates that non-empty list of type E contains a data member of type E, and a reference to another List object for the rest of the list (or a null reference to indicate that this is the end of the list).
258:
and a list of trees (its children). This definition is more compact, but somewhat messier: a tree consists of a pair of one type and a list another, which require disentangling to prove results about.
573:
There are two forms of recursive types: the so-called isorecursive types, and equirecursive types. The two forms differ in how terms of a recursive type are introduced and eliminated.
865:
528:
783:
568:
906:
608:
952:
695:
658:
78:
1231:
Another way to see it is that a level of indirection (the algebraic data type) is required to allow the isorecursive type system to figure out when to
697:
indicates that all instances of Z are replaced with Y in X) are distinct (and disjoint) types with special term constructs, usually called
1499:
1343:
1326:
17:
1870:
1504:
1494:
1489:
244:
This mutually recursive definition can be converted to a singly recursive definition by inlining the definition of a forest:
1477:
1378:
1655:
1031:
1013:
966:
Isorecursive types capture the form of self-referential (or mutually referential) type definitions seen in nominal
1628:
1106:
flag is used or it's a record or variant), or
Haskell; so, for example the following Haskell types are illegal:
1745:
1550:
1482:
1444:
998:
788:
489:
88:
712:
1645:
1575:
1423:
1095:
541:
1900:
1535:
54:
for values that may contain other values of the same type. Data of recursive types are usually viewed as
1523:
265:, the tree and forest data types can be mutually recursively defined as follows, allowing empty trees:
974:. In functional programming languages, isorecursive types (in the guise of datatypes) are common too.
1833:
1785:
1697:
1675:
1670:
1598:
1464:
1418:
1155:
Instead, they must be wrapped inside an algebraic data type (even if they only has one constructor):
1707:
1371:
971:
882:
584:
1301:
219:, which can be defined mutually recursively in terms of a forest (a list of trees). Symbolically:
1860:
1775:
1263:
1009:
534:
represent the Zero and Succ data constructors. Zero takes no arguments (thus represented by the
1603:
1459:
1413:
1296:
206:
1593:
1568:
1005:
216:
1926:
1395:
1248:
31:
1349:
8:
1921:
1865:
1843:
1623:
1615:
1364:
1253:
66:
1848:
1828:
1780:
1755:
1540:
1509:
911:
663:
617:
1735:
1665:
1640:
1454:
1449:
1316:
Revisiting iso-recursive subtyping | Proceedings of the ACM on
Programming Languages
79:
Recursion (computer science) § Recursive data structures (structural recursion)
1880:
1765:
1563:
1295:"Numbering Matters: First-Order Canonical Forms for Second-Order Recursive Types".
868:
455:
212:
84:
1885:
1750:
1702:
1635:
970:
programming languages, and also arise in type-theoretic semantics of objects and
967:
1048:, recursion is allowed in type aliases. Thus, the following example is allowed.
1838:
1660:
1650:
1558:
1258:
959:
55:
1915:
1760:
448:
1717:
1692:
138:
containing an 'a' (the "head" of the list) and another list (the "tail").
1895:
1890:
1740:
1687:
1514:
1315:
706:
444:
262:
1800:
1795:
1712:
1680:
1585:
1528:
1045:
1327:(More) Recursive Type Aliases - Announcing TypeScript 3.7 - TypeScript
1875:
1853:
1810:
1805:
1472:
1428:
1387:
535:
51:
1016:. Statements consisting only of original research should be removed.
347:
In
Haskell, the tree and forest data types can be defined similarly:
1790:
531:
451:α may appear in the type T and stands for the entire type itself.
1208:
134:
This indicates that a list of a's is either an empty list or a
1356:
1099:
1408:
1403:
141:
Another example is a similar singly linked type in Java:
447:, a recursive type has the general form μα.T where the
1094:
However, recursion is not allowed in type synonyms in
538:) and Succ takes another Nat (thus another element of
914:
885:
791:
715:
666:
620:
587:
544:
492:
65:
Sometimes the term "inductive data type" is used for
946:
900:
859:
777:
689:
652:
602:
562:
522:
1276:
27:Data type that refers to itself in its definition
1913:
215:. The most important basic example of this is a
200:
1212:to itself, e.g. "Bad" will grow indefinitely:
1372:
879:Under equirecursive rules, a recursive type
581:With isorecursive types, the recursive type
1288:
1379:
1365:
977:
458:) may be defined by the Haskell datatype:
229:consists of a list of trees, while a tree
1300:
1032:Learn how and when to remove this message
860:{\displaystyle unroll:\mu \alpha .T\to T}
523:{\displaystyle nat=\mu \alpha .1+\alpha }
778:{\displaystyle roll:T\to \mu \alpha .T}
14:
1914:
1341:
1282:
874:
454:For example, the natural numbers (see
1360:
576:
563:{\displaystyle \mu \alpha .1+\alpha }
69:which are not necessarily recursive.
1207:This is because type synonyms, like
981:
24:
211:Data types can also be defined by
207:Mutual recursion § Data types
25:
1938:
986:
1386:
1320:
1309:
941:
918:
854:
831:
825:
760:
757:
734:
709:between them. To be precise:
684:
670:
647:
624:
486:In type theory, we would say:
254:consists of a pair of a value
233:consists of a pair of a value
13:
1:
1445:Arbitrary-precision or bignum
1269:
901:{\displaystyle \mu \alpha .T}
603:{\displaystyle \mu \alpha .T}
201:Mutually recursive data types
7:
1242:
1012:the claims made and adding
10:
1943:
1335:
530:where the two arms of the
204:
76:
72:
1819:
1786:Strongly typed identifier
1728:
1614:
1584:
1549:
1437:
1394:
438:
1157:
1108:
1050:
460:
349:
267:
143:
93:
18:Recursive data structure
1861:Parametric polymorphism
1342:Harper, Robert (1998),
1264:Node (computer science)
978:Recursive type synonyms
948:
902:
861:
779:
691:
654:
610:and its expansion (or
604:
564:
524:
1345:Datatype Declarations
949:
903:
862:
780:
692:
655:
605:
565:
525:
205:Further information:
32:programming languages
1249:Recursive definition
912:
883:
867:, and these two are
789:
713:
664:
660:(where the notation
618:
585:
542:
490:
222:f: , ..., t] t: v f
67:algebraic data types
1866:Primitive data type
1771:Recursive data type
1624:Algebraic data type
1500:Quadruple precision
1254:Algebraic data type
875:Equirecursive types
48:inductive data type
44:inductively-defined
40:recursively-defined
36:recursive data type
1829:Abstract data type
1510:Extended precision
1469:Reduced precision
997:possibly contains
944:
908:and its unrolling
898:
857:
775:
687:
650:
600:
577:Isorecursive types
560:
520:
83:An example is the
1909:
1908:
1641:Associative array
1505:Octuple precision
1222:(Int, (Int, Bad))
1042:
1041:
1034:
999:original research
947:{\displaystyle T}
869:inverse functions
690:{\displaystyle X}
653:{\displaystyle T}
38:(also known as a
16:(Redirected from
1934:
1881:Type constructor
1766:Opaque data type
1698:Record or Struct
1495:Double precision
1490:Single precision
1381:
1374:
1367:
1358:
1357:
1353:
1348:, archived from
1329:
1324:
1318:
1313:
1307:
1306:
1304:
1292:
1286:
1280:
1227:
1223:
1219:
1215:
1203:
1200:
1197:
1194:
1191:
1188:
1185:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1161:
1151:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1105:
1090:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1037:
1030:
1026:
1023:
1017:
1014:inline citations
990:
989:
982:
953:
951:
950:
945:
937:
907:
905:
904:
899:
866:
864:
863:
858:
850:
784:
782:
781:
776:
753:
696:
694:
693:
688:
680:
659:
657:
656:
651:
643:
609:
607:
606:
601:
569:
567:
566:
561:
529:
527:
526:
521:
482:
479:
476:
473:
470:
467:
464:
456:Peano arithmetic
434:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
389:
386:
383:
380:
377:
374:
371:
368:
365:
362:
359:
356:
353:
343:
340:
337:
334:
331:
328:
325:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
271:
213:mutual recursion
192:
189:
186:
183:
180:
177:
174:
171:
168:
165:
162:
159:
156:
153:
150:
147:
130:
127:
124:
121:
118:
115:
112:
109:
106:
103:
100:
97:
21:
1942:
1941:
1937:
1936:
1935:
1933:
1932:
1931:
1912:
1911:
1910:
1905:
1886:Type conversion
1821:
1815:
1751:Enumerated type
1724:
1610:
1604:null-terminated
1580:
1545:
1433:
1390:
1385:
1338:
1333:
1332:
1325:
1321:
1314:
1310:
1294:
1293:
1289:
1281:
1277:
1272:
1245:
1225:
1221:
1217:
1213:
1205:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1153:
1152:
1149:
1146:
1143:
1140:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1103:
1092:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1038:
1027:
1021:
1018:
1003:
991:
987:
980:
968:object-oriented
933:
913:
910:
909:
884:
881:
880:
877:
846:
790:
787:
786:
749:
714:
711:
710:
705:, that form an
676:
665:
662:
661:
639:
619:
616:
615:
586:
583:
582:
579:
543:
540:
539:
491:
488:
487:
484:
483:
480:
477:
474:
471:
468:
465:
462:
441:
436:
435:
432:
429:
426:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
345:
344:
341:
338:
335:
332:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
299:
296:
293:
290:
287:
284:
281:
278:
275:
272:
269:
248:
247:t: v , ..., t]
223:
209:
203:
194:
193:
190:
187:
184:
181:
178:
175:
172:
169:
166:
163:
160:
157:
154:
151:
148:
145:
132:
131:
128:
125:
122:
119:
116:
113:
110:
107:
104:
101:
98:
95:
81:
75:
56:directed graphs
28:
23:
22:
15:
12:
11:
5:
1940:
1930:
1929:
1924:
1907:
1906:
1904:
1903:
1898:
1893:
1888:
1883:
1878:
1873:
1868:
1863:
1858:
1857:
1856:
1846:
1841:
1839:Data structure
1836:
1831:
1825:
1823:
1817:
1816:
1814:
1813:
1808:
1803:
1798:
1793:
1788:
1783:
1778:
1773:
1768:
1763:
1758:
1753:
1748:
1743:
1738:
1732:
1730:
1726:
1725:
1723:
1722:
1721:
1720:
1710:
1705:
1700:
1695:
1690:
1685:
1684:
1683:
1673:
1668:
1663:
1658:
1653:
1648:
1643:
1638:
1633:
1632:
1631:
1620:
1618:
1612:
1611:
1609:
1608:
1607:
1606:
1596:
1590:
1588:
1582:
1581:
1579:
1578:
1573:
1572:
1571:
1566:
1555:
1553:
1547:
1546:
1544:
1543:
1538:
1533:
1532:
1531:
1521:
1520:
1519:
1518:
1517:
1507:
1502:
1497:
1492:
1487:
1486:
1485:
1480:
1478:Half precision
1475:
1465:Floating point
1462:
1457:
1452:
1447:
1441:
1439:
1435:
1434:
1432:
1431:
1426:
1421:
1416:
1411:
1406:
1400:
1398:
1392:
1391:
1384:
1383:
1376:
1369:
1361:
1355:
1354:
1337:
1334:
1331:
1330:
1319:
1308:
1287:
1274:
1273:
1271:
1268:
1267:
1266:
1261:
1259:Inductive type
1256:
1251:
1244:
1241:
1158:
1109:
1051:
1040:
1039:
994:
992:
985:
979:
976:
960:type inference
943:
940:
936:
932:
929:
926:
923:
920:
917:
897:
894:
891:
888:
876:
873:
856:
853:
849:
845:
842:
839:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
794:
774:
771:
768:
765:
762:
759:
756:
752:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
718:
686:
683:
679:
675:
672:
669:
649:
646:
642:
638:
635:
632:
629:
626:
623:
599:
596:
593:
590:
578:
575:
559:
556:
553:
550:
547:
519:
516:
513:
510:
507:
504:
501:
498:
495:
461:
440:
437:
350:
268:
246:
221:
202:
199:
144:
94:
74:
71:
62:compile time.
26:
9:
6:
4:
3:
2:
1939:
1928:
1925:
1923:
1920:
1919:
1917:
1902:
1899:
1897:
1894:
1892:
1889:
1887:
1884:
1882:
1879:
1877:
1874:
1872:
1869:
1867:
1864:
1862:
1859:
1855:
1852:
1851:
1850:
1847:
1845:
1842:
1840:
1837:
1835:
1832:
1830:
1827:
1826:
1824:
1818:
1812:
1809:
1807:
1804:
1802:
1799:
1797:
1794:
1792:
1789:
1787:
1784:
1782:
1779:
1777:
1774:
1772:
1769:
1767:
1764:
1762:
1761:Function type
1759:
1757:
1754:
1752:
1749:
1747:
1744:
1742:
1739:
1737:
1734:
1733:
1731:
1727:
1719:
1716:
1715:
1714:
1711:
1709:
1706:
1704:
1701:
1699:
1696:
1694:
1691:
1689:
1686:
1682:
1679:
1678:
1677:
1674:
1672:
1669:
1667:
1664:
1662:
1659:
1657:
1654:
1652:
1649:
1647:
1644:
1642:
1639:
1637:
1634:
1630:
1627:
1626:
1625:
1622:
1621:
1619:
1617:
1613:
1605:
1602:
1601:
1600:
1597:
1595:
1592:
1591:
1589:
1587:
1583:
1577:
1574:
1570:
1567:
1565:
1562:
1561:
1560:
1557:
1556:
1554:
1552:
1548:
1542:
1539:
1537:
1534:
1530:
1527:
1526:
1525:
1522:
1516:
1513:
1512:
1511:
1508:
1506:
1503:
1501:
1498:
1496:
1493:
1491:
1488:
1484:
1481:
1479:
1476:
1474:
1471:
1470:
1468:
1467:
1466:
1463:
1461:
1458:
1456:
1453:
1451:
1448:
1446:
1443:
1442:
1440:
1436:
1430:
1427:
1425:
1422:
1420:
1417:
1415:
1412:
1410:
1407:
1405:
1402:
1401:
1399:
1397:
1396:Uninterpreted
1393:
1389:
1382:
1377:
1375:
1370:
1368:
1363:
1362:
1359:
1352:on 1999-10-01
1351:
1347:
1346:
1340:
1339:
1328:
1323:
1317:
1312:
1303:
1302:10.1.1.4.2276
1298:
1291:
1284:
1279:
1275:
1265:
1262:
1260:
1257:
1255:
1252:
1250:
1247:
1246:
1240:
1238:
1234:
1229:
1210:
1156:
1107:
1101:
1097:
1049:
1047:
1036:
1033:
1025:
1015:
1011:
1007:
1001:
1000:
995:This section
993:
984:
983:
975:
973:
969:
964:
961:
957:
938:
934:
930:
927:
924:
921:
915:
895:
892:
889:
886:
872:
870:
851:
847:
843:
840:
837:
834:
828:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
772:
769:
766:
763:
754:
750:
746:
743:
740:
737:
731:
728:
725:
722:
719:
716:
708:
704:
700:
681:
677:
673:
667:
644:
640:
636:
633:
630:
627:
621:
613:
597:
594:
591:
588:
574:
571:
557:
554:
551:
548:
545:
537:
533:
517:
514:
511:
508:
505:
502:
499:
496:
493:
459:
457:
452:
450:
449:type variable
446:
348:
266:
264:
259:
257:
253:
245:
242:
240:
237:and a forest
236:
232:
228:
220:
218:
214:
208:
198:
142:
139:
137:
92:
90:
86:
80:
70:
68:
63:
59:
57:
53:
49:
45:
41:
37:
33:
19:
1770:
1666:Intersection
1350:the original
1344:
1322:
1311:
1290:
1278:
1236:
1232:
1230:
1206:
1154:
1093:
1043:
1028:
1022:January 2024
1019:
996:
965:
955:
878:
702:
698:
611:
580:
572:
485:
453:
442:
346:
260:
255:
251:
249:
243:
238:
234:
230:
226:
224:
210:
195:
140:
135:
133:
82:
64:
60:
47:
43:
39:
35:
30:In computer
29:
1927:Type theory
1896:Type theory
1891:Type system
1741:Bottom type
1688:Option type
1629:generalized
1515:Long double
1460:Fixed point
1283:Harper 1998
707:isomorphism
445:type theory
263:Standard ML
1922:Data types
1916:Categories
1801:Empty type
1796:Type class
1746:Collection
1703:Refinement
1681:metaobject
1529:signedness
1388:Data types
1270:References
1218:(Int, Bad)
1046:TypeScript
1006:improve it
77:See also:
1876:Subtyping
1871:Interface
1854:metaclass
1806:Unit type
1776:Semaphore
1756:Exception
1661:Inductive
1651:Dependent
1616:Composite
1594:Character
1576:Reference
1473:Minifloat
1429:Bit array
1297:CiteSeerX
1104:-rectypes
1010:verifying
939:α
925:α
922:μ
890:α
887:μ
852:α
838:α
835:μ
826:→
817:α
814:μ
767:α
764:μ
761:→
755:α
741:α
738:μ
645:α
631:α
628:μ
612:unrolling
592:α
589:μ
558:α
549:α
546:μ
536:unit type
518:α
509:α
506:μ
225:A forest
136:cons cell
87:type, in
52:data type
1901:Variable
1791:Top type
1656:Equality
1564:physical
1541:Rational
1536:Interval
1483:bfloat16
1243:See also
1209:typedefs
1102:(unless
532:sum type
270:datatype
1844:Generic
1820:Related
1736:Boolean
1693:Product
1569:virtual
1559:Address
1551:Pointer
1524:Integer
1455:Decimal
1450:Complex
1438:Numeric
1336:Sources
1096:Miranda
1004:Please
972:classes
250:A tree
89:Haskell
73:Example
50:) is a
1834:Boxing
1822:topics
1781:Stream
1718:tagged
1676:Object
1599:String
1299:
1237:unroll
1062:number
703:unroll
439:Theory
427:Forest
394:Forest
382:Forest
342:forest
339:'a
330:'a
312:forest
309:'a
303:forest
300:'a
294:'a
273:'a
1729:Other
1713:Union
1646:Class
1636:Array
1419:Tryte
1196:->
1147:->
1100:OCaml
956:equal
364:Empty
282:Empty
167:value
146:class
1849:Kind
1811:Void
1671:List
1586:Text
1424:Word
1414:Trit
1409:Byte
1235:and
1233:roll
1199:Fine
1193:Bool
1181:Fine
1178:data
1175:Good
1169:Pair
1163:Good
1160:data
1150:Evil
1144:Bool
1138:Evil
1135:type
1111:type
1083:Tree
1077:tree
1068:Tree
1056:Tree
1053:type
954:are
785:and
701:and
699:roll
478:Succ
472:Zero
463:data
415:Tree
409:Cons
391:data
370:Node
355:Tree
352:data
333:tree
324:Cons
288:Node
276:tree
217:tree
185:next
182:>
176:<
173:List
158:>
152:<
149:List
123:List
114:Cons
99:List
96:data
85:list
34:, a
1708:Set
1404:Bit
1226:...
1214:Bad
1187:Fun
1172:Int
1129:Bad
1123:Int
1114:Bad
1074:let
1044:In
1008:by
570:).
481:Nat
466:Nat
443:In
403:Nil
318:Nil
306:and
261:In
108:Nil
46:or
1918::
1239:.
1228:.
1224:→
1220:→
1216:→
1098:,
1089:];
871:.
614:)
552:.1
512:.1
327:of
291:of
91::
58:.
42:,
1380:e
1373:t
1366:v
1305:.
1285:.
1202:)
1190:(
1184:=
1166:=
1141:=
1132:)
1126:,
1120:(
1117:=
1086:=
1080::
1071:;
1065:|
1059:=
1035:)
1029:(
1024:)
1020:(
1002:.
942:]
935:/
931:T
928:.
919:[
916:T
896:T
893:.
855:]
848:/
844:T
841:.
832:[
829:T
823:T
820:.
811::
808:l
805:l
802:o
799:r
796:n
793:u
773:T
770:.
758:]
751:/
747:T
744:.
735:[
732:T
729::
726:l
723:l
720:o
717:r
685:]
682:Z
678:/
674:Y
671:[
668:X
648:]
641:/
637:T
634:.
625:[
622:T
598:T
595:.
555:+
515:+
503:=
500:t
497:a
494:n
475:|
469:=
433:)
430:a
424:(
421:)
418:a
412:(
406:|
400:=
397:a
388:)
385:a
379:,
376:a
373:(
367:|
361:=
358:a
336:*
321:|
315:=
297:*
285:|
279:=
256:v
252:t
239:f
235:v
231:t
227:f
191:}
188:;
179:E
170:;
164:E
161:{
155:E
129:)
126:a
120:(
117:a
111:|
105:=
102:a
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.