Talk:Pattern matching

This is the talk page for discussing improvements to the Pattern matching article. This is not a forum for general discussion of the subject of the article.

Add new text under old text. New to Wikipedia? Welcome! Learn to edit; get help. Start a new topic Assume good faith Be polite and avoid personal attacks Be welcoming to newcomers Seek dispute resolution if needed Article policies Neutral point of view No original research Verifiability

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computer science Mid‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science Mid This article has been rated as Mid-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

To-do list for Pattern matching: edit · history · watch · refresh · Updated 2019-02-14 Here are some tasks awaiting attention: Expand : Add information about: Fuzzy pattern matching Other methods for pattern matching, such as unification Pattern matching algorithms Pattern matching features of programming languages such as C#, C++, Rust, Swift, and SQL

"Pattern matching failure can often be ascribed to a type signature that is not strong enough or is incorrect."

I took that out because although I can imagine type signature can be blamed, I'm not at all assured that's a frequent or even reasonable cause. At least in Haskell, pattern type and expression type are statically checked to match. Perhaps if the type of a function is Maybe Integer -> Integer but giving Nothing as argument causes a matching failure, so the point would be the type should actually be Integer -> Integer? --82.181.66.63 10:32, 18 August 2005 (UTC)Reply

This article started as one about pattern matching in the ML family of programming languages. At some point a mention of Mathematica was added as an additional example. It's an interesting programming language, but not a general-purpose one, and its flavour of pattern matching is problematic as it's computationally expensive (NP-complete?). Thus I question whether the recent addition of the examples in Mathematica syntax and focus of discussion matter into regex-like features can keep the article focused. There already are articles about Mathematica and regexes, respectively, and their intersection might perhaps even warrant an article of its own. Be bold in your edits, but please include a comment, and discuss if you want to reach mutual understanding. --TuukkaH 22:54:17, 2005-09-03 (UTC)

Ok, this is still going into more general direction, I hope it works out well for an article with such an ambitious title :-) I just moved Mathematica and string pattern matching stuff into their own subsections. Now to make this more balanced, we would need at least:

• a subsection about Snobol syntax
• a short section and a see also to string patterns (regexes?)
• a subsection about history of pattern matching
• more examples to illustrate the points
• diagrams about patterns

--TuukkaH 01:34:26, 2005-09-10 (UTC)

I have a number of comments. First is that I think its a good idea to work together to make this a great section. However I respectfully disagree with the claims that Mathematica is not a general purpose language. I see it as an extremely general purpose language, that happens to also have a whole bunch of math functionality built it. (It is certainly as general purpose as ML or Haskell, and in some ways more so because of its graphics, import/export, and support for very wide array of programming constructs). It is true that the pattern matching in Mathematica is theoretically NP complete; yet in practice this is rarely an issue. Besides, I think it's good to cover pattern matching in all of its radically different flavors.

Perhaps we won't want to use the term general-purpose in this article then :-) There must be reasons why the programming language of Mathematica is without family. I can't but think it's designed as a scripting tool for symbolic mathematics, also built-in math already makes it special-purpose. Also, general-purpose is orthogonal with multi-paradigm. You do know that Haskell has been used to implement Perl 6 (Pugs), a revision-control system (Darcs) and an operating system with a graphical user-interface (House)? --TuukkaH 16:57, 21 September 2005 (UTC)Reply

I think my concept for the article is to list a bunch of ways pattern matching can be used, and then show how 2-3 "paradigmatic" languages implement those ideas. In a way, my structure was an implicit challenge. Mathematica's use of pattern matching is quite frankly powerful and advanced, and I wanted to see if people could post examples in other languages of the same sorts of things. (I am happy to see that this challenge has been met in some of the places). But it is not unreasonable to organize it by language rather than by application of pattern matching. I agree that diagrams would be helpful. --Kovas

It should be clear by now that I would prefer Haskell as the general syntax and to absolutely keep info about Mathematica in. I start another thread below, because I'm starting to have a hard time thinking of all the organizational possibilities. --TuukkaH 16:57, 21 September 2005 (UTC)Reply

Regarding complexity of pattern matching, with GHC's view patterns extension, pattern matching in Haskell can be arbitrarily complex. — Daf (talk) 02:08, 5 October 2009 (UTC)Reply

Contents at the moment:

1. Primitive patterns
2. Tree patterns
3. Filtering data with patterns
4. Pattern matching in Mathematica
   1. Declarative programming
5. Pattern matching and strings
   1. Tree patterns for strings
   2. Example string patterns

Contents from a previous version by Kevin:

1. Primitive patterns
2. Structure patterns
3. Pattern matching for user-defined types
4. Extracting data with patterns
5. Patterns for declarative programming
6. Pattern matching and Strings

Stuff I'd want to cover:

• Important uses: function definitions, filtering and extraction, replacing (==rewriting?)
• Languages: SNOBOL, Perl?, Mathematica, Haskell
• Patterns: primitives, combination, regexes, trees, advanced features
• History of pattern matching

Some of the language stuff can go to language-specific articles and some of the pattern stuff could go to a separate article about patterns if there are a lot of general features to discuss. --TuukkaH 16:57, 21 September 2005 (UTC)Reply

So a tentative table of contents:

1. Patterns (primitive, in Haskell function definitions)
   1. Sequences (Perl, regexes)
   2. Trees (combinations into trees)
2. Filtering and extraction
3. Rewriting
4. Mathematica (syntax, advanced features, symbolic features)
5. History
   1. SNOBOL (syntax)

--TuukkaH 16:57, 21 September 2005 (UTC)Reply

Am I wrong in thinking pattern matching is used in AI? It doesn't seem to be mentioned on the page at all.

I'm thinking of the syntax matching Parry did, when he converted sentences into basic syntax forms. Thanks,

--Elín 23:08, 13 January 2007 (UTC)Reply

Pattern-matching is used by the human brain - it is one of our greatest strengths. One of the first things a baby masters is the visual tracking of human faces. But this article only mentions pattern-matching from the computer standpoint. Grassynoel 09:03, 16 September 2007 (UTC)Reply

Seems like this article should be titled "Pattern matching in Haskell", not "Pattern matching".

Well, not really - it also talks about pattern matching in Mathematica...

I'm glad we all agree it should be titled something like "Pattern matching in obscure languages". For my part I would expect to see a pattern matching article mention things like Rete or Levensthein distance rather than deep dives into various peoples' favorite obscure languages. Hard to even give this article points for mentioning regular expressions because they're barely examined.

An article that treats a class of algorithms should be offering information about those algorithms and techniques in a language-agnostic sense, not losing the reader in the syntax and implementation details of an specific implementation language. -- Mikeblas 17:11, 13 October 2007 (UTC)Reply

What is "language-agnostic" in the context of programming? The sort of pseudocode I've seen usually bears a striking resemblance to the favoured language of its progenitor (typically Pascal or C).

Should Wikipedia articles be written in a "natural language agnostic" sense, by avoiding the use of English? Should we invent a "pseudo-English", whose only purpose is to avoid losing readers in the details of actual English? I am being facetious, obviously, but there is a serious point to be made here. It's a bit too constraining to talk about programming without being able to present any actual source code.

Yes again you've nailed it. This should not be a programming centric article.

Could you be more specific about which pieces of the text you think go into the details of Haskell too much, in the context of this article?—greenrd 19:34, 13 October 2007 (UTC)Reply

I've added a hatnote indicating this article (currently) concerns itself with pattern matching in functional programming languages, even though the lead does not accurately reflect this. "Pattern matching" is often used as a synonym for string matching and especially pattern recognition. Perhaps this should be turned into a disambiguation page instead? —Ruud 12:02, 7 March 2012 (UTC)Reply

Hello fellow Wikipedians,

I have just modified 8 external links on Pattern matching. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20070203111451/http://www.cs.nott.ac.uk/~ctm/view.ps.gz to http://www.cs.nott.ac.uk/~ctm/view.ps.gz
• Added archive https://web.archive.org/web/20170409021442/http://www.reouterhelpsupport.com/arris-customer-service.php to http://www.reouterhelpsupport.com/arris-customer-service.php
• Added archive https://web.archive.org/web/20110711112227/http://pure-lang.googlecode.com/svn/docs/pure-intro/pure-intro.pdf to http://pure-lang.googlecode.com/svn/docs/pure-intro/pure-intro.pdf
• Added archive https://archive.is/19990225161739/http://www.haskell.org/development/views.html to http://www.haskell.org/development/views.html
• Added archive https://web.archive.org/web/20060304053330/http://wwwhome.cs.utwente.nl/~tina/apm/applPatts.pdf to http://wwwhome.cs.utwente.nl/~tina/apm/applPatts.pdf
• Added archive https://archive.is/20130630081135/http://www.showtrend.com/ to http://www.showtrend.com/
• Added archive https://web.archive.org/web/20060211020429/http://cm.bell-labs.com/cm/cs/who/dmr/qed.html to http://cm.bell-labs.com/cm/cs/who/dmr/qed.html
• Added archive https://web.archive.org/web/20090822225301/http://www.cs.nyu.edu/leunga/prop.html to http://www.cs.nyu.edu/leunga/prop.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 15:51, 3 September 2017 (UTC)Reply

The article seems to be languishing and does not provide an overview of pattern matching is modern languages, where a common set of functionality is emerging -- it references a bunch of these (Scala, F#, Haskell) but the examples are too ML- and Mathematica-centric, and the Haskell example is hard to follow. Gvanrossum (talk) 04:32, 16 June 2020 (UTC)Reply

• Indeed! There's so much left to say. Setting aside structural problems with the article as it stands, there are important things to say about irrefutability, exhaustiveness, complexity, prioritised vs nonintersecting alternatives and more, none of which are yet meaningfully addressed. Leastfixedpoint (talk) 08:42, 25 June 2025 (UTC)Reply

As it stands now (and as has been mentioned several times over the years on this very talk page) the article is a bit schizophrenic.

• On one hand, this is currently the main article of Category:Pattern matching (think approximate string matching, diff, escape characters, metacharacter, wildcard characters etc., with Category:Regular expressions and Category:String matching algorithms as sub-categories).
• On the other hand, the article is in the categories Category:Conditional constructs and Category:Functional programming, and most of the article body talks about pattern matching as it is used in a variety of programming languages as a language construct for conditional execution. That's mostly in programming languages with built-in support for algebraic data types, especially sum types, and (for historical reasons?) that's mostly functional programming languages, though Rust for example has match, and there are proposals to add pattern matching for std::variant that was introduced with C++17.

So, perhaps it would be a good idea to split off most the article body into a separate article, e.g. named Pattern matching (programming languages) or Pattern matching (conditional)? – Tea2min (talk) 13:46, 30 November 2020 (UTC)Reply

@Tea2min: This article already has a disambiguation hatnote that explains that this article is about pattern matching in functional programming languages. Pattern matching in strings is also known as "string matching." Jarble (talk) 01:05, 28 May 2021 (UTC)Reply

@Jarble: Well, yes. I guess what I am trying to say is that "pattern matching in functional programming languages" may not the primary topic for the term "pattern matching", and furthermore, there is a whole section in the article talking about Pattern matching and strings ("By far the most common form of pattern matching involves strings of characters. ..."), so the article is not exclusively about pattern matching in functional programming languages. (Perhaps it's just that I find it confusing that big parts of the article talk about Mathematica.) – Tea2min (talk) 06:11, 28 May 2021 (UTC)Reply

My own preference is for "discriminant" but that term seems to be largely unknown to others; "scrutinee" is strongly preferred in the informal poll I took on Mastodon in June 2025 (respondents mostly CS academics with deep functional programming experience), and seems to be the term consistently used in e.g. Rust documentation, Wiktionary etc. Leastfixedpoint (talk) 09:21, 2 September 2025 (UTC)Reply