CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Pattern matching - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"9a94bf88-23da-4299-ae00-c4fc63fe6610","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Pattern_matching","wgTitle":"Pattern matching","wgCurRevisionId":1256970399,"wgRevisionId":1256970399,"wgArticleId":279688,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Articles needing additional references from February 2011","All articles needing additional references","All articles with unsourced statements","Articles with unsourced statements from January 2019","Articles to be expanded from May 2008","All articles to be expanded","Commons category link from Wikidata","Articles with example Haskell code","Pattern matching","Conditional constructs", "Functional programming"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Pattern_matching","wgRelevantArticleId":279688,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty": false,"wgWikibaseItemId":"Q1503724","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","site","mediawiki.page.ready", "jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Pattern matching - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Pattern_matching"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Pattern_matching&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Pattern_matching"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Pattern_matching rootpage-Pattern_matching skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Pattern+matching" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Pattern+matching" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Pattern+matching" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Pattern+matching" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-History" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#History"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>History</span> </div> </a> <ul id="toc-History-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Primitive_patterns" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Primitive_patterns"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Primitive patterns</span> </div> </a> <ul id="toc-Primitive_patterns-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Tree_patterns" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Tree_patterns"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Tree patterns</span> </div> </a> <ul id="toc-Tree_patterns-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Filtering_data_with_patterns" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Filtering_data_with_patterns"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Filtering data with patterns</span> </div> </a> <ul id="toc-Filtering_data_with_patterns-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Pattern_matching_in_Mathematica" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Pattern_matching_in_Mathematica"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Pattern matching in Mathematica</span> </div> </a> <button aria-controls="toc-Pattern_matching_in_Mathematica-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Pattern matching in Mathematica subsection</span> </button> <ul id="toc-Pattern_matching_in_Mathematica-sublist" class="vector-toc-list"> <li id="toc-Declarative_programming" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Declarative_programming"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Declarative programming</span> </div> </a> <ul id="toc-Declarative_programming-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Pattern_matching_and_strings" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Pattern_matching_and_strings"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Pattern matching and strings</span> </div> </a> <button aria-controls="toc-Pattern_matching_and_strings-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Pattern matching and strings subsection</span> </button> <ul id="toc-Pattern_matching_and_strings-sublist" class="vector-toc-list"> <li id="toc-Tree_patterns_for_strings" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Tree_patterns_for_strings"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.1</span> <span>Tree patterns for strings</span> </div> </a> <ul id="toc-Tree_patterns_for_strings-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Example_string_patterns" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Example_string_patterns"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.2</span> <span>Example string patterns</span> </div> </a> <ul id="toc-Example_string_patterns-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-SNOBOL" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#SNOBOL"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.3</span> <span>SNOBOL</span> </div> </a> <ul id="toc-SNOBOL-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Pattern matching</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 17 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-17" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">17 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-bn mw-list-item"><a href="https://bn.wikipedia.org/wiki/%E0%A6%AC%E0%A6%BF%E0%A6%A8%E0%A7%8D%E0%A6%AF%E0%A6%BE%E0%A6%B8_%E0%A6%AE%E0%A6%BF%E0%A6%B2%E0%A6%95%E0%A6%B0%E0%A6%A3" title="বিন্যাস মিলকরণ – Bangla" lang="bn" hreflang="bn" data-title="বিন্যাস মিলকরণ" data-language-autonym="বাংলা" data-language-local-name="Bangla" class="interlanguage-link-target"><span>বাংলা</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Comprovaci%C3%B3_de_patrons" title="Comprovació de patrons – Catalan" lang="ca" hreflang="ca" data-title="Comprovació de patrons" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/M%C3%B8nstergenkendelse" title="Mønstergenkendelse – Danish" lang="da" hreflang="da" data-title="Mønstergenkendelse" data-language-autonym="Dansk" data-language-local-name="Danish" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Pattern_Matching" title="Pattern Matching – German" lang="de" hreflang="de" data-title="Pattern Matching" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/B%C3%BAsqueda_de_patrones" title="Búsqueda de patrones – Spanish" lang="es" hreflang="es" data-title="Búsqueda de patrones" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AA%D8%B7%D8%A8%DB%8C%D9%82_%D8%A7%D9%84%DA%AF%D9%88" title="تطبیق الگو – Persian" lang="fa" hreflang="fa" data-title="تطبیق الگو" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Filtrage_par_motif" title="Filtrage par motif – French" lang="fr" hreflang="fr" data-title="Filtrage par motif" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%ED%8C%A8%ED%84%B4_%EB%A7%A4%EC%B9%AD" title="패턴 매칭 – Korean" lang="ko" hreflang="ko" data-title="패턴 매칭" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Patroonvergelijking" title="Patroonvergelijking – Dutch" lang="nl" hreflang="nl" data-title="Patroonvergelijking" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0" title="パターンマッチング – Japanese" lang="ja" hreflang="ja" data-title="パターンマッチング" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Dopasowanie_do_wzorca" title="Dopasowanie do wzorca – Polish" lang="pl" hreflang="pl" data-title="Dopasowanie do wzorca" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Casamento_de_padr%C3%B5es" title="Casamento de padrões – Portuguese" lang="pt" hreflang="pt" data-title="Casamento de padrões" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D0%BF%D0%BE%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D1%86%D0%BE%D0%BC" title="Сопоставление с образцом – Russian" lang="ru" hreflang="ru" data-title="Сопоставление с образцом" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Pattern_matching" title="Pattern matching – Simple English" lang="en-simple" hreflang="en-simple" data-title="Pattern matching" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Podudaranje_paterna" title="Podudaranje paterna – Serbian" lang="sr" hreflang="sr" data-title="Podudaranje paterna" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%97%D1%96%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D1%8F%D0%BD%D0%BD%D1%8F_%D1%96%D0%B7_%D0%B2%D0%B7%D1%96%D1%80%D1%86%D0%B5%D0%BC" title="Зіставляння із взірцем – Ukrainian" lang="uk" hreflang="uk" data-title="Зіставляння із взірцем" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D" title="模式匹配 – Chinese" lang="zh" hreflang="zh" data-title="模式匹配" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1503724#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Pattern_matching" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Pattern_matching" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Pattern_matching"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Pattern_matching&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Pattern_matching&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Pattern_matching"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Pattern_matching&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Pattern_matching&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Pattern_matching" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Pattern_matching" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Pattern_matching&oldid=1256970399" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Pattern_matching&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Pattern_matching&id=1256970399&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPattern_matching"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPattern_matching"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Pattern_matching&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Pattern_matching&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Pattern_matching" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1503724" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Act of checking a given sequence of tokens for the presence of the constituents of some pattern</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">This article is about pattern matching in <a href="/wiki/Functional_programming" title="Functional programming">functional programming</a>. For other uses, see <a href="/wiki/String_matching" class="mw-redirect" title="String matching">string matching</a> and <a href="/wiki/Pattern_recognition" title="Pattern recognition">pattern recognition</a>.</div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">For the use of variable matching criteria in defining abstract patterns to match, see <a href="/wiki/Regular_expression" title="Regular expression">regular expression</a>.</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-More_citations_needed plainlinks metadata ambox ambox-content ambox-Refimprove" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Pattern_matching" title="Special:EditPage/Pattern matching">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and removed.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22Pattern+matching%22">"Pattern matching"</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22Pattern+matching%22+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22Pattern+matching%22&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22Pattern+matching%22+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22Pattern+matching%22">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22Pattern+matching%22&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">February 2011</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, <b>pattern matching</b> is the act of checking a given sequence of <a href="/wiki/Lexical_analysis#Token" title="Lexical analysis">tokens</a> for the presence of the constituents of some <a href="/wiki/Pattern" title="Pattern">pattern</a>. In contrast to <a href="/wiki/Pattern_recognition" title="Pattern recognition">pattern recognition</a>, the match usually has to be exact: "either it will or will not be a match." The patterns generally have the form of either <a href="/wiki/String_(computer_science)" title="String (computer science)">sequences</a> or <a href="/wiki/Tree_structure" title="Tree structure">tree structures</a>. 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., <a href="/wiki/Regular_expression" title="Regular expression">search and replace</a>). </p><p>Sequence patterns (e.g., a text string) are often described using <a href="/wiki/Regular_expression" title="Regular expression">regular expressions</a> and matched using techniques such as <a href="/wiki/Backtracking" title="Backtracking">backtracking</a>. </p><p>Tree patterns are used in some <a href="/wiki/Programming_language" title="Programming language">programming languages</a> as a general tool to process data based on its structure, e.g. <a href="/wiki/C_Sharp_(programming_language)" title="C Sharp (programming language)">C#</a>,<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> <a href="/wiki/F_Sharp_(programming_language)" title="F Sharp (programming language)">F#</a>,<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Haskell" title="Haskell">Haskell</a>,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> <a href="/wiki/ML_(programming_language)" title="ML (programming language)">ML</a>, <a href="/wiki/Python_(programming_language)" title="Python (programming language)">Python</a>,<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Ruby_(programming_language)" title="Ruby (programming language)">Ruby</a>,<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Rust_(programming_language)" title="Rust (programming language)">Rust</a>,<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Scala_(programming_language)" title="Scala (programming language)">Scala</a>,<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Swift_(programming_language)" title="Swift (programming language)">Swift</a><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> and the symbolic mathematics language <a href="/wiki/Mathematica" class="mw-redirect" title="Mathematica">Mathematica</a> have special <a href="/wiki/Syntax_(programming_languages)" title="Syntax (programming languages)">syntax</a> for expressing tree patterns and a <a href="/wiki/Language_construct" title="Language construct">language construct</a> for <a href="/wiki/Conditional_(computer_programming)" title="Conditional (computer programming)">conditional execution</a> and value retrieval based on it. </p><p>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 <a href="/wiki/Guard_(computer_science)" title="Guard (computer science)">guards</a>.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (January 2019)">citation needed</span></a></i>]</sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="History">History</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=1" title="Edit section: History"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Regular_expression#History" title="Regular expression">Regular expression § History</a></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Expand_section plainlinks metadata ambox mbox-small-left ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><span typeof="mw:File"><a href="/wiki/File:Wiki_letter_w_cropped.svg" class="mw-file-description"><img alt="[icon]" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png" decoding="async" width="20" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/30px-Wiki_letter_w_cropped.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/40px-Wiki_letter_w_cropped.svg.png 2x" data-file-width="44" data-file-height="31" /></a></span></td><td class="mbox-text"><div class="mbox-text-span">This section <b>needs expansion</b>. You can help by <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Pattern_matching&action=edit&section=">adding to it</a>. <span class="date-container"><i>(<span class="date">May 2008</span>)</i></span></div></td></tr></tbody></table> <p>Early programming languages with pattern matching constructs include <a href="/wiki/COMIT" title="COMIT">COMIT</a> (1957), <a href="/wiki/SNOBOL" title="SNOBOL">SNOBOL</a> (1962), <a href="/wiki/Refal" title="Refal">Refal</a> (1968) with tree-based pattern matching, <a href="/wiki/Prolog" title="Prolog">Prolog</a> (1972), St Andrews Static Language (<a href="/wiki/SASL_(programming_language)" title="SASL (programming language)">SASL</a>) (1976), <a href="/wiki/NPL_(programming_language)" title="NPL (programming language)">NPL</a> (1977), and <a href="/wiki/Kent_Recursive_Calculator" title="Kent Recursive Calculator">Kent Recursive Calculator</a> (KRC) (1981). </p><p>The pattern matching feature of function arguments in the <a href="/wiki/ML_(programming_language)" title="ML (programming language)">ML programming language</a> (1973) and its dialect <a href="/wiki/Standard_ML" title="Standard ML">Standard ML</a> (1983) has been carried over to some other <a href="/wiki/Functional_programming" title="Functional programming">functional programming languages</a> that were influenced by them, such as <a href="/wiki/Haskell" title="Haskell">Haskell</a> (1990), <a href="/wiki/Scala_(programming_language)" title="Scala (programming language)">Scala</a> (2004) and <a href="/wiki/F_Sharp_(programming_language)" title="F Sharp (programming language)">F#</a> (2005). The pattern matching construct with the <code>match</code> keyword that was introduced in the <a href="/wiki/ML_(programming_language)" title="ML (programming language)">ML</a> dialect <a href="/wiki/Caml" title="Caml">Caml</a> (1985) was followed by programming languages such as <a href="/wiki/OCaml" title="OCaml">OCaml</a> (1996), <a href="/wiki/F_Sharp_(programming_language)" title="F Sharp (programming language)">F#</a> (2005), <a href="/wiki/F*_(programming_language)" title="F* (programming language)">F*</a> (2011) and <a href="/wiki/Rust_(programming_language)" title="Rust (programming language)">Rust</a> (2015). </p><p>Many <a href="/wiki/Text_editor" title="Text editor">text editors</a> support pattern matching of various kinds: the <a href="/wiki/QED_(text_editor)" title="QED (text editor)">QED editor</a> supports <a href="/wiki/Regular_expression" title="Regular expression">regular expression</a> search, and some versions of <a href="/wiki/TECO_(text_editor)" title="TECO (text editor)">TECO</a> support the OR operator in searches. </p><p><a href="/wiki/Computer_algebra_system" title="Computer algebra system">Computer algebra systems</a> generally support pattern matching on algebraic expressions.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Primitive_patterns">Primitive patterns</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=2" title="Edit section: Primitive patterns"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>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): </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="nf">f</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="mi">1</span> </pre></div> <p>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 to take more generic arguments: </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="nf">f</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> </pre></div> <p>Here, the first <code>n</code> 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 <a href="/wiki/Hope_(programming_language)" title="Hope (programming language)">Hope</a>), 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 <code>n * f (n-1)</code> with n being the argument. </p><p>The wildcard pattern (often written as <code>_</code>) is also simple: like a variable name, it matches any value, but does not bind the value to any name. Algorithms for <a href="/wiki/Matching_wildcards" title="Matching wildcards">matching wildcards</a> in simple string-matching situations have been developed in a number of <a href="/wiki/Recursion" title="Recursion">recursive</a> and non-recursive varieties.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Tree_patterns">Tree patterns</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=3" title="Edit section: Tree patterns"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>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 the combination of the concrete elements and the elements that are allowed to vary within the structure of the pattern. </p><p>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 <a href="/wiki/Abstract_syntax_tree" title="Abstract syntax tree">abstract syntax tree</a> of a programming language and <a href="/wiki/Algebraic_data_type" title="Algebraic data type">algebraic data types</a>. </p><p>In Haskell, the following line defines an algebraic data type <code>Color</code> that has a single data constructor <code>ColorConstructor</code> that wraps an integer and a string. </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="kr">data</span><span class="w"> </span><span class="kt">Color</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="kt">ColorConstructor</span><span class="w"> </span><span class="kt">Integer</span><span class="w"> </span><span class="kt">String</span> </pre></div> <p>The constructor is a node in a tree and the integer and string are leaves in branches. </p><p>When we want to write <a href="/wiki/Function_(programming)" class="mw-redirect" title="Function (programming)">functions</a> to make <code>Color</code> an <a href="/wiki/Abstract_data_type" title="Abstract data type">abstract data type</a>, we wish to write functions to <a href="/wiki/Interface_(computer_science)" class="mw-redirect" title="Interface (computer science)">interface</a> 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 <code>Color</code>. </p><p>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 <code>Color</code>, we can use a simple tree pattern and write: </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="nf">integerPart</span><span class="w"> </span><span class="p">(</span><span class="kt">ColorConstructor</span><span class="w"> </span><span class="n">theInteger</span><span class="w"> </span><span class="kr">_</span><span class="p">)</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">theInteger</span> </pre></div> <p>As well: </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="nf">stringPart</span><span class="w"> </span><span class="p">(</span><span class="kt">ColorConstructor</span><span class="w"> </span><span class="kr">_</span><span class="w"> </span><span class="n">theString</span><span class="p">)</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">theString</span> </pre></div> <p>The creations of these functions can be automated by Haskell's data <a href="/wiki/Record_(computer_science)" title="Record (computer science)">record</a> syntax. </p><p>This <a href="/wiki/OCaml" title="OCaml">OCaml</a> example which defines a <a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">red–black tree</a> 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. </p> <div class="mw-highlight mw-highlight-lang-ocaml mw-content-ltr" dir="ltr"><pre><span></span><span class="k">type</span> <span class="n">color</span> <span class="o">=</span> <span class="nc">Red</span> <span class="o">|</span> <span class="nc">Black</span> <span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">tree</span> <span class="o">=</span> <span class="nc">Empty</span> <span class="o">|</span> <span class="nc">Tree</span> <span class="k">of</span> <span class="n">color</span> <span class="o">*</span> <span class="k">'</span><span class="n">a</span> <span class="n">tree</span> <span class="o">*</span> <span class="k">'</span><span class="n">a</span> <span class="o">*</span> <span class="k">'</span><span class="n">a</span> <span class="n">tree</span> <span class="k">let</span> <span class="n">rebalance</span> <span class="n">t</span> <span class="o">=</span> <span class="k">match</span> <span class="n">t</span> <span class="k">with</span> <span class="o">|</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Black</span><span class="o">,</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Red</span><span class="o">,</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Red</span><span class="o">,</span> <span class="n">a</span><span class="o">,</span> <span class="n">x</span><span class="o">,</span> <span class="n">b</span><span class="o">),</span> <span class="n">y</span><span class="o">,</span> <span class="n">c</span><span class="o">),</span> <span class="n">z</span><span class="o">,</span> <span class="n">d</span><span class="o">)</span> <span class="o">|</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Black</span><span class="o">,</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Red</span><span class="o">,</span> <span class="n">a</span><span class="o">,</span> <span class="n">x</span><span class="o">,</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Red</span><span class="o">,</span> <span class="n">b</span><span class="o">,</span> <span class="n">y</span><span class="o">,</span> <span class="n">c</span><span class="o">)),</span> <span class="n">z</span><span class="o">,</span> <span class="n">d</span><span class="o">)</span> <span class="o">|</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Black</span><span class="o">,</span> <span class="n">a</span><span class="o">,</span> <span class="n">x</span><span class="o">,</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Red</span><span class="o">,</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Red</span><span class="o">,</span> <span class="n">b</span><span class="o">,</span> <span class="n">y</span><span class="o">,</span> <span class="n">c</span><span class="o">),</span> <span class="n">z</span><span class="o">,</span> <span class="n">d</span><span class="o">))</span> <span class="o">|</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Black</span><span class="o">,</span> <span class="n">a</span><span class="o">,</span> <span class="n">x</span><span class="o">,</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Red</span><span class="o">,</span> <span class="n">b</span><span class="o">,</span> <span class="n">y</span><span class="o">,</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Red</span><span class="o">,</span> <span class="n">c</span><span class="o">,</span> <span class="n">z</span><span class="o">,</span> <span class="n">d</span><span class="o">)))</span> <span class="o">-></span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Red</span><span class="o">,</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Black</span><span class="o">,</span> <span class="n">a</span><span class="o">,</span> <span class="n">x</span><span class="o">,</span> <span class="n">b</span><span class="o">),</span> <span class="n">y</span><span class="o">,</span> <span class="nc">Tree</span> <span class="o">(</span><span class="nc">Black</span><span class="o">,</span> <span class="n">c</span><span class="o">,</span> <span class="n">z</span><span class="o">,</span> <span class="n">d</span><span class="o">))</span> <span class="o">|</span> <span class="o">_</span> <span class="o">-></span> <span class="n">t</span> <span class="c">(* the 'catch-all' case if no previous pattern matches *)</span> </pre></div> <div class="mw-heading mw-heading2"><h2 id="Filtering_data_with_patterns">Filtering data with patterns</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=4" title="Edit section: Filtering data with patterns"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Pattern matching can be used to filter data of a certain structure. For instance, in Haskell a <a href="/wiki/List_comprehension" title="List comprehension">list comprehension</a> could be used for this kind of filtering: </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="p">[</span><span class="kt">A</span><span class="w"> </span><span class="n">x</span><span class="o">|</span><span class="kt">A</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="ow"><-</span><span class="w"> </span><span class="p">[</span><span class="kt">A</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="kt">B</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="kt">A</span><span class="w"> </span><span class="mi">2</span><span class="p">,</span><span class="w"> </span><span class="kt">B</span><span class="w"> </span><span class="mi">2</span><span class="p">]]</span> </pre></div> <p>evaluates to </p> <pre>[A 1, A 2] </pre> <div class="mw-heading mw-heading2"><h2 id="Pattern_matching_in_Mathematica">Pattern matching in Mathematica</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=5" title="Edit section: Pattern matching in Mathematica"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In <a href="/wiki/Mathematica" class="mw-redirect" title="Mathematica">Mathematica</a>, the only structure that exists is the <a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">tree</a>, which is populated by symbols. In the <a href="/wiki/Haskell" title="Haskell">Haskell</a> syntax used thus far, this could be defined as </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="kr">data</span><span class="w"> </span><span class="kt">SymbolTree</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="kt">Symbol</span><span class="w"> </span><span class="kt">String</span><span class="w"> </span><span class="p">[</span><span class="kt">SymbolTree</span><span class="p">]</span> </pre></div> <p>An example tree could then look like </p> <div class="mw-highlight mw-highlight-lang-mathematica mw-content-ltr" dir="ltr"><pre><span></span><span class="n">Symbol</span><span class="w"> </span><span class="s">"a"</span><span class="w"> </span><span class="p">[</span><span class="n">Symbol</span><span class="w"> </span><span class="s">"b"</span><span class="w"> </span><span class="p">[],</span><span class="w"> </span><span class="n">Symbol</span><span class="w"> </span><span class="s">"c"</span><span class="w"> </span><span class="p">[]]</span> </pre></div> <p>In the traditional, more suitable syntax, the symbols are written as they are and the levels of the tree are represented using <code>[]</code>, so that for instance <code>a[b,c]</code> is a tree with a as the parent, and b and c as the children. </p><p>A pattern in Mathematica involves putting "_" at positions in that tree. For instance, the pattern </p> <pre>A[_] </pre> <p>will match elements such as A[1], A[2], or more generally A[<i>x</i>] where <i>x</i> is any entity. In this case, <code>A</code> is the concrete element, while <code>_</code> denotes the piece of tree that can be varied. A symbol prepended to <code>_</code> binds the match to that variable name while a symbol appended to <code>_</code> restricts the matches to nodes of that symbol. Note that even blanks themselves are internally represented as <code>Blank[]</code> for <code>_</code> and <code>Blank[x]</code> for <code>_x</code>. </p><p>The Mathematica function <code>Cases</code> filters elements of the first argument that match the pattern in the second argument:<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-highlight mw-highlight-lang-mathematica mw-content-ltr" dir="ltr"><pre><span></span><span class="n">Cases</span><span class="p">[{</span><span class="n">a</span><span class="p">[</span><span class="mi">1</span><span class="p">],</span><span class="w"> </span><span class="n">b</span><span class="p">[</span><span class="mi">1</span><span class="p">],</span><span class="w"> </span><span class="n">a</span><span class="p">[</span><span class="mi">2</span><span class="p">],</span><span class="w"> </span><span class="n">b</span><span class="p">[</span><span class="mi">2</span><span class="p">]},</span><span class="w"> </span><span class="n">a</span><span class="p">[</span><span class="nv">_</span><span class="p">]</span><span class="w"> </span><span class="p">]</span> </pre></div> <p>evaluates to </p> <div class="mw-highlight mw-highlight-lang-mathematica mw-content-ltr" dir="ltr"><pre><span></span><span class="p">{</span><span class="n">a</span><span class="p">[</span><span class="mi">1</span><span class="p">],</span><span class="w"> </span><span class="n">a</span><span class="p">[</span><span class="mi">2</span><span class="p">]}</span> </pre></div> <p>Pattern matching applies to the <i>structure</i> of expressions. In the example below, </p> <div class="mw-highlight mw-highlight-lang-mathematica mw-content-ltr" dir="ltr"><pre><span></span><span class="n">Cases</span><span class="p">[</span><span class="w"> </span><span class="p">{</span><span class="n">a</span><span class="p">[</span><span class="n">b</span><span class="p">],</span><span class="w"> </span><span class="n">a</span><span class="p">[</span><span class="n">b</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">],</span><span class="w"> </span><span class="n">a</span><span class="p">[</span><span class="n">b</span><span class="p">[</span><span class="n">c</span><span class="p">],</span><span class="w"> </span><span class="n">d</span><span class="p">],</span><span class="w"> </span><span class="n">a</span><span class="p">[</span><span class="n">b</span><span class="p">[</span><span class="n">c</span><span class="p">],</span><span class="w"> </span><span class="n">d</span><span class="p">[</span><span class="n">e</span><span class="p">]],</span><span class="w"> </span><span class="n">a</span><span class="p">[</span><span class="n">b</span><span class="p">[</span><span class="n">c</span><span class="p">],</span><span class="w"> </span><span class="n">d</span><span class="p">,</span><span class="w"> </span><span class="n">e</span><span class="p">]},</span><span class="w"> </span><span class="n">a</span><span class="p">[</span><span class="n">b</span><span class="p">[</span><span class="nv">_</span><span class="p">],</span><span class="w"> </span><span class="nv">_</span><span class="p">]</span><span class="w"> </span><span class="p">]</span> </pre></div> <p>returns </p> <div class="mw-highlight mw-highlight-lang-mathematica mw-content-ltr" dir="ltr"><pre><span></span><span class="p">{</span><span class="n">a</span><span class="p">[</span><span class="n">b</span><span class="p">[</span><span class="n">c</span><span class="p">],</span><span class="n">d</span><span class="p">],</span><span class="w"> </span><span class="n">a</span><span class="p">[</span><span class="n">b</span><span class="p">[</span><span class="n">c</span><span class="p">],</span><span class="n">d</span><span class="p">[</span><span class="n">e</span><span class="p">]]}</span> </pre></div> <p>because only these elements will match the pattern <code>a[b[_],_]</code> above. </p><p>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 <code>Trace</code> can be used to monitor a computation, and return the elements that arise which match a pattern. For example, we can define the <a href="/wiki/Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci sequence</a> as </p> <div class="mw-highlight mw-highlight-lang-mathematica mw-content-ltr" dir="ltr"><pre><span></span><span class="n">fib</span><span class="p">[</span><span class="mi">0</span><span class="o">|</span><span class="mi">1</span><span class="p">]</span><span class="o">:=</span><span class="mi">1</span> <span class="n">fib</span><span class="p">[</span><span class="nv">n_</span><span class="p">]</span><span class="o">:=</span><span class="w"> </span><span class="n">fib</span><span class="p">[</span><span class="n">n</span><span class="mi">-1</span><span class="p">]</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">fib</span><span class="p">[</span><span class="n">n</span><span class="mi">-2</span><span class="p">]</span> </pre></div> <p>Then, we can ask the question: Given fib[3], what is the sequence of recursive Fibonacci calls? </p> <div class="mw-highlight mw-highlight-lang-mathematica mw-content-ltr" dir="ltr"><pre><span></span><span class="n">Trace</span><span class="p">[</span><span class="n">fib</span><span class="p">[</span><span class="mi">3</span><span class="p">],</span><span class="w"> </span><span class="n">fib</span><span class="p">[</span><span class="nv">_</span><span class="p">]]</span> </pre></div> <p>returns a structure that represents the occurrences of the pattern <code>fib[_]</code> in the computational structure: </p> <div class="mw-highlight mw-highlight-lang-mathematica mw-content-ltr" dir="ltr"><pre><span></span><span class="p">{</span><span class="n">fib</span><span class="p">[</span><span class="mi">3</span><span class="p">],{</span><span class="n">fib</span><span class="p">[</span><span class="mi">2</span><span class="p">],{</span><span class="n">fib</span><span class="p">[</span><span class="mi">1</span><span class="p">]},{</span><span class="n">fib</span><span class="p">[</span><span class="mi">0</span><span class="p">]}},{</span><span class="n">fib</span><span class="p">[</span><span class="mi">1</span><span class="p">]}}</span> </pre></div> <div class="mw-heading mw-heading3"><h3 id="Declarative_programming">Declarative programming</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=6" title="Edit section: Declarative programming"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>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. </p><p>For instance, the <a href="/wiki/Mathematica" class="mw-redirect" title="Mathematica">Mathematica</a> function <code>Compile</code> 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 <code>{{com[_], Integer}}</code> instructs <code>Compile</code> that expressions of the form <code>com[_]</code> can be assumed to be <a href="/wiki/Integer" title="Integer">integers</a> for the purposes of compilation: </p> <div class="mw-highlight mw-highlight-lang-mathematica mw-content-ltr" dir="ltr"><pre><span></span><span class="n">com</span><span class="p">[</span><span class="nv">i_</span><span class="p">]</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="n">Binomial</span><span class="p">[</span><span class="mi">2</span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">i</span><span class="p">]</span> <span class="n">Compile</span><span class="p">[{</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="p">{</span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="nv">_Integer</span><span class="p">}},</span><span class="w"> </span><span class="n">x</span><span class="o">^</span><span class="n">com</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="w"> </span><span class="p">{{</span><span class="n">com</span><span class="p">[</span><span class="nv">_</span><span class="p">],</span><span class="w"> </span><span class="n">Integer</span><span class="p">}}]</span> </pre></div> <p>Mailboxes in <a href="/wiki/Erlang_(programming_language)" title="Erlang (programming language)">Erlang</a> also work this way. </p><p>The <a href="/wiki/Curry%E2%80%93Howard_correspondence" title="Curry–Howard correspondence">Curry–Howard correspondence</a> between proofs and programs relates <a href="/wiki/ML_(programming_language)" title="ML (programming language)">ML</a>-style pattern matching to <a href="/wiki/Proof_by_cases" class="mw-redirect" title="Proof by cases">case analysis</a> and <a href="/wiki/Proof_by_exhaustion" title="Proof by exhaustion">proof by exhaustion</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Pattern_matching_and_strings">Pattern matching and strings</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=7" title="Edit section: Pattern matching and strings"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>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. </p><p>However, it is possible to perform some string pattern matching within the same framework that has been discussed throughout this article. </p> <div class="mw-heading mw-heading3"><h3 id="Tree_patterns_for_strings">Tree patterns for strings</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=8" title="Edit section: Tree patterns for strings"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>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. </p><p>In Haskell and <a href="/wiki/Functional_programming" title="Functional programming">functional programming</a> languages in general, strings are represented as functional <a href="/wiki/List_(computing)" class="mw-redirect" title="List (computing)">lists</a> of characters. A functional list is defined as an empty list, or an element constructed on an existing list. In Haskell syntax: </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="kt">[]</span><span class="w"> </span><span class="c1">-- an empty list</span> <span class="nf">x</span><span class="kt">:</span><span class="n">xs</span><span class="w"> </span><span class="c1">-- an element x constructed on a list xs</span> </pre></div> <p>The structure for a list with some elements is thus <code>element:list</code>. When pattern matching, we assert that a certain piece of data is equal to a certain pattern. For example, in the function: </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="nf">head</span><span class="w"> </span><span class="p">(</span><span class="n">element</span><span class="kt">:</span><span class="n">list</span><span class="p">)</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">element</span> </pre></div> <p>We assert that the first element of <code>head</code>'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). </p><p>In the example, we have no use for <code>list</code>, so we can disregard it, and thus write the function: </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="nf">head</span><span class="w"> </span><span class="p">(</span><span class="n">element</span><span class="kt">:</span><span class="kr">_</span><span class="p">)</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">element</span> </pre></div> <p>The equivalent Mathematica transformation is expressed as </p> <pre>head[element, ]:=element </pre> <div class="mw-heading mw-heading3"><h3 id="Example_string_patterns">Example string patterns</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=9" title="Edit section: Example string patterns"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In Mathematica, for instance, </p> <pre>StringExpression["a",_] </pre> <p>will match a string that has two characters and begins with "a". </p><p>The same pattern in Haskell: </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="p">[</span><span class="sc">'a'</span><span class="p">,</span><span class="w"> </span><span class="kr">_</span><span class="p">]</span> </pre></div> <p>Symbolic entities can be introduced to represent many different classes of relevant features of a string. For instance, </p> <pre>StringExpression[LetterCharacter, DigitCharacter] </pre> <p>will match a string that consists of a letter first, and then a number. </p><p>In Haskell, <a href="/wiki/Guard_(computer_science)" title="Guard (computer science)">guards</a> could be used to achieve the same matches: </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="p">[</span><span class="n">letter</span><span class="p">,</span><span class="w"> </span><span class="n">digit</span><span class="p">]</span><span class="w"> </span><span class="o">|</span><span class="w"> </span><span class="n">isAlpha</span><span class="w"> </span><span class="n">letter</span><span class="w"> </span><span class="o">&&</span><span class="w"> </span><span class="n">isDigit</span><span class="w"> </span><span class="n">digit</span> </pre></div> <p>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 the programs that contain them. </p> <div class="mw-heading mw-heading3"><h3 id="SNOBOL">SNOBOL</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=10" title="Edit section: SNOBOL"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/SNOBOL" title="SNOBOL">SNOBOL</a></div> <p>SNOBOL (<i>StriNg Oriented and symBOlic Language</i>) is a computer programming language developed between 1962 and 1967 at <a href="/wiki/AT%26T_Corporation" title="AT&T Corporation">AT&T</a> <a href="/wiki/Bell_Laboratories" class="mw-redirect" title="Bell Laboratories">Bell Laboratories</a> by <a href="/wiki/David_J._Farber" title="David J. Farber">David J. Farber</a>, <a href="/wiki/Ralph_E._Griswold" class="mw-redirect" title="Ralph E. Griswold">Ralph E. Griswold</a> and Ivan P. Polonsky. </p><p>SNOBOL4 stands apart from most programming languages by having patterns as a <a href="/wiki/First-class_object" class="mw-redirect" title="First-class object">first-class data type</a> (<i>i.e.</i> 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 <a href="/wiki/Concatenation" title="Concatenation">concatenation</a> and <a href="/wiki/Alternation_(formal_language_theory)" title="Alternation (formal language theory)">alternation</a>. Strings generated during execution can be treated as programs and executed. </p><p>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 <a href="/wiki/Humanities" title="Humanities">humanities</a>. </p><p>Since SNOBOL's creation, newer languages such as <a href="/wiki/Awk" class="mw-redirect" title="Awk">Awk</a> and <a href="/wiki/Perl" title="Perl">Perl</a> have made string manipulation by means of <a href="/wiki/Regular_expression" title="Regular expression">regular expressions</a> fashionable. SNOBOL4 patterns, however, subsume <a href="/wiki/Backus%E2%80%93Naur_form" title="Backus–Naur form">BNF</a> grammars, which are equivalent to <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammars</a> and more powerful than <a href="/wiki/Regular_expression" title="Regular expression">regular expressions</a>.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=11" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Artificial_Intelligence_Markup_Language" title="Artificial Intelligence Markup Language">Artificial Intelligence Markup Language</a> (AIML) for an AI language based on matching patterns in speech</li> <li><a href="/wiki/AWK" title="AWK">AWK</a> language</li> <li><a href="/wiki/Coccinelle_(software)" title="Coccinelle (software)">Coccinelle</a> pattern matches C source code</li> <li><a href="/wiki/Matching_wildcards" title="Matching wildcards">Matching wildcards</a></li> <li><a href="/wiki/Glob_(programming)" title="Glob (programming)">glob (programming)</a></li> <li><a href="/wiki/Pattern_calculus" title="Pattern calculus">Pattern calculus</a></li> <li><a href="/wiki/Pattern_recognition" title="Pattern recognition">Pattern recognition</a> for fuzzy patterns</li> <li><a href="/wiki/PCRE" class="mw-redirect" title="PCRE">PCRE</a> Perl Compatible Regular Expressions, a common modern implementation of string pattern matching ported to many languages</li> <li><a href="/wiki/REBOL#parse" class="mw-redirect" title="REBOL">REBOL parse dialect</a> for pattern matching used to implement language dialects</li> <li><a href="/wiki/Symbolic_integration" title="Symbolic integration">Symbolic integration</a></li> <li><a href="/wiki/Tagged_union" title="Tagged union">Tagged union</a></li> <li><a href="/wiki/Tom_(pattern_matching_language)" class="mw-redirect" title="Tom (pattern matching language)">Tom (pattern matching language)</a></li> <li><a href="/wiki/SNOBOL" title="SNOBOL">SNOBOL</a> for a programming language based on one kind of pattern matching</li> <li><a href="/wiki/Pattern_language" title="Pattern language">Pattern language</a> — metaphoric, drawn from architecture</li> <li><a href="/wiki/Graph_matching" title="Graph matching">Graph matching</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=12" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239549316">.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}</style><div class="refbegin" style=""> <ul><li>The Mathematica Book, chapter <a rel="nofollow" class="external text" href="https://web.archive.org/web/20050408135452/http://documents.wolfram.com/mathematica/book/section-2.3">Section 2.3: Patterns</a></li> <li>The Haskell 98 Report, chapter <a rel="nofollow" class="external text" href="http://haskell.org/onlinereport/exps.html#pattern-matching">3.17 Pattern Matching</a>.</li> <li>Python Reference Manual, chapter <a rel="nofollow" class="external text" href="https://docs.python.org/2/reference/simple_stmts.html#assignment-statements">6.3 Assignment statements</a>.</li> <li>The <a href="/wiki/Pure_(programming_language)" class="mw-redirect" title="Pure (programming language)">Pure</a> Programming Language, chapter <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110711112227/http://pure-lang.googlecode.com/svn/docs/pure-intro/pure-intro.pdf">4.3: Patterns</a></li></ul> </div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.microsoft.com/en-us/dotnet/csharp/pattern-matching">"Pattern Matching - C# Guide"</a>. 13 March 2024.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Pattern+Matching+-+C%23+Guide&rft.date=2024-03-13&rft_id=https%3A%2F%2Fdocs.microsoft.com%2Fen-us%2Fdotnet%2Fcsharp%2Fpattern-matching&rfr_id=info%3Asid%2Fen.wikipedia.org%3APattern+matching" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/pattern-matching">"Pattern Matching - F# Guide"</a>. 5 November 2021.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Pattern+Matching+-+F%23+Guide&rft.date=2021-11-05&rft_id=https%3A%2F%2Fdocs.microsoft.com%2Fen-us%2Fdotnet%2Ffsharp%2Flanguage-reference%2Fpattern-matching&rfr_id=info%3Asid%2Fen.wikipedia.org%3APattern+matching" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.haskell.org/tutorial/patterns.html">A Gentle Introduction to Haskell: Patterns</a></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.python.org/3.10/whatsnew/3.10.html#pep-634-structural-pattern-matching">"What's New In Python 3.10 — Python 3.10.0b3 documentation"</a>. <i>docs.python.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-07-06</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=docs.python.org&rft.atitle=What%27s+New+In+Python+3.10+%E2%80%94+Python+3.10.0b3+documentation&rft_id=https%3A%2F%2Fdocs.python.org%2F3.10%2Fwhatsnew%2F3.10.html%23pep-634-structural-pattern-matching&rfr_id=info%3Asid%2Fen.wikipedia.org%3APattern+matching" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.ruby-lang.org/en/3.0.0/doc/syntax/pattern_matching_rdoc.html">"pattern_matching - Documentation for Ruby 3.0.0"</a>. <i>docs.ruby-lang.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-07-06</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=docs.ruby-lang.org&rft.atitle=pattern_matching+-+Documentation+for+Ruby+3.0.0&rft_id=https%3A%2F%2Fdocs.ruby-lang.org%2Fen%2F3.0.0%2Fdoc%2Fsyntax%2Fpattern_matching_rdoc.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3APattern+matching" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://doc.rust-lang.org/book/ch18-03-pattern-syntax.html">"Pattern Syntax - The Rust Programming Language"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Pattern+Syntax+-+The+Rust+Programming+Language&rft_id=https%3A%2F%2Fdoc.rust-lang.org%2Fbook%2Fch18-03-pattern-syntax.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3APattern+matching" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.scala-lang.org/tour/pattern-matching.html">"Pattern Matching"</a>. <i>Scala Documentation</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-01-17</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Scala+Documentation&rft.atitle=Pattern+Matching&rft_id=https%3A%2F%2Fdocs.scala-lang.org%2Ftour%2Fpattern-matching.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3APattern+matching" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.swift.org/swift-book/ReferenceManual/Patterns.html">"Patterns — The Swift Programming Language (Swift 5.1)"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Patterns+%E2%80%94+The+Swift+Programming+Language+%28Swift+5.1%29&rft_id=https%3A%2F%2Fdocs.swift.org%2Fswift-book%2FReferenceManual%2FPatterns.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3APattern+matching" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">Joel Moses, "Symbolic Integration", MIT Project MAC MAC-TR-47, December 1967</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCantatore2003" class="citation web cs1">Cantatore, Alessandro (2003). <a rel="nofollow" class="external text" href="http://xoomer.virgilio.it/acantato/dev/wildcard/wildmatch.html">"Wildcard matching algorithms"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Wildcard+matching+algorithms&rft.date=2003&rft.aulast=Cantatore&rft.aufirst=Alessandro&rft_id=http%3A%2F%2Fxoomer.virgilio.it%2Facantato%2Fdev%2Fwildcard%2Fwildmatch.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3APattern+matching" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://reference.wolfram.com/language/ref/Cases.html.en">"Cases—Wolfram Language Documentation"</a>. <i>reference.wolfram.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2020-11-17</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=reference.wolfram.com&rft.atitle=Cases%E2%80%94Wolfram+Language+Documentation&rft_id=https%3A%2F%2Freference.wolfram.com%2Flanguage%2Fref%2FCases.html.en&rfr_id=info%3Asid%2Fen.wikipedia.org%3APattern+matching" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text">Gimpel, J. F. 1973. A theory of discrete patterns and their implementation in SNOBOL4. Commun. ACM 16, 2 (Feb. 1973), 91–100. DOI=<a rel="nofollow" class="external free" href="http://doi.acm.org/10.1145/361952.361960">http://doi.acm.org/10.1145/361952.361960</a>.</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Pattern_matching&action=edit&section=13" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1235681985">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><style data-mw-deduplicate="TemplateStyles:r1237033735">@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}</style><div class="side-box side-box-right plainlinks sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/d/df/Wikibooks-logo-en-noslogan.svg/40px-Wikibooks-logo-en-noslogan.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/df/Wikibooks-logo-en-noslogan.svg/60px-Wikibooks-logo-en-noslogan.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/df/Wikibooks-logo-en-noslogan.svg/80px-Wikibooks-logo-en-noslogan.svg.png 2x" data-file-width="400" data-file-height="400" /></span></span></div> <div class="side-box-text plainlist">The Wikibook <i><a href="https://en.wikibooks.org/wiki/Haskell" class="extiw" title="wikibooks:Haskell">Haskell</a></i> has a page on the topic of: <i><b><a href="https://en.wikibooks.org/wiki/Haskell/Pattern_matching" class="extiw" title="wikibooks:Haskell/Pattern matching">Pattern matching</a></b></i></div></div> </div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1235681985"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1237033735"><div class="side-box side-box-right plainlinks sistersitebox"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1126788409"> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png" decoding="async" width="30" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/45px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/59px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></span></span></div> <div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Pattern_matching" class="extiw" title="commons:Category:Pattern matching">Pattern matching</a></span>.</div></div> </div> <ul><li><a rel="nofollow" class="external text" href="https://archive.today/19990225161739/http://www.haskell.org/development/views.html">Views: An Extension to Haskell Pattern Matching</a></li> <li>Nikolaas N. Oosterhof, Philip K. F. Hölzenspies, and Jan Kuper. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20060304053330/http://wwwhome.cs.utwente.nl/~tina/apm/applPatts.pdf">Application patterns</a>. A presentation at Trends in Functional Programming, 2005</li> <li><a rel="nofollow" class="external text" href="http://www.cs.cornell.edu/Projects/jmatch">JMatch</a>: the <a href="/wiki/Java_(programming_language)" title="Java (programming language)">Java</a> language extended with pattern matching</li> <li><a rel="nofollow" class="external text" href="https://archive.today/20130630081135/http://www.showtrend.com/">ShowTrend</a>: Online pattern matching for stock prices</li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20060211020429/http://cm.bell-labs.com/cm/cs/who/dmr/qed.html">An incomplete history of the QED Text Editor</a> by <a href="/wiki/Dennis_Ritchie" title="Dennis Ritchie">Dennis Ritchie</a> - provides the history of regular expressions in computer programs</li> <li><a rel="nofollow" class="external text" href="http://research.microsoft.com/~simonpj/papers/slpj-book-1987/index.htm">The Implementation of Functional Programming Languages, pages 53–103</a> Simon Peyton Jones, published by Prentice Hall, 1987.</li> <li><a rel="nofollow" class="external text" href="https://github.com/rsdn/nemerle/wiki/Grok-Variants-and-matching#matching">Nemerle, pattern matching</a>.</li> <li><a rel="nofollow" class="external text" href="http://erlang.org/doc/reference_manual/expressions.html#pattern">Erlang, pattern matching</a>.</li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20090822225301/http://www.cs.nyu.edu/leunga/prop.html">Prop: a C++ based pattern matching language, 1999</a></li> <li><a rel="nofollow" class="external text" href="https://github.com/Henry/PatMat">PatMat: a C++ pattern matching library based on</a> <a href="/wiki/SNOBOL" title="SNOBOL">SNOBOL</a>/<a href="/wiki/SPITBOL" title="SPITBOL">SPITBOL</a></li> <li>Temur Kutsia. <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1016/j.jsc.2008.05.001">Flat Matching</a>. Journal of Symbolic Computation 43(12): 858–873. Describes in details flat matching in Mathematica.</li> <li><a rel="nofollow" class="external text" href="http://www.datamystic.com/easypatterns_reference.html">EasyPattern language</a> pattern matching language for non-programmers</li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Strings" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Strings" title="Template:Strings"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Strings" title="Template talk:Strings"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Strings" title="Special:EditPage/Template:Strings"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Strings" style="font-size:114%;margin:0 4em"><a href="/wiki/String_(computer_science)" title="String (computer science)">Strings</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/String_metric" title="String metric">String metric</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Approximate_string_matching" title="Approximate string matching">Approximate string matching</a></li> <li><a href="/wiki/Bitap_algorithm" title="Bitap algorithm">Bitap algorithm</a></li> <li><a href="/wiki/Damerau%E2%80%93Levenshtein_distance" title="Damerau–Levenshtein distance">Damerau–Levenshtein distance</a></li> <li><a href="/wiki/Edit_distance" title="Edit distance">Edit distance</a></li> <li><a href="/wiki/Gestalt_pattern_matching" title="Gestalt pattern matching">Gestalt pattern matching</a></li> <li><a href="/wiki/Hamming_distance" title="Hamming distance">Hamming distance</a></li> <li><a href="/wiki/Jaro%E2%80%93Winkler_distance" title="Jaro–Winkler distance">Jaro–Winkler distance</a></li> <li><a href="/wiki/Lee_distance" title="Lee distance">Lee distance</a></li> <li><a href="/wiki/Levenshtein_automaton" title="Levenshtein automaton">Levenshtein automaton</a></li> <li><a href="/wiki/Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a></li> <li><a href="/wiki/Wagner%E2%80%93Fischer_algorithm" title="Wagner–Fischer algorithm">Wagner–Fischer algorithm </a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/String-searching_algorithm" title="String-searching algorithm">String-searching algorithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Apostolico%E2%80%93Giancarlo_algorithm" title="Apostolico–Giancarlo algorithm">Apostolico–Giancarlo algorithm</a></li> <li><a href="/wiki/Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a></li> <li><a href="/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm" title="Boyer–Moore–Horspool algorithm">Boyer–Moore–Horspool algorithm</a></li> <li><a href="/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithm</a></li> <li><a href="/wiki/Rabin%E2%80%93Karp_algorithm" title="Rabin–Karp algorithm">Rabin–Karp algorithm</a></li> <li><a href="/wiki/Raita_algorithm" title="Raita algorithm">Raita algorithm</a></li> <li><a href="/wiki/Trigram_search" title="Trigram search">Trigram search</a></li> <li><a href="/wiki/Two-way_string-matching_algorithm" title="Two-way string-matching algorithm">Two-way string-matching algorithm</a></li> <li><a href="/wiki/Zhu%E2%80%93Takaoka_string_matching_algorithm" title="Zhu–Takaoka string matching algorithm">Zhu–Takaoka string matching algorithm</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Multiple string searching</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Aho%E2%80%93Corasick_algorithm" title="Aho–Corasick algorithm">Aho–Corasick</a></li> <li><a href="/wiki/Commentz-Walter_algorithm" title="Commentz-Walter algorithm">Commentz-Walter algorithm</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Regular_expression" title="Regular expression">Regular expression</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Comparison_of_regular-expression_engines" class="mw-redirect" title="Comparison of regular-expression engines">Comparison of regular-expression engines</a></li> <li><a href="/wiki/Regular_grammar" title="Regular grammar">Regular grammar</a></li> <li><a href="/wiki/Thompson%27s_construction" title="Thompson's construction">Thompson's construction</a></li> <li><a href="/wiki/Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">Nondeterministic finite automaton</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Sequence_alignment" title="Sequence alignment">Sequence alignment</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/BLAST_(biotechnology)" title="BLAST (biotechnology)">BLAST</a></li> <li><a href="/wiki/Hirschberg%27s_algorithm" title="Hirschberg's algorithm">Hirschberg's algorithm</a></li> <li><a href="/wiki/Needleman%E2%80%93Wunsch_algorithm" title="Needleman–Wunsch algorithm">Needleman–Wunsch algorithm</a></li> <li><a href="/wiki/Smith%E2%80%93Waterman_algorithm" title="Smith–Waterman algorithm">Smith–Waterman algorithm</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Data_structure" title="Data structure">Data structure</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">DAFSA</a></li> <li><a href="/wiki/Suffix_array" title="Suffix array">Suffix array</a></li> <li><a href="/wiki/Suffix_automaton" title="Suffix automaton">Suffix automaton</a></li> <li><a href="/wiki/Suffix_tree" title="Suffix tree">Suffix tree</a></li> <li><a href="/wiki/Generalized_suffix_tree" title="Generalized suffix tree">Generalized suffix tree</a></li> <li><a href="/wiki/Rope_(data_structure)" title="Rope (data structure)">Rope</a></li> <li><a href="/wiki/Ternary_search_tree" title="Ternary search tree">Ternary search tree</a></li> <li><a href="/wiki/Trie" title="Trie">Trie</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Parsing" title="Parsing">Parsing</a></li> <li><a class="mw-selflink selflink">Pattern matching</a></li> <li><a href="/wiki/Compressed_pattern_matching" title="Compressed pattern matching">Compressed pattern matching</a></li> <li><a href="/wiki/Longest_common_subsequence" title="Longest common subsequence">Longest common subsequence</a></li> <li><a href="/wiki/Longest_common_substring" title="Longest common substring">Longest common substring</a></li> <li><a href="/wiki/Sequential_pattern_mining" title="Sequential pattern mining">Sequential pattern mining</a></li> <li><a href="/wiki/Category:String_sorting_algorithms" title="Category:String sorting algorithms">Sorting</a></li> <li><a href="/wiki/Semi-Thue_system" title="Semi-Thue system">String rewriting systems</a></li> <li><a href="/wiki/String_operations" title="String operations">String operations</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Help:Authority_control" title="Help:Authority control">Authority control databases</a>: National <span class="mw-valign-text-top noprint" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q1503724#identifiers" title="Edit this at Wikidata"><img alt="Edit this at Wikidata" src="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4307192-2">Germany</a></span></li></ul></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Pattern_matching&oldid=1256970399">https://en.wikipedia.org/w/index.php?title=Pattern_matching&oldid=1256970399</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Pattern_matching" title="Category:Pattern matching">Pattern matching</a></li><li><a href="/wiki/Category:Conditional_constructs" title="Category:Conditional constructs">Conditional constructs</a></li><li><a href="/wiki/Category:Functional_programming" title="Category:Functional programming">Functional programming</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_February_2011" title="Category:Articles needing additional references from February 2011">Articles needing additional references from February 2011</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_January_2019" title="Category:Articles with unsourced statements from January 2019">Articles with unsourced statements from January 2019</a></li><li><a href="/wiki/Category:Articles_to_be_expanded_from_May_2008" title="Category:Articles to be expanded from May 2008">Articles to be expanded from May 2008</a></li><li><a href="/wiki/Category:All_articles_to_be_expanded" title="Category:All articles to be expanded">All articles to be expanded</a></li><li><a href="/wiki/Category:Commons_category_link_from_Wikidata" title="Category:Commons category link from Wikidata">Commons category link from Wikidata</a></li><li><a href="/wiki/Category:Articles_with_example_Haskell_code" title="Category:Articles with example Haskell code">Articles with example Haskell code</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 12 November 2024, at 14:11<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Pattern_matching&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-ksxdk","wgBackendResponseTime":165,"wgPageParseReport":{"limitreport":{"cputime":"0.550","walltime":"2.038","ppvisitednodes":{"value":1587,"limit":1000000},"postexpandincludesize":{"value":47061,"limit":2097152},"templateargumentsize":{"value":2316,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":30,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":70880,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 1950.250 1 -total"," 6.70% 130.653 1 Template:Reflist"," 5.82% 113.500 9 Template:Cite_web"," 5.17% 100.925 1 Template:Short_description"," 4.41% 86.008 1 Template:Strings"," 4.30% 83.833 1 Template:Navbox"," 4.17% 81.297 1 Template:More_citations_needed"," 4.07% 79.319 2 Template:Ambox"," 3.22% 62.825 2 Template:Sister_project"," 3.13% 61.001 2 Template:Side_box"]},"scribunto":{"limitreport-timeusage":{"value":"0.318","limit":"10.000"},"limitreport-memusage":{"value":6347581,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-sscwj","timestamp":"20241122140612","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Pattern matching","url":"https:\/\/en.wikipedia.org\/wiki\/Pattern_matching","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1503724","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1503724","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-07-27T11:12:17Z","dateModified":"2024-11-12T14:11:04Z","headline":"checking a given sequence of tokens for the presence of the constituents of some pattern, but less strict than exact match as in pattern recognition"}</script> </body> </html>