282:
58:
1769:'s argument is called element, and the function returns this. We know that this is the first element because of the way lists are defined, a single element constructed onto a list. This single element must be the first. The empty list would not match the pattern at all, as an empty list does not have a head (the first element that is constructed).
469:
More complex patterns can be built from the primitive ones of the previous section, usually in the same way as values are built by combining other values. The difference then is that with variable and wildcard parts, a pattern doesn't build into a single value, but matches a group of values that are
393:
Here, 0 is a single value pattern. Now, whenever f is given 0 as argument the pattern matches and the function returns 1. With any other argument, the matching and thus the function fail. As the syntax supports alternative patterns in function definitions, we can continue the definition extending it
1872:
The main advantage of symbolic string manipulation is that it can be completely integrated with the rest of the programming language, rather than being a separate, special purpose subunit. The entire power of the language can be leveraged to build up the patterns themselves or analyze and transform
1588:
In symbolic programming languages, it is easy to have patterns as arguments to functions or as elements of data structures. A consequence of this is the ability to use patterns to declaratively make statements about pieces of data and to flexibly instruct functions how to operate.
1696:
In
Mathematica, strings are represented as trees of root StringExpression and all the characters in order as children of the root. Thus, to match "any amount of trailing characters", a new wildcard ___ is needed in contrast to _ that would match only a single character.
373:
The simplest pattern in pattern matching is an explicit value or a variable. For an example, consider a simple function definition in
Haskell syntax (function parameters are not in parentheses but are separated by spaces, = is not assignment but definition):
624:
and a function to re-balance it after element insertion shows how to match on a more complex structure generated by a recursive data type. The compiler verifies at compile-time that the list of cases is exhaustive and none are redundant.
1684:
By far the most common form of pattern matching involves strings of characters. In many programming languages, a particular syntax of strings is used to represent regular expressions, which are patterns describing string characters.
182:. Uses of pattern matching include outputting the locations (if any) of a pattern within a token sequence, to output some component of the matched pattern, and to substitute the matching pattern with some other token sequence (i.e.,
473:
A tree pattern describes a part of a tree by starting with a node and specifying some branches and nodes and leaving some unspecified with a variable or wildcard pattern. It may help to think of the
259:
Often it is possible to give alternative patterns that are tried one by one, which yields a powerful conditional programming construct. Pattern matching sometimes includes support for
1928:
SNOBOL was quite widely taught in larger US universities in the late 1960s and early 1970s and was widely used in the 1970s and 1980s as a text manipulation language in the
442:), patterns are tried in order so the first definition still applies in the very specific case of the input being 0, while for any other argument the function returns
438:
is a single variable pattern, which will match absolutely any argument and bind it to name n to be used in the rest of the definition. In
Haskell (unlike at least
1600:
can be used to make more efficient versions of the code. In the following example the details do not particularly matter; what matters is that the subexpression
1481:
In
Mathematica, it is also possible to extract structures as they are created in the course of computation, regardless of how or where they appear. The function
1917:
a data type whose values can be manipulated in all ways permitted to any other data type in the programming language) and by providing operators for pattern
543:
If we pass a variable that is of type Color, how can we get the data out of this variable? For example, for a function to get the integer part of
2084:
2649:
1688:
However, it is possible to perform some string pattern matching within the same framework that has been discussed throughout this article.
2060:
536:
with the data type, and thus we want to extract some data from the data type, for example, just the string or just the integer part of
2544:
2583:
2309:
2286:
Gimpel, J. F. 1973. A theory of discrete patterns and their implementation in SNOBOL4. Commun. ACM 16, 2 (Feb. 1973), 91–100. DOI=
2509:
1968:
1708:
of characters. A functional list is defined as an empty list, or an element constructed on an existing list. In
Haskell syntax:
2514:
1485:
can be used to monitor a computation, and return the elements that arise which match a pattern. For example, we can define the
1242:
In the traditional, more suitable syntax, the symbols are written as they are and the levels of the tree are represented using
174:, the match usually has to be exact: "either it will or will not be a match." The patterns generally have the form of either
122:
1734:. When pattern matching, we assert that a certain piece of data is equal to a certain pattern. For example, in the function:
94:
2331:
2519:
1922:
1834:
Symbolic entities can be introduced to represent many different classes of relevant features of a string. For instance,
470:
the combination of the concrete elements and the elements that are allowed to vary within the structure of the pattern.
101:
2730:
2504:
2010:
Perl
Compatible Regular Expressions, a common modern implementation of string pattern matching ported to many languages
253:
2139:
453:) is also simple: like a variable name, it matches any value, but does not bind the value to any name. Algorithms for
2598:
2539:
2411:
2303:
2114:
141:
75:
2359:
2446:
17:
108:
2771:
2766:
2029:
1661:
2626:
245:
209:
205:
79:
2073:
1278:
restricts the matches to nodes of that symbol. Note that even blanks themselves are internally represented as
1654:
221:
90:
2163:
2631:
2486:
533:
237:
233:
2710:
2436:
2341:
2319:
2080:
439:
329:
229:
225:
2715:
2593:
2560:
2496:
333:
293:
2347:
2761:
2725:
2621:
2565:
2466:
2420:
2380:. Journal of Symbolic Computation 43(12): 858–873. Describes in details flat matching in Mathematica.
1665:
610:
337:
217:
175:
2720:
2524:
2456:
1844:
1252:
A pattern in
Mathematica involves putting "_" at positions in that tree. For instance, the pattern
260:
2353:
2225:
2100:
2669:
2325:
2249:
362:
68:
1701:
1159:
Pattern matching can be used to filter data of a certain structure. For instance, in
Haskell a
521:
272:
31:
27:
Act of checking a given sequence of tokens for the presence of the constituents of some pattern
115:
2674:
2616:
2476:
2404:
2187:
2066:
1980:
1520:
Then, we can ask the question: Given fib, what is the sequence of recursive
Fibonacci calls?
1188:
2481:
2263:
2019:
1952:
1948:
474:
201:
8:
2679:
2201:
2001:
1892:
1673:
478:
171:
163:
39:
2383:
2608:
2575:
1991:
1986:
1956:
1944:
1910:
1160:
621:
529:
517:
The constructor is a node in a tree and the integer and string are leaves in branches.
454:
356:
352:
249:
190:
183:
46:
1301:
filters elements of the first argument that match the pattern in the second argument:
45:
For the use of variable matching criteria in defining abstract patterns to match, see
2740:
1903:
1895:
348:
2735:
2659:
2461:
2397:
2040:
1996:
1705:
1486:
155:
2588:
2529:
2441:
1899:
35:
2127:
2641:
2534:
2377:
2335:
2046:
1669:
179:
1925:. Strings generated during execution can be treated as programs and executed.
2755:
2451:
2428:
1918:
1909:
SNOBOL4 stands apart from most programming languages by having patterns as a
2315:
2238:
Joel Moses, "Symbolic
Integration", MIT Project MAC MAC-TR-47, December 1967
2654:
2471:
2287:
2024:
194:
2664:
1593:
1184:
344:
241:
1891:) is a computer programming language developed between 1962 and 1967 at
1840:
will match a string that consists of a letter first, and then a number.
457:
in simple string-matching situations have been developed in a number of
281:
1929:
458:
312:
Early programming languages with pattern matching constructs include
2342:
The Implementation of Functional Programming Languages, pages 53–103
1270:
denotes the piece of tree that can be varied. A symbol prepended to
609:
The creations of these functions can be automated by Haskell's data
57:
2013:
1539:
returns a structure that represents the occurrences of the pattern
2364:
2338:- provides the history of regular expressions in computer programs
189:
Sequence patterns (e.g., a text string) are often described using
2700:
2371:
1824:
will match a string that has two characters and begins with "a".
1613:
1274:
binds the match to that variable name while a symbol appended to
1192:
1149:(* the 'catch-all' case if no previous pattern matches *)
213:
167:
2308:
Nikolaas N. Oosterhof, Philip K. F. Hölzenspies, and Jan Kuper.
2037:
for a programming language based on one kind of pattern matching
2367:
2034:
1882:
325:
317:
204:
as a general tool to process data based on its structure, e.g.
1971:(AIML) for an AI language based on matching patterns in speech
484:
In Haskell, the following line defines an algebraic data type
1249:
is a tree with a as the parent, and b and c as the children.
617:
365:
generally support pattern matching on algebraic expressions.
321:
313:
1704:
languages in general, strings are represented as functional
1258:
will match elements such as A, A, or more generally A where
2684:
2140:"What's New In Python 3.10 — Python 3.10.0b3 documentation"
2007:
1940:
2389:
2312:. A presentation at Trends in Functional Programming, 2005
1807:
The equivalent Mathematica transformation is expressed as
1974:
1936:
2016:
for pattern matching used to implement language dialects
2226:"Patterns — The Swift Programming Language (Swift 5.1)"
1776:, so we can disregard it, and thus write the function:
2344:
Simon Peyton Jones, published by Prentice Hall, 1987.
1730:
The structure for a list with some elements is thus
1474:because only these elements will match the pattern
82:. Unsourced material may be challenged and removed.
1178:
2360:Prop: a C++ based pattern matching language, 1999
2164:"pattern_matching - Documentation for Ruby 3.0.0"
1935:Since SNOBOL's creation, newer languages such as
2753:
2188:"Pattern Syntax - The Rust Programming Language"
1947:fashionable. SNOBOL4 patterns, however, subsume
2365:PatMat: a C++ pattern matching library based on
2304:Views: An Extension to Haskell Pattern Matching
1679:
1195:syntax used thus far, this could be defined as
1154:
347:support pattern matching of various kinds: the
547:, we can use a simple tree pattern and write:
2405:
2386:pattern matching language for non-programmers
166:for the presence of the constituents of some
2332:An incomplete history of the QED Text Editor
1691:
1847:could be used to achieve the same matches:
162:is the act of checking a given sequence of
2412:
2398:
2328:: Online pattern matching for stock prices
2128:A Gentle Introduction to Haskell: Patterns
1943:have made string manipulation by means of
1813:
1583:
1163:could be used for this kind of filtering:
30:This article is about pattern matching in
2247:
324:(1968) with tree-based pattern matching,
142:Learn how and when to remove this message
2584:Comparison of regular-expression engines
2288:http://doi.acm.org/10.1145/361952.361960
1725:-- an element x constructed on a list xs
1191:, which is populated by symbols. In the
1187:, the only structure that exists is the
2322:language extended with pattern matching
1969:Artificial Intelligence Markup Language
449:The wildcard pattern (often written as
14:
2754:
2264:"Cases—Wolfram Language Documentation"
1364:of expressions. In the example below,
240:and the symbolic mathematics language
2545:Zhu–Takaoka string matching algorithm
2393:
2043:— metaphoric, drawn from architecture
1889:StriNg Oriented and symBOlic Language
1217:An example tree could then look like
368:
359:support the OR operator in searches.
193:and matched using techniques such as
1765:We assert that the first element of
1664:between proofs and programs relates
492:that wraps an integer and a string.
328:(1972), St Andrews Static Language (
276:
80:adding citations to reliable sources
51:
2510:Boyer–Moore string-search algorithm
1772:In the example, we have no use for
488:that has a single data constructor
248:for expressing tree patterns and a
24:
1951:grammars, which are equivalent to
25:
2783:
2599:Nondeterministic finite automaton
2540:Two-way string-matching algorithm
2297:
2072:Python Reference Manual, chapter
1616:for the purposes of compilation:
273:Regular expression § History
256:and value retrieval based on it.
1873:the programs that contain them.
1543:in the computational structure:
1360:Pattern matching applies to the
532:, we wish to write functions to
464:
394:to take more generic arguments:
280:
56:
2280:
2256:
2241:
2065:The Haskell 98 Report, chapter
2030:Tom (pattern matching language)
1266:is the concrete element, while
1179:Pattern matching in Mathematica
200:Tree patterns are used in some
67:needs additional citations for
2515:Boyer–Moore–Horspool algorithm
2505:Apostolico–Giancarlo algorithm
2250:"Wildcard matching algorithms"
2248:Cantatore, Alessandro (2003).
2232:
2218:
2194:
2180:
2156:
2132:
2121:
2107:
2093:
2083:Programming Language, chapter
2059:The Mathematica Book, chapter
1818:In Mathematica, for instance,
477:of a programming language and
13:
1:
2115:"Pattern Matching - F# Guide"
2101:"Pattern Matching - C# Guide"
2052:
1983:pattern matches C source code
1827:The same pattern in Haskell:
1608:that expressions of the form
1262:is any entity. In this case,
461:and non-recursive varieties.
355:search, and some versions of
2520:Knuth–Morris–Pratt algorithm
2447:Damerau–Levenshtein distance
1680:Pattern matching and strings
1155:Filtering data with patterns
7:
2711:Compressed pattern matching
2437:Approximate string matching
2419:
1962:
1668:-style pattern matching to
1662:Curry–Howard correspondence
446:with n being the argument.
10:
2788:
2716:Longest common subsequence
2627:Needleman–Wunsch algorithm
2497:String-searching algorithm
1880:
270:
266:
44:
29:
2726:Sequential pattern mining
2693:
2640:
2607:
2574:
2566:Commentz-Walter algorithm
2554:Multiple string searching
2553:
2495:
2487:Wagner–Fischer algorithm
2427:
2348:Nemerle, pattern matching
2074:6.3 Assignment statements
1876:
1692:Tree patterns for strings
1297:The Mathematica function
338:Kent Recursive Calculator
2736:String rewriting systems
2721:Longest common substring
2632:Smith–Waterman algorithm
2457:Gestalt pattern matching
2354:Erlang, pattern matching
1849:
1829:
1778:
1736:
1710:
1618:
1545:
1522:
1491:
1442:
1366:
1340:
1303:
1219:
1197:
1165:
627:
620:example which defines a
580:
549:
494:
396:
376:
363:Computer algebra systems
2670:Generalized suffix tree
2594:Thompson's construction
1955:and more powerful than
1814:Example string patterns
1584:Declarative programming
1245:, so that for instance
2772:Functional programming
2767:Conditional constructs
2622:Hirschberg's algorithm
1906:and Ivan P. Polonsky.
1702:functional programming
520:When we want to write
34:. For other uses, see
32:functional programming
2477:Levenshtein automaton
2467:Jaro–Winkler distance
2268:reference.wolfram.com
2067:3.17 Pattern Matching
2061:Section 2.3: Patterns
1953:context-free grammars
1911:first-class data type
1612:can be assumed to be
254:conditional execution
202:programming languages
2525:Rabin–Karp algorithm
2482:Levenshtein distance
2384:EasyPattern language
2310:Application patterns
2020:Symbolic integration
1657:also work this way.
479:algebraic data types
475:abstract syntax tree
76:improve this article
2680:Ternary search tree
2206:Scala Documentation
2014:REBOL parse dialect
2002:Pattern recognition
1957:regular expressions
1945:regular expressions
1674:proof by exhaustion
191:regular expressions
172:pattern recognition
40:pattern recognition
2609:Sequence alignment
2576:Regular expression
2202:"Pattern Matching"
2168:docs.ruby-lang.org
2004:for fuzzy patterns
1992:glob (programming)
1987:Matching wildcards
1592:For instance, the
1487:Fibonacci sequence
1161:list comprehension
530:abstract data type
455:matching wildcards
369:Primitive patterns
353:regular expression
292:. You can help by
250:language construct
184:search and replace
91:"Pattern matching"
47:regular expression
2749:
2748:
2741:String operations
1904:Ralph E. Griswold
1896:Bell Laboratories
1837:StringExpression
1821:StringExpression
1602:{{com, Integer}}
310:
309:
170:. In contrast to
152:
151:
144:
126:
16:(Redirected from
2779:
2762:Pattern matching
2706:Pattern matching
2660:Suffix automaton
2462:Hamming distance
2414:
2407:
2400:
2391:
2390:
2291:
2284:
2278:
2277:
2275:
2274:
2260:
2254:
2253:
2245:
2239:
2236:
2230:
2229:
2222:
2216:
2215:
2213:
2212:
2198:
2192:
2191:
2184:
2178:
2177:
2175:
2174:
2160:
2154:
2153:
2151:
2150:
2136:
2130:
2125:
2119:
2118:
2111:
2105:
2104:
2097:
2041:Pattern language
1997:Pattern calculus
1868:
1865:
1862:
1859:
1856:
1853:
1803:
1800:
1797:
1794:
1791:
1788:
1785:
1782:
1775:
1768:
1761:
1758:
1755:
1752:
1749:
1746:
1743:
1740:
1733:
1726:
1723:
1720:
1717:
1714:
1713:-- an empty list
1649:
1646:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1611:
1607:
1603:
1599:
1579:
1576:
1573:
1570:
1567:
1564:
1561:
1558:
1555:
1552:
1549:
1542:
1535:
1532:
1529:
1526:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1495:
1484:
1477:
1470:
1467:
1464:
1461:
1458:
1455:
1452:
1449:
1446:
1436:
1433:
1430:
1427:
1424:
1421:
1418:
1415:
1412:
1409:
1406:
1403:
1400:
1397:
1394:
1391:
1388:
1385:
1382:
1379:
1376:
1373:
1370:
1356:
1353:
1350:
1347:
1344:
1334:
1331:
1328:
1325:
1322:
1319:
1316:
1313:
1310:
1307:
1300:
1293:
1289:
1285:
1281:
1277:
1273:
1269:
1265:
1248:
1244:
1238:
1235:
1232:
1229:
1226:
1223:
1213:
1210:
1207:
1204:
1201:
1169:
1150:
1147:
1144:
1141:
1138:
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:
916:
913:
910:
907:
904:
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:
799:
796:
793:
790:
787:
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:
605:
602:
599:
596:
593:
590:
589:ColorConstructor
587:
584:
574:
571:
568:
565:
562:
559:
558:ColorConstructor
556:
553:
546:
539:
527:
513:
510:
507:
506:ColorConstructor
504:
501:
498:
491:
490:ColorConstructor
487:
452:
445:
437:
434:Here, the first
430:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
389:
386:
383:
380:
305:
302:
284:
277:
160:pattern matching
156:computer science
147:
140:
136:
133:
127:
125:
84:
60:
52:
21:
18:Pattern-matching
2787:
2786:
2782:
2781:
2780:
2778:
2777:
2776:
2752:
2751:
2750:
2745:
2689:
2636:
2603:
2589:Regular grammar
2570:
2549:
2530:Raita algorithm
2491:
2442:Bitap algorithm
2423:
2418:
2300:
2295:
2294:
2285:
2281:
2272:
2270:
2262:
2261:
2257:
2246:
2242:
2237:
2233:
2224:
2223:
2219:
2210:
2208:
2200:
2199:
2195:
2186:
2185:
2181:
2172:
2170:
2162:
2161:
2157:
2148:
2146:
2144:docs.python.org
2138:
2137:
2133:
2126:
2122:
2113:
2112:
2108:
2099:
2098:
2094:
2089:
2055:
1965:
1900:David J. Farber
1885:
1879:
1870:
1869:
1866:
1863:
1860:
1857:
1854:
1851:
1838:
1832:
1831:
1822:
1816:
1811:
1805:
1804:
1801:
1798:
1795:
1792:
1789:
1786:
1783:
1780:
1773:
1766:
1763:
1762:
1759:
1756:
1753:
1750:
1747:
1744:
1741:
1738:
1731:
1728:
1727:
1724:
1721:
1718:
1715:
1712:
1700:In Haskell and
1694:
1682:
1651:
1650:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1609:
1605:
1601:
1597:
1586:
1581:
1580:
1577:
1574:
1571:
1568:
1565:
1562:
1559:
1556:
1553:
1550:
1547:
1540:
1537:
1536:
1533:
1530:
1527:
1524:
1518:
1517:
1514:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1482:
1475:
1472:
1471:
1468:
1465:
1462:
1459:
1456:
1453:
1450:
1447:
1444:
1438:
1437:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1389:
1386:
1383:
1380:
1377:
1374:
1371:
1368:
1358:
1357:
1354:
1351:
1348:
1345:
1342:
1336:
1335:
1332:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1308:
1305:
1298:
1291:
1287:
1283:
1279:
1275:
1271:
1267:
1263:
1256:
1246:
1243:
1240:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1215:
1214:
1211:
1208:
1205:
1202:
1199:
1181:
1176:
1171:
1170:
1167:
1157:
1152:
1151:
1148:
1145:
1142:
1139:
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:
914:
911:
908:
905:
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:
797:
794:
791:
788:
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:
607:
606:
603:
600:
597:
594:
591:
588:
585:
582:
576:
575:
572:
569:
566:
563:
560:
557:
554:
551:
544:
537:
525:
515:
514:
511:
508:
505:
502:
499:
496:
489:
485:
467:
450:
443:
435:
432:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
391:
390:
387:
384:
381:
378:
371:
306:
300:
297:
290:needs expansion
275:
269:
180:tree structures
148:
137:
131:
128:
85:
83:
73:
61:
50:
43:
36:string matching
28:
23:
22:
15:
12:
11:
5:
2785:
2775:
2774:
2769:
2764:
2747:
2746:
2744:
2743:
2738:
2733:
2728:
2723:
2718:
2713:
2708:
2703:
2697:
2695:
2691:
2690:
2688:
2687:
2682:
2677:
2672:
2667:
2662:
2657:
2652:
2646:
2644:
2642:Data structure
2638:
2637:
2635:
2634:
2629:
2624:
2619:
2613:
2611:
2605:
2604:
2602:
2601:
2596:
2591:
2586:
2580:
2578:
2572:
2571:
2569:
2568:
2563:
2557:
2555:
2551:
2550:
2548:
2547:
2542:
2537:
2535:Trigram search
2532:
2527:
2522:
2517:
2512:
2507:
2501:
2499:
2493:
2492:
2490:
2489:
2484:
2479:
2474:
2469:
2464:
2459:
2454:
2449:
2444:
2439:
2433:
2431:
2425:
2424:
2417:
2416:
2409:
2402:
2394:
2388:
2387:
2381:
2376:Temur Kutsia.
2374:
2362:
2357:
2351:
2345:
2339:
2336:Dennis Ritchie
2329:
2323:
2313:
2306:
2299:
2298:External links
2296:
2293:
2292:
2279:
2255:
2240:
2231:
2217:
2193:
2179:
2155:
2131:
2120:
2106:
2091:
2090:
2088:
2087:
2077:
2070:
2063:
2056:
2054:
2051:
2050:
2049:
2047:Graph matching
2044:
2038:
2032:
2027:
2022:
2017:
2011:
2005:
1999:
1994:
1989:
1984:
1978:
1972:
1964:
1961:
1881:Main article:
1878:
1875:
1850:
1836:
1830:
1820:
1815:
1812:
1810:head:=element
1809:
1779:
1737:
1711:
1693:
1690:
1681:
1678:
1619:
1585:
1582:
1546:
1523:
1492:
1443:
1367:
1341:
1304:
1254:
1220:
1198:
1180:
1177:
1175:
1166:
1156:
1153:
628:
622:red–black tree
581:
550:
495:
466:
463:
397:
377:
370:
367:
340:(KRC) (1981).
308:
307:
287:
285:
268:
265:
150:
149:
64:
62:
55:
26:
9:
6:
4:
3:
2:
2784:
2773:
2770:
2768:
2765:
2763:
2760:
2759:
2757:
2742:
2739:
2737:
2734:
2732:
2729:
2727:
2724:
2722:
2719:
2717:
2714:
2712:
2709:
2707:
2704:
2702:
2699:
2698:
2696:
2692:
2686:
2683:
2681:
2678:
2676:
2673:
2671:
2668:
2666:
2663:
2661:
2658:
2656:
2653:
2651:
2648:
2647:
2645:
2643:
2639:
2633:
2630:
2628:
2625:
2623:
2620:
2618:
2615:
2614:
2612:
2610:
2606:
2600:
2597:
2595:
2592:
2590:
2587:
2585:
2582:
2581:
2579:
2577:
2573:
2567:
2564:
2562:
2559:
2558:
2556:
2552:
2546:
2543:
2541:
2538:
2536:
2533:
2531:
2528:
2526:
2523:
2521:
2518:
2516:
2513:
2511:
2508:
2506:
2503:
2502:
2500:
2498:
2494:
2488:
2485:
2483:
2480:
2478:
2475:
2473:
2470:
2468:
2465:
2463:
2460:
2458:
2455:
2453:
2452:Edit distance
2450:
2448:
2445:
2443:
2440:
2438:
2435:
2434:
2432:
2430:
2429:String metric
2426:
2422:
2415:
2410:
2408:
2403:
2401:
2396:
2395:
2392:
2385:
2382:
2379:
2378:Flat Matching
2375:
2373:
2369:
2366:
2363:
2361:
2358:
2355:
2352:
2349:
2346:
2343:
2340:
2337:
2333:
2330:
2327:
2324:
2321:
2317:
2314:
2311:
2307:
2305:
2302:
2301:
2289:
2283:
2269:
2265:
2259:
2251:
2244:
2235:
2227:
2221:
2207:
2203:
2197:
2189:
2183:
2169:
2165:
2159:
2145:
2141:
2135:
2129:
2124:
2116:
2110:
2102:
2096:
2092:
2086:
2085:4.3: Patterns
2082:
2078:
2075:
2071:
2068:
2064:
2062:
2058:
2057:
2048:
2045:
2042:
2039:
2036:
2033:
2031:
2028:
2026:
2023:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1998:
1995:
1993:
1990:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1966:
1960:
1958:
1954:
1950:
1946:
1942:
1938:
1933:
1931:
1926:
1924:
1920:
1919:concatenation
1916:
1912:
1907:
1905:
1901:
1897:
1894:
1890:
1884:
1874:
1848:
1846:
1841:
1835:
1828:
1825:
1819:
1808:
1777:
1770:
1735:
1709:
1707:
1703:
1698:
1689:
1686:
1677:
1675:
1671:
1670:case analysis
1667:
1663:
1658:
1656:
1653:Mailboxes in
1617:
1615:
1595:
1590:
1544:
1521:
1490:
1488:
1479:
1441:
1365:
1363:
1339:
1338:evaluates to
1302:
1295:
1261:
1253:
1250:
1234:"c"
1225:"a"
1218:
1196:
1194:
1190:
1186:
1174:
1173:evaluates to
1164:
1162:
626:
623:
619:
614:
612:
579:
548:
541:
535:
531:
523:
518:
493:
482:
480:
476:
471:
465:Tree patterns
462:
460:
456:
447:
441:
395:
375:
366:
364:
360:
358:
354:
350:
346:
341:
339:
335:
331:
327:
323:
319:
315:
304:
295:
291:
288:This section
286:
283:
279:
278:
274:
264:
262:
257:
255:
251:
247:
244:have special
243:
239:
235:
231:
227:
223:
219:
215:
211:
207:
203:
198:
196:
192:
187:
185:
181:
177:
173:
169:
165:
161:
157:
146:
143:
135:
132:February 2011
124:
121:
117:
114:
110:
107:
103:
100:
96:
93: –
92:
88:
87:Find sources:
81:
77:
71:
70:
65:This article
63:
59:
54:
53:
48:
41:
37:
33:
19:
2705:
2655:Suffix array
2561:Aho–Corasick
2472:Lee distance
2282:
2271:. Retrieved
2267:
2258:
2243:
2234:
2220:
2209:. Retrieved
2205:
2196:
2182:
2171:. Retrieved
2167:
2158:
2147:. Retrieved
2143:
2134:
2123:
2109:
2095:
2025:Tagged union
1934:
1927:
1914:
1908:
1888:
1886:
1871:
1843:In Haskell,
1842:
1839:
1833:
1826:
1823:
1817:
1806:
1771:
1764:
1732:element:list
1729:
1699:
1695:
1687:
1683:
1659:
1652:
1591:
1587:
1538:
1519:
1480:
1473:
1439:
1361:
1359:
1337:
1296:
1259:
1257:
1251:
1241:
1216:
1182:
1172:
1158:
615:
608:
577:
542:
519:
516:
483:
472:
468:
448:
433:
392:
372:
361:
345:text editors
342:
336:(1977), and
311:
298:
294:adding to it
289:
258:
199:
195:backtracking
188:
159:
153:
138:
129:
119:
112:
105:
98:
86:
74:Please help
69:verification
66:
2665:Suffix tree
1923:alternation
1594:Mathematica
1185:Mathematica
552:integerPart
444:n * f (n-1)
242:Mathematica
2756:Categories
2273:2020-11-17
2211:2021-01-17
2173:2021-07-06
2149:2021-07-06
2053:References
1981:Coccinelle
1930:humanities
1861:&&
1604:instructs
1203:SymbolTree
583:stringPart
573:theInteger
561:theInteger
349:QED editor
332:) (1976),
271:See also:
102:newspapers
2326:ShowTrend
1596:function
1362:structure
714:rebalance
604:theString
595:theString
578:As well:
534:interface
522:functions
459:recursive
351:supports
176:sequences
1977:language
1963:See also
1893:AT&T
1887:SNOBOL (
1627:Binomial
1614:integers
1440:returns
613:syntax.
524:to make
320:(1962),
316:(1957),
301:May 2008
2731:Sorting
2701:Parsing
2421:Strings
2372:SPITBOL
1864:isDigit
1855:isAlpha
1802:element
1787:element
1760:element
1745:element
1645:Integer
1630:Compile
1606:Compile
1598:Compile
1478:above.
1193:Haskell
509:Integer
267:History
214:Haskell
168:pattern
116:scholar
2368:SNOBOL
2318:: the
2316:JMatch
2035:SNOBOL
1883:SNOBOL
1877:SNOBOL
1858:letter
1845:guards
1655:Erlang
1231:Symbol
1222:Symbol
1212:String
1209:Symbol
611:record
512:String
326:Prolog
318:SNOBOL
261:guards
246:syntax
222:Python
164:tokens
118:
111:
104:
97:
89:
2694:Other
2650:DAFSA
2617:BLAST
1867:digit
1706:lists
1525:Trace
1483:Trace
1369:Cases
1306:Cases
1299:Cases
1288:Blank
1280:Blank
1143:->
1113:Black
1077:Black
1056:->
984:Black
903:Black
822:Black
741:Black
723:match
702:'
693:'
681:'
675:color
663:Empty
651:'
645:Black
633:color
618:OCaml
616:This
545:Color
538:Color
526:Color
500:Color
486:Color
343:Many
322:Refal
314:COMIT
238:Swift
234:Scala
123:JSTOR
109:books
2685:Trie
2675:Rope
2320:Java
2081:Pure
2079:The
2008:PCRE
1941:Perl
1939:and
1921:and
1915:i.e.
1781:head
1774:list
1767:head
1751:list
1739:head
1672:and
1660:The
1572:}},{
1476:a,_]
1290:for
1286:and
1282:for
1200:data
1189:tree
1107:Tree
1071:Tree
1059:Tree
1026:Tree
1002:Tree
978:Tree
933:Tree
921:Tree
897:Tree
852:Tree
828:Tree
816:Tree
759:Tree
747:Tree
735:Tree
729:with
708:tree
687:tree
669:Tree
657:tree
648:type
630:type
497:data
440:Hope
357:TECO
330:SASL
252:for
230:Rust
226:Ruby
95:news
38:and
2334:by
1975:AWK
1949:BNF
1937:Awk
1898:by
1648:}}]
1639:com
1621:com
1610:com
1575:fib
1569:fib
1566:},{
1563:fib
1557:fib
1551:fib
1541:fib
1531:fib
1515:fib
1509:fib
1503:fib
1494:fib
1489:as
1420:]},
1183:In
1065:Red
1053:)))
1032:Red
1008:Red
939:Red
927:Red
879:)),
858:Red
834:Red
765:Red
753:Red
711:let
639:Red
528:an
334:NPL
296:.
186:).
178:or
154:In
78:by
2758::
2266:.
2204:.
2166:.
2142:.
1959:.
1932:.
1902:,
1722:xs
1676:.
1666:ML
1636:{{
1624::=
1578:}}
1560:,{
1554:,{
1506::=
1497::=
1469:]}
1457:],
1402:],
1390:],
1327:},
1294:.
1292:_x
1255:A
1134:))
1098:),
972:))
960:),
798:),
786:),
672:of
540:.
481:.
263:.
236:,
232:,
228:,
224:,
220:,
218:ML
216:,
212:,
210:F#
208:,
206:C#
197:.
158:,
2413:e
2406:t
2399:v
2370:/
2356:.
2350:.
2290:.
2276:.
2252:.
2228:.
2214:.
2190:.
2176:.
2152:.
2117:.
2103:.
2076:.
2069:.
1913:(
1852:|
1799:=
1796:)
1793:_
1790::
1784:(
1757:=
1754:)
1748::
1742:(
1719::
1716:x
1642:,
1633:,
1548:{
1534:]
1528:,
1512:+
1500:1
1466:d
1463:,
1460:a
1454:d
1451:,
1448:a
1445:{
1435:]
1432:]
1429:_
1426:,
1423:a
1417:e
1414:,
1411:d
1408:,
1405:a
1399:d
1396:,
1393:a
1387:d
1384:,
1381:a
1378:,
1375:a
1372:,
1355:}
1352:a
1349:,
1346:a
1343:{
1333:]
1330:a
1324:b
1321:,
1318:a
1315:,
1312:b
1309:,
1284:_
1276:_
1272:_
1268:_
1264:A
1260:x
1247:a
1237:]
1228:,
1206:=
1168:]
1146:t
1140:_
1137:|
1131:d
1128:,
1125:z
1122:,
1119:c
1116:,
1110:(
1104:,
1101:y
1095:b
1092:,
1089:x
1086:,
1083:a
1080:,
1074:(
1068:,
1062:(
1050:d
1047:,
1044:z
1041:,
1038:c
1035:,
1029:(
1023:,
1020:y
1017:,
1014:b
1011:,
1005:(
999:,
996:x
993:,
990:a
987:,
981:(
975:|
969:d
966:,
963:z
957:c
954:,
951:y
948:,
945:b
942:,
936:(
930:,
924:(
918:,
915:x
912:,
909:a
906:,
900:(
894:|
891:)
888:d
885:,
882:z
876:c
873:,
870:y
867:,
864:b
861:,
855:(
849:,
846:x
843:,
840:a
837:,
831:(
825:,
819:(
813:|
810:)
807:d
804:,
801:z
795:c
792:,
789:y
783:b
780:,
777:x
774:,
771:a
768:,
762:(
756:,
750:(
744:,
738:(
732:|
726:t
720:=
717:t
705:a
699:*
696:a
690:*
684:a
678:*
666:|
660:=
654:a
642:|
636:=
601:=
598:)
592:_
586:(
570:=
567:)
564:_
555:(
503:=
451:_
436:n
429:)
426:1
423:-
420:n
417:(
414:f
411:*
408:n
405:=
402:n
399:f
388:1
385:=
382:0
379:f
303:)
299:(
145:)
139:(
134:)
130:(
120:·
113:·
106:·
99:·
72:.
49:.
42:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
