Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to understand the basic ideas of pattern calculus and do not have a lot of time to read through a rather long book. Can someone explain this in simple terms and give an example of how pattern calculus works?

I don't understand "The ability to pass patterns as parameters (pattern polymorphism) is illustrated by defining a generic eliminator." as explained here in the Wikipedia article. If someone could work through an example showing how the patterns were transformed and why they were transformed in that way, that would be useful to me, thanks.

share|cite|improve this question
AJed's comment is a result of a simple Google search. You didn't have time to do that before you asked this question? – scaaahu Jan 22 '13 at 2:40
I don't understand the bottom half of that wikipedia article "pattern polymorphism". – Phil Jan 22 '13 at 2:42
Then I suggest you to edit your question to tell us what you already understand and what you don't yet. – scaaahu Jan 22 '13 at 2:47
up vote 3 down vote accepted

I can't really say that I know bondi (this is the first time I heard about it), but my experience with functional languages will allow me to give you hints.

Let's first discuss what the example given in the wikipedia page do. There are two functions called elimLeafs and elimCount. Both are accessed such as elimLeaf (Leaf 3) returns 3 and elimCount(Count 3) returns 3. "Do not focus on what these functions do !" .. There is a similarity between the two functions in that:

  • elimLeaf (Laef x) or elimCount (Count x) can be return as elimPattern (Pattern x) where Pattern is either Count, Leaf or any other thing you want to name.

Knowing this, you can write both functions such as "Pattern" in elimPattern (Pattern x) is a variable .. and whence you can write both elimPattern and elimLeaf such as:

 elim = | x -> | {y} x y -> y 

which can be called as:

  elim Leaf (Leaf 3) returns 3 .... for example.

The function elim above is actually two functions (or I dont know what is called in Bondi). First, you got the name of the function, which is elim. The name shall be followed by =| . Then you have the definition of the function"s" which is followed by ->. So,

  • "elim Leaf" is matched with "elim =| x" and therefore evaluated to | {y} x y
  • Now, x is Leaf in "elim Leaf". Thus, "| {y} x y" is equivalent to "| {y} Leaf y".
  • The function elim above can be further evaluated such that "| {y} Leaf y -> y" (that is "| {y} Leaf y" is evaluated to y.) y in this case would be 3, given the input above.
  • Note here that right now you did exactly what elimLeaf did ! You can do the same for elimCount by simply replacing Leaf by Count in the input.

To clarify more: Assume you want to do this with C++. The definition of the functions elimCount and elimLeaf are as follows:

int elimCount(int x) { return x;} 
int elimLeaf(int x) { return x;}     // we are just assuming int in this example, 

To write both these functions with only one, perhaps you would do something like:

int elim (const char* pattern, int x) { 
    if (strcmp(pattern, "Leaf") == 0) return x
    if (strcmp(pattern, "Count") == 0), return x
share|cite|improve this answer
So far this doesn't seem to be any more than what Scala case classes with pattern matching can do, perhaps I am missing something – Phil Jan 22 '13 at 10:04
Well this answers the question anyhow. – Phil Jan 22 '13 at 10:37
I dont know really, i ve never worked with scala. But there is a lot of things in CS that are explained using very complex tools, while they can also be explained with the simplest ever tools ! – AJed Jan 22 '13 at 20:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.