309:
that yields either a pair of a value and a new state, or a singleton to mark the end of the list. The anamorphism would then begin with a first seed, compute whether the list continues or ends, and in case of a nonempty list, prepend the computed value to the recursive call to the anamorphism.
34:
is a function that generates a sequence by repeated application of the function to its previous result. You begin with some value A and apply a function f to it to get B. Then you apply f to B to get C, and so on until some terminating condition is reached. The anamorphism is the function that
1824:
290:
is the fixed point. (Also note that in
Haskell, least and greatest fixed points of functors coincide, therefore inductive lists are the same as coinductive, potentially infinite lists.)
1774:
542:
This function will decrement an integer and output it at the same time, until it is negative, at which point it will mark the end of the list. Correspondingly,
1870:
1196:
takes a thing, x, and a function, f, from such things to such things, and returns the infinite list that comes from repeated application of f, i.e. the list .
1139:
With these definitions, the argument to the constructor of the type has the same type as the return type of the first argument of
1941:
1160:
1944:; Fokkinga, Maarten; Paterson, Ross (1991). "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire": 124–144.
1907:
181:
17:
557:
An anamorphism can be defined for any recursive type, according to a generic pattern, generalizing the second version of
101:
68:
1179:
1780:
35:
generates the list of A, B, C, etc. You can think of the anamorphism as unfolding the initial value into a sequence.
1155:
One of the first publications to introduce the notion of an anamorphism in the context of programming was the paper
2009:
2004:
1945:
1611:
301:) would build a (potentially infinite) list from a state value. Typically, the unfold takes a state value
92:
63:
1989:
1739:
1959:
118:
1950:
121:
and which is parameterized by functions that determine the next single step of the construction.
1575:
165:
110:
106:
76:
1972:
1594:
1571:
55:
39:
788:
To better see the relationship between the recursive type and its anamorphism, note that
1841:
132:. By the universal property of final coalgebras, there is a unique coalgebra morphism
1998:
1913:
1901:
1655:
1579:
80:
24:
1919:
1604:
1597:
114:
59:
43:
1721:
In other words, we have the following defining relationship, given some fixed
1895:
1562:
are merely defined terms, as we have seen from the definitions given above.
47:
1889:
1619:
1167:
51:
1157:
Functional
Programming with Bananas, Lenses, Envelopes and Barbed Wire
313:
A Haskell definition of an unfold, or anamorphism for lists, called
148:
_into_ a coinductive datatype by specifying a coalgebra structure
124:
The data type in question is defined as the greatest fixed point
1350:
To prove this, we can implement both using our generic unfold,
1192:
takes a pair of lists, say and and returns a list of pairs .
1582:(and catamorphisms are the categorical dual of anamorphisms).
38:
The above layman's description can be stated more formally in
1630:, and since it is assumed to be final we know that whenever (
1876:, after which anamorphisms are sometimes referred to as
1550:
In a language like
Haskell, even the abstract functions
1143:, with the recursive mentions of the type replaced with
1844:
1783:
1742:
564:
For example, the unfold for the tree data structure
432:We can now implement quite general functions using
1864:
1818:
1768:
1858:
1848:
164:As an example, the type of potentially infinite
1819:{\displaystyle \mathrm {fin} \circ h=Fh\circ f}
180:and a further list, or it is empty. A (pseudo-)
144:. Thus, one can define functions from a type
8:
1906:An anamorphism followed by an catamorphism:
280:One can easily check that indeed the type
1949:
1843:
1784:
1782:
1749:
1741:
79:(aka opposite) of the anamorphism is the
1912:Extension of the idea of catamorphisms:
1933:
1918:Extension of the idea of anamorphisms:
1900:From an initial algebra to an algebra:
1968:
1957:
99:is a generalization of the concept of
87:Anamorphisms in functional programming
553:Anamorphisms on other data structures
212:It is the fixed point of the functor
7:
1585:That means the following. Suppose (
1354:, using a simple recursive routine:
1769:{\displaystyle h=\mathrm {ana} \ f}
176:, i.e. a list consists either of a
160:Example: Potentially infinite lists
1791:
1788:
1785:
1756:
1753:
1750:
1166:, which was in the context of the
184:-Definition might look like this:
14:
1872:. The brackets used are known as
1714:that uniquely specified morphism
297:for lists (then usually known as
117:construct a result of a certain
1566:Anamorphisms in category theory
1188:are examples of anamorphisms.
168:(with elements of a fixed type
1859:
1855:
1849:
1845:
172:) is given as the fixed point
1:
109:. Formally, anamorphisms are
18:Anamorphosis (disambiguation)
62:. These objects are used in
46:denotes the assignment of a
30:In computer programming, an
1838:found in the literature is
436:, for example a countdown:
2026:
1654:), there will be a unique
22:
15:
1356:
1267:-- || means 'or'
1198:
915:
798:
624:
566:
438:
319:
218:
186:
23:Not to be confused with
1990:Anamorphisms in Haskell
1642:-coalgebra (a morphism
1574:, anamorphisms are the
42:: the anamorphism of a
1967:Cite journal requires
1866:
1820:
1770:
1677:), that is a morphism
1170:programming language.
546:will compute the list
93:functional programming
64:functional programming
1867:
1821:
1771:
1701:. Then for each such
796:can be defined thus:
174:= ν X . value × X + 1
1842:
1781:
1740:
909:appears by renaming
16:For other uses, see
1834:A notation for ana
1614:into itself. Thus,
1862:
1816:
1766:
2010:Recursion schemes
1762:
905:The analogy with
317:, is as follows:
283:is isomorphic to
111:generic functions
2017:
1977:
1976:
1970:
1965:
1963:
1955:
1953:
1938:
1871:
1869:
1868:
1865:{\displaystyle }
1863:
1825:
1823:
1822:
1817:
1794:
1775:
1773:
1772:
1767:
1760:
1759:
1576:categorical dual
1561:
1557:
1553:
1546:
1543:
1540:
1537:
1534:
1531:
1528:
1525:
1522:
1519:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1495:
1492:
1489:
1486:
1483:
1480:
1477:
1474:
1471:
1468:
1465:
1462:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1417:
1414:
1411:
1408:
1405:
1402:
1399:
1396:
1393:
1390:
1387:
1384:
1381:
1378:
1375:
1372:
1369:
1366:
1363:
1360:
1353:
1346:
1343:
1340:
1337:
1334:
1331:
1328:
1325:
1322:
1319:
1316:
1313:
1310:
1307:
1304:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1195:
1191:
1187:
1182:
1146:
1142:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
912:
908:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
817:
814:
811:
808:
805:
802:
795:
791:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
618:
615:
612:
609:
606:
603:
600:
597:
594:
591:
588:
585:
582:
579:
576:
573:
570:
548:
545:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
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:
350:
347:
344:
341:
338:
335:
332:
329:
326:
323:
316:
308:
304:
289:
286:
282:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
225:
222:
215:
208:
205:
202:
199:
196:
193:
190:
142:a : A → F A
77:categorical dual
44:coinductive type
2025:
2024:
2020:
2019:
2018:
2016:
2015:
2014:
2005:Category theory
1995:
1994:
1986:
1981:
1980:
1966:
1956:
1940:
1939:
1935:
1930:
1886:
1840:
1839:
1832:
1779:
1778:
1738:
1737:
1572:category theory
1568:
1559:
1555:
1551:
1548:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1487:
1484:
1481:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1448:
1445:
1442:
1439:
1436:
1433:
1430:
1427:
1424:
1421:
1418:
1415:
1412:
1409:
1406:
1403:
1400:
1397:
1394:
1391:
1388:
1385:
1382:
1379:
1376:
1373:
1370:
1367:
1364:
1361:
1358:
1351:
1348:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1269:
1266:
1263:
1260:
1257:
1254:
1251:
1248:
1245:
1242:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1200:
1193:
1189:
1185:
1180:
1178:Functions like
1176:
1153:
1144:
1140:
1137:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
910:
906:
903:
902:
899:
896:
893:
890:
887:
884:
881:
878:
875:
872:
869:
866:
863:
860:
857:
854:
851:
848:
845:
842:
839:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
800:
793:
789:
786:
785:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
635:
632:
629:
626:
620:
619:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
555:
547:
543:
540:
539:
536:
533:
530:
527:
524:
521:
518:
515:
512:
509:
506:
503:
500:
497:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
440:
430:
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:
348:
345:
342:
339:
336:
333:
330:
327:
324:
321:
314:
306:
305:and a function
302:
288:
284:
281:
278:
277:
274:
271:
268:
265:
262:
259:
256:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
223:
220:
213:
210:
209:
206:
203:
200:
197:
194:
191:
188:
162:
105:on coinductive
89:
56:final coalgebra
40:category theory
28:
21:
12:
11:
5:
2023:
2021:
2013:
2012:
2007:
1997:
1996:
1993:
1992:
1985:
1984:External links
1982:
1979:
1978:
1969:|journal=
1932:
1931:
1929:
1926:
1925:
1924:
1923:
1922:
1916:
1910:
1904:
1892:
1885:
1882:
1861:
1857:
1854:
1851:
1847:
1831:
1828:
1827:
1826:
1815:
1812:
1809:
1806:
1803:
1800:
1797:
1793:
1790:
1787:
1776:
1765:
1758:
1755:
1752:
1748:
1745:
1567:
1564:
1357:
1199:
1175:
1172:
1152:
1149:
916:
799:
625:
622:is as follows
567:
554:
551:
439:
320:
219:
187:
161:
158:
136:for any other
88:
85:
50:to its unique
13:
10:
9:
6:
4:
3:
2:
2022:
2011:
2008:
2006:
2003:
2002:
2000:
1991:
1988:
1987:
1983:
1974:
1961:
1952:
1951:10.1.1.41.125
1947:
1943:
1937:
1934:
1927:
1921:
1917:
1915:
1911:
1909:
1905:
1903:
1899:
1898:
1897:
1894:Morphisms of
1893:
1891:
1888:
1887:
1883:
1881:
1879:
1875:
1874:lens brackets
1852:
1837:
1829:
1813:
1810:
1807:
1804:
1801:
1798:
1795:
1777:
1763:
1746:
1743:
1736:
1735:
1734:
1732:
1728:
1724:
1719:
1717:
1713:
1712:
1708:
1705:we denote by
1704:
1700:
1698:
1694:
1688:
1684:
1680:
1676:
1672:
1668:
1664:
1660:
1657:
1653:
1649:
1645:
1641:
1638:) is another
1637:
1633:
1629:
1625:
1621:
1617:
1613:
1609:
1606:
1602:
1600:
1596:
1592:
1588:
1583:
1581:
1580:catamorphisms
1577:
1573:
1565:
1563:
1355:
1197:
1183:
1173:
1171:
1169:
1165:
1162:
1158:
1150:
1148:
914:
913:in its type:
797:
623:
565:
562:
560:
552:
550:
437:
435:
318:
311:
300:
296:
291:
217:
185:
183:
179:
175:
171:
167:
159:
157:
155:
151:
147:
143:
139:
135:
134:A → ν X . F X
131:
128:of a functor
127:
122:
120:
116:
115:corecursively
112:
108:
104:
103:
98:
94:
86:
84:
82:
78:
73:
71:
70:
65:
61:
57:
53:
49:
45:
41:
36:
33:
26:
19:
1960:cite journal
1942:Meijer, Erik
1936:
1914:Paramorphism
1908:Hylomorphism
1902:Catamorphism
1877:
1873:
1835:
1833:
1730:
1726:
1722:
1720:
1715:
1710:
1709:
1706:
1702:
1696:
1692:
1690:
1686:
1682:
1678:
1674:
1670:
1666:
1662:
1658:
1656:homomorphism
1651:
1647:
1643:
1639:
1635:
1631:
1627:
1623:
1615:
1607:
1598:
1590:
1586:
1584:
1569:
1549:
1349:
1177:
1174:Applications
1163:
1156:
1154:
1138:
904:
787:
621:
563:
558:
556:
541:
433:
431:
312:
298:
294:
292:
279:
211:
177:
173:
169:
163:
153:
149:
145:
141:
137:
133:
129:
125:
123:
100:
96:
90:
81:catamorphism
74:
67:
37:
31:
29:
25:Catamorphism
1920:Apomorphism
1605:endofunctor
1161:Erik Meijer
561:for lists.
295:anamorphism
287:, and thus
140:-coalgebra
97:anamorphism
60:endofunctor
32:anamorphism
1999:Categories
1928:References
1896:F-algebras
1733:as above:
1689:such that
1601:-coalgebra
534:oneSmaller
528:oneSmaller
504:oneSmaller
483:oneSmaller
1946:CiteSeerX
1811:∘
1796:∘
1603:for some
216:, where:
126:ν X . F X
113:that can
48:coalgebra
1890:Morphism
1884:See also
1830:Notation
1620:morphism
1612:category
1610:of some
1488:iterate2
1168:Squiggol
427:stateNew
406:stateNew
382:stateOld
370:stateOld
285:F value
52:morphism
1695:h = Fh
1593:) is a
1330:iterate
1309:iterate
1194:Iterate
1186:iterate
1151:History
1074:anaTree
1017:newtype
963:anaList
918:newtype
846:newtype
801:newtype
777:unspool
759:unspool
699:unspool
687:unspool
544:ana f 3
516:Nothing
489:current
474:current
388:Nothing
242:Nothing
214:F value
182:Haskell
102:unfolds
69:unfolds
54:to the
1948:
1878:lenses
1761:
1729:, and
1669:) to (
1661:from (
1556:unfold
1164:et al.
1122:tree_a
1110:tree_a
1098:tree_a
1089:Either
1083:tree_a
1041:Either
1035:unNode
1002:list_a
990:list_a
972:list_a
936:unCons
870:Either
864:unNode
819:unCons
750:Branch
642:Either
590:Branch
299:unfold
58:of an
1681:from
1646:from
1622:from
1618:is a
1595:final
1542:False
1539:->
1509:->
1374:where
1159:, by
1125:->
1116:->
1086:->
1005:->
996:->
978:Maybe
975:->
942:Maybe
825:Maybe
747:->
723:Right
714:->
675:->
669:->
639:->
453:Maybe
450:->
415:value
412:->
400:value
391:->
361:->
358:state
355:->
349:state
343:value
337:Maybe
334:->
331:state
266:value
260:Maybe
251:value
224:Maybe
198:value
178:value
170:value
166:lists
107:lists
95:, an
1973:help
1691:fin
1558:and
1552:fold
1425:unsp
1368:unsp
1359:zip2
1273:else
1270:then
1184:and
1128:Tree
1065:Tree
1050:Tree
1029:Tree
1020:Tree
1008:List
954:List
930:List
921:List
894:Tree
879:Tree
858:Tree
849:Tree
837:List
813:List
804:List
794:List
792:and
790:Tree
717:Leaf
708:Left
696:case
678:Tree
611:Tree
596:Tree
581:Leaf
572:Tree
569:data
522:Just
519:else
513:then
507:<
394:Just
376:case
293:The
245:data
233:Just
221:data
189:data
119:type
75:The
1731:fin
1707:ana
1685:to
1675:fin
1650:to
1626:to
1616:fin
1591:fin
1578:of
1570:In
1560:ana
1497:ana
1473:),(
1377:fin
1371:fin
1365:ana
1352:ana
1297:zip
1201:zip
1190:zip
1181:zip
1141:ana
1071:))}
907:ana
900:))}
774:ana
756:ana
684:ana
627:ana
559:ana
480:let
465:Int
459:Int
447:Int
434:ana
421:ana
364:ana
322:ana
315:ana
152:on
91:In
66:as
2001::
1964::
1962:}}
1958:{{
1880:.
1725:,
1718:.
1673:,
1665:,
1652:FX
1634:,
1628:FA
1589:,
1554:,
1527:))
1485:))
1482:bs
1476:as
1461:((
1455:))
1452:bs
1440:),
1437:as
1428:((
1419:==
1416:bs
1410:||
1404:==
1401:as
1389:bs
1383:as
1345:))
1303:bs
1300:as
1261:==
1258:bs
1252:||
1246:==
1243:as
1237:if
1228:bs
1213:as
1147:.
1113:))
1077:::
1038:::
993:))
966:::
960:)}
939:::
867:::
843:)}
822:::
705:of
666:))
630:::
549:.
501:if
498:in
444:::
385:of
352:))
325:::
156:.
83:.
72:.
1975:)
1971:(
1954:.
1860:]
1856:)
1853:f
1850:(
1846:[
1836:f
1814:f
1808:h
1805:F
1802:=
1799:h
1792:n
1789:i
1786:f
1764:f
1757:a
1754:n
1751:a
1747:=
1744:h
1727:A
1723:F
1716:h
1711:f
1703:f
1699:f
1697:.
1693:.
1687:A
1683:X
1679:h
1671:A
1667:f
1663:X
1659:h
1648:X
1644:f
1640:F
1636:f
1632:X
1624:A
1608:F
1599:F
1587:A
1545:)
1536:x
1533:\
1530:(
1524:a
1521:f
1518:,
1515:a
1512:(
1506:a
1503:\
1500:(
1494:=
1491:f
1479:,
1470:b
1467:,
1464:a
1458:=
1449::
1446:b
1443:(
1434::
1431:a
1422:)
1413:(
1407:)
1398:(
1395:=
1392:)
1386:,
1380:(
1362:=
1342:x
1339:f
1336:(
1333:f
1327:(
1324::
1321:x
1318:=
1315:x
1312:f
1306:)
1294:(
1291::
1288:)
1285:b
1282:,
1279:a
1276:(
1264:)
1255:(
1249:)
1240:(
1234:=
1231:)
1225::
1222:b
1219:(
1216:)
1210::
1207:a
1204:(
1145:b
1134:)
1131:a
1119:(
1107:,
1104:a
1101:,
1095:(
1092:a
1080:(
1068:a
1062:,
1059:a
1056:,
1053:a
1047:(
1044:a
1032:{
1026:=
1023:a
1014:)
1011:a
999:(
987:,
984:a
981:(
969:(
957:a
951:,
948:a
945:(
933:{
927:=
924:a
911:b
897:a
891:,
888:a
885:,
882:a
876:(
873:a
861:{
855:=
852:a
840:a
834:,
831:a
828:(
816:{
810:=
807:a
783:)
780:r
771:(
768:x
765:)
762:l
753:(
744:)
741:r
738:,
735:x
732:,
729:l
726:(
720:a
711:a
702:x
693:=
690:x
681:a
672:b
663:b
660:,
657:a
654:,
651:b
648:(
645:a
636:b
633:(
617:)
614:a
608:(
605:a
602:)
599:a
593:(
587:|
584:a
578:=
575:a
537:)
531:,
525:(
510:0
495:1
492:-
486:=
477:=
471:f
468:)
462:,
456:(
441:f
424:f
418::
409:)
403:,
397:(
379:f
373:=
367:f
346:,
340:(
328:(
307:f
303:x
275:)
272:x
269:,
263:(
257:=
254:x
248:F
239:|
236:a
230:=
227:a
207:|
204:)
201::
195:(
192:=
154:A
150:a
146:A
138:F
130:F
27:.
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.