12 Pattern Matching
When manipulating data, we almost always need to access their components (if any). This is exactly why our design recipe recommends that when you define a function that manipulates some kind of data, compose a template containing code fragments that extract the components of the input data. The essential of these code fragments, the parts that actually perform the extraction, are the so-called accessor functions, or simply accessors. The disadvantage of using accessors is that it often results in more verbose and thus less readable code, especially when the data is very complex. To handle complex data more gracefully, we need pattern matching.
Pattern matching is a technique that allows us to examine the form of data. Through the examination, we gain access to the components (if any) of data. This is achieved by constructing a pattern with the form of some expected data, but with the interesting components replaced by variables. These variables can be mentioned in an expression that comes together with the pattern. The form of the pattern determines the form of the data that can match. When they match, the variables in the pattern are bound to the corresponding components in the data; and the expression associated to the pattern can be evaluated in the scope of these bindings. Otherwise, the expression is not evaluated. Thus a pattern serves as a guard of its associated expression. Usually there are other pattern-expression pairs. In case one pattern fails to match, other pattern-expression pairs are tried.
Using pattern matching, we can write neat code, code that is clean, clear and concise. Racket supports pattern matching on a huge set of data. We will cover the essential, including matching literals and matching data structures, both built-in and user-defined. Then we will uncover the magic behind functions like + that can accept an arbitrary number of arguments. As you may guess, it has something to with pattern matching, but on a limited form.
12.1 Matching Literals
12.1.1 Motivating Example 1 —
We want to debitalize the world to see the truth!
In the bital world, bit (short for binary digit) is the smallest information unit. A bit can be either 0 or 1. In the logical world, truth is the most fundamental concepts. A truth value can be either true or false. Despite their superficial difference, these two worlds are so closely related, especially when we interpret 0 as false and 1 as true. This is what we mean by debitalization: translating a bit into a truth value, 0 to false and 1 to true.
We want to write a Racket program to do the translation. Bit can be represented just as number 0 or 1; truth can be represented by boolean false or true. Now we can define a function that debitalizes a bit.
; debit : number -> boolean ; debitalizes a bit, via equality test (define (debit b) (cond [(= b 0) false] [(= b 1) true]))
In addition to the one-to-one mapping between bit and truth, there are also correspondences between the fundamental operators in both worlds. In the bital world, these are the NOT, AND and OR operators. NOT negates an input bit, inverting 0 to 1 and input 1 to 0. AND conjoins two input bits, resulting 1 if and only if both inputs are 1. OR disjoins two input bits, returning 0 if and only if both inputs are 0. If you substitute false for 0 and true for 1 in the preceeding description, you can see it specifies exactly the logical ¬, ∧ and ∨ operators on truth values. According to the specification for the three bit operators, we can easily define three Racket functions that act the same.
; NOT : number -> number ; negates a bit, via pattern matching ; ... ; AND : number number -> number ; conjoins two bits, via equality test (define (AND b1 b2) (cond [(and (= b1 0) (= b2 0)) 0] [(and (= b1 0) (= b2 1)) 0] [(and (= b1 1) (= b2 0)) 0] [(and (= b1 1) (= b2 1)) 1])) ; OR : number number -> number ; disjoins two bits, via equality test ; ...
Exercise 3. Supply the definitions for NOT and OR.
With these three functions, we can simulate any arbitrary complicated operations in the bital world. After we get the final result of the simulation, we can readily see the truth by invoking the debit function to translate the result. For example,
(debit (NOT (OR (AND 0 1) (AND 1 0))))
Let us pause for a moment to have a look at the functions we have defined. They all involve equality tests. In particular, we have to write down these equality tests explicitly. In debit, they are just a few. But in AND, there seems too many than necessary. Indeed, we can rewrite AND as follows:
; AND : number number -> number ; conjoins two bits, via equality test (define (AND b1 b2) (cond [(= b1 0) 0] [(= b1 1) (cond [(= b2 0) 0] [(= b2 1) 1])])) ; OR : number number -> number ; disjoins two bits, via equality test ; ...
Exercise 4. Rewrite your OR definition if you also use too many equality tests.
In this version, we have decreased the number of equality tests by half. Though, can we do better? In other words, can we write even less but still maintain the behavior of the function. The answer is positive. With pattern matching, we can indeed write less but say the same. Let us see how debit would be defined using the match form provided by Racket.
; debit : number -> boolean ; debitalizes a bit, via pattern matching (define (debit b) (match b [0 false] [1 true]))
You see instead of a cond-expression, we now have a match-expression. A match-expression is similar to a cond-expression in structure except that:
It also takes another expression. In the two examples both are the variable b. But in general any expression is allowed.
The left of a clause (enclosed in brackets [ ]) is now a pattern instead of a boolean expression.
A pattern renders the form of some data. For the moment, a pattern can be any Racket literal, like a boolean, a number, a character, a string, etc. Later we will see a pattern can also describle a data structure. The right part of a clause can be any expression, as with that in a cond-expression.
A match-expression first evaluates the expression it takes, then tries to match the value of the expression against the pattern of each clause in sequence. On the first pattern it matches, the expression corresponding to the pattern is evaluated and its result is returned as the result of the whole match-expression. The behavior is similar to that of a cond-expression.
Basically, when a pattern is a literal, you can think of pattern matching as equality tests. But rather than say "is equal to", we say "matches". For example, you can read the match-expression as "match the value of expression b against 0, if it matches, return false; otherwise, match it against 1, if it matches, return true." Now comes the question, what if it also fails to match 1? Then Racket throws out an error. For example, try to evaluate (debit 2).
In general, when you construct a match-expression, you should make sure that you take all possible cases into account and provide at least one pattern that covers each case, just as you did before with a cond-expression.
Exercise 5. Write the pattern-matching version of NOT using the match form.
A match-expression is like any other expression. That is, it can appear anywhere a normal expression is expected. In particular, it can appear as the expression associated to a pattern inside another match-expression. In this case, we say we have nested match-expressions, just as we can have nested cond-expressions. AND can be rewritten using nested match-expressions.
; AND : number number -> number ; conjoins two bits, via pattern matching (define (AND b1 b2) (match b1 [0 0] [1 (match b2 [0 0] [1 1])])) ; OR : number number -> number ; disjoins two bits, via pattern matching ; ...
Exercise 6. Write the pattern-matching version of OR.
12.2 Matching Data Structures
12.2.1 Matching Built-in Data Structures
Debitalizing a single bit is just the first step. Massive information flows in the bital world like streams. When faced with a bit stream, we’d better have a function that can translate it into a truth stream. We can represent a bit stream as a list of bits, for example, (list 0 1 1 0). Then on top of debit, we can easily define a new function that can debitalize a bit stream.
; debits : (listof number) -> (listof boolean) ; debitalizes a bit stream, via isomorphism test (define (debits bs) (cond [(empty? bs) bs] [else (cons (debit (first b)) (debits (rest bs)))]))
Correspondingly, in the bital world, there must be operators that can manipulate bit streams. Naturally they are based on the three basic operators. Each of them operates on a bit stream or two bit streams bit by bit. Thus they are also called bit-wise operators. Similar to the case of debitalization, functions simulating them can also be defined on top of those functions that simulate single-bit operators.
; NOTs : (listof number) -> (listof number) ; bit-wise negates a bit stream, via isomorphism test ; ... ; ANDs : (listof number) (listof number) -> (listof number) ; bit-wise conjoins two bit streams, via isomorphism test (define (ANDs bs1 bs2) (cond [(or (empty? bs1) (empty? bs2)) empty] [else (cons (AND (first bs1) (first bs2)) (ANDs (rest bs1) (rest bs2)))])) ; ORs : (listof number) (listof number) -> (listof number) ; bit-wise disjoins two bit streams, via isomorphism test ; ...
Exercise 7. Supply the definitinos for NOTs and ORs.
These definitions are all defined by recursion on the built-in list data structure by the so-called isomorphism tests. Two data structures are said to be isomorphic if they have the same form. Again, the body of debits looks still not that bad. But the body of ANDs is cluttered by the accessor functions that decompose the list. One way to avoid this clutter is by moving the decompositions into the binding part of a let-expression as shown below.
; ANDs : (listof number) (listof number) -> (listof number) ; bit-wise conjoins two bit streams, via isomorphism test (define (ANDs bs1 bs2) (cond [(or (empty? bs1) (empty? bs2)) empty] [else (let [(b1 (first bs1)) (bs1 (rest bs1)) (b2 (first bs2)) (bs2 (rest bs2))] (cons (AND b1 b2) (ANDs bs1 bs2)))]))
Exercise 8. Rewrite debits and ORs in the same way.
This version is clearer but feels heavy. Here comes is the same question that whether we can do it by saying less. Yes, pattern matching helps again. Racket supports pattern matching on all built-in data structures, like pairs, lists, vectors, etc. Let us first see how the simpler debits can be rewritten using pattern matching.
; debits : (listof number) -> (listof boolean) ; debitalize a bit stream, via isomorphism test (define (debits bs) (match bs [(list) bs] [(list b bs ...) (cons (debit b) (debits bs))]))
Things new in the match-expression are the patterns: (list) and (list b bs ...). You see the syntax for patterns in Racket tries to mimic the actual form of the expected data as much as possible. This is exactly the meaning of isomorphim we explained above. But be aware that patterns in Racket are never evaluated. They serve only as specifications for the form of some expected data. So the pattern (list) is not evaluated, nor is the pattern (list b bs ...). The former happens to be a valid expression (when evaluated it will return an empty list). It specifies that only an empty list can match. The latter is even not a valid expression. It says only a non-empty list can match; and in particular, when a non-empty list matches, its first element and its remaining elements (as a list) will be bound respectively to the variable b and bs for use in the expression (cons (debit b) (debits bs)). An ellipsis ... is allowed in a list pattern and usually follows a variable. It indicates that the variable preceeding it can match a list of zero or more elements. For example, the pattern (list x ...) can match any list (empty or not), and the list will be bound to the variable x. In the pattern (list b bs ...), since there is another variable b before bs ..., together the whole pattern specifies that it can match a list of at least one element. All in all, the whole match-expression can be understood in terms of the version using cond to test isomorphism and let to bind the components extracted by the relevant accessor functions.
You may have noticed that a variable in a pattern seems to be able to match anything. The reason is that a variable has no structure. It acts as a placeholder. It is used only to name some components inside some matching data. In particular, if a variable appears alone as a pattern (not inside any data structure), matching will succeed immediately with whatever bound to the variable. Be careful with its powerful matching ability. If you accidentally placed a single variable pattern before any other pattern, matching can never reach other patterns. For example, in the following function,
(define (always-no order) (match order [whatever "No, Sir!"] ["Do it!" "Yes, Sir!"]))
you will never reply "Yes, Sir!" because whatever the order is, you reply immediately "No, Sir!". This is dangerous! So make sure that is what you intended to do. Sometimes, this kind of behavior is required. In particular, you may just want a dummy variable to match anything but ignore that thing. For this purpose, Racket provides a special identifier, the underscore _, usually called a wildcard. It acts as a pattern variable, that is, it can match anything, but it does no binding. Anything that matches is ignored. For example, we can use it to define the function that returns the length of a list as follows:
(define (len l) (match l [(list) 0] [(list _ xs ...) (+ 1 (len xs))]))
Since we do not care about what an element is, in particular, we we will not mention any element in the expression (+ 1 (len x)), we use the underscore in the pattern. When an underscore _ is used alone, not in any data structure, it plays the role of a default clause, just like an else clause in a cond-expression, for example:
(define (bit? b) (match b [0 "yes"] [1 "yes"] [_ "no"]))
One more thing to bear in mind is that the identifier list appearing in the head position of a list pattern is not a function name. This can be seen as an explanation for the claim that patterns are never evaluated. We will soon see patterns for other data structures. In these patterns, there are always one or more these kind of special names. A good way to understand their roles is by thinking of them as literals. It is important not to confuse them with variables in a pattern. They are used for identifying a particular type of data, thus list for a list.
Exercise 9. Rewrite NOTs using pattern matching.
As before, match-expressions can be nested. Back to our debitalization example, we can rewrite ANDs using nested match-expressions.
; ANDs : (listof number) (listof number) -> (listof number) ; bit-wise conjoins two bit streams, via isomorphism test (define (ANDs bs1 bs2) (match bs1 [(list) bs1] [(list b1 bs1 ...) (match bs2 [(list) bs2] [(list b2 bs2 ...) (cons (AND b1 b2) (ANDs bs1 bs2))])]))
Exercise 10. Rewrite ORs in the same way.
Since list is such an important data structure. Racket supports rich patterns around it. Here are more examples.
> (match (list 1 2) [(list 0 1) "one"] [(list 1 2) "two"]) "two"
> (match (list 1) [(list x) (+ x 1)] [(list x y) (+ x y)]) 2
> (match (list 1 2) [(list x) (+ x 1)] [(list x y) (+ x y)]) 3
> (match (list 2 2) [(list x x) "equal"] [_ "not equal"]) "equal"
> (match (list 2 3) [(list x x) "equal"] [_ "not equal"]) "not equal"
The last two examples show that Racket even supports the so-called non-linear patterns. In these kind of patterns, variables can appear multiple (so non-linear) times rather than just once (linear time). In the two examples, the pattern variable x appears twice. But be aware that using the same name for two different things is usually the origin of confusion. You would better avoid it.
The ellipsis ... in Racket is a powerful utility to build very general patterns. Here are two examples.
> (match (list 1 2 2 2 3 4) [(list 1 2 ... 3 4) "ones and two"] [else "other"]) "ones and two"
> (match (list 1 2 2 2 3 4) [(list 1 x ... 3 4) x] [else "other"]) '(2 2 2)
Try to play with it to see how expressive you can be. Constructing patterns is fun and art. The philosophy of pattern matching is accessing data by constructing pattern instead of defining accessors. Sometimes, a clever pattern is all what you need to get access to the interesting components of a complex data structure. Be constructive! Be creative!
12.2.2 Matching User-defined Data Structures
In addition to built-in data structures, Racket also support pattern matching on user-defined data structures via using struct or define-struct. We will illustrate its usage through a second motivating example, poker cards.
12.2.2.1 Motivating Example 2 —
Every poker card has a rank and a suit. The rank of a card is one of the numbers from 2 to 10, or one of the symbols A (Ace), J (Jack), Q (Queen) and K (King). The suit of a card is one of the the symbols ♠ (Spade), ♥ (Heart), ♦ (Diamond), and ♣ (Club).
We can represent a poker card as a struct.
(define-struct card (rank suit)) ; rank : "2", "3", "4", "5", "6", "7", "8", ; "9", "10", "J", "Q", "K", "A" ; suit : "♠", "♥", "♦", "♣"
For simplicity, we use string uniformly for a rank, insted of a mixture of numbers and strings. A suit is also represented as a string.
Let us first define a function that echoes the name of a rank.
; rank-name : string -> string ; echoes the name of a rank (define (rank-name r) (match r ["A" "Ace"] ["J" "Jack"] ["Q" "Queen"] ["K" "King"] [_ r]))
This time, we define the function directly by pattern matching on the input string. Imagine what you would have to do without pattern matching. Note that how the underscore _ is effectively used to match all other ranks, that is numbers. Since these numbers are in string forms, we return them immediately.
Exercise 11. Define a function suit-name that echoes the name of a suit.
A poker card is usually called by first saying its rank name, followed by the word "of" and then the plural form of its suit name. For example, the card 🂡 will be called "Ace of Spades", the card 🃊 will be called "10 of Diamonds", and so on. Fortunately the plural form for all the four suit names are simply formed by appending an "s". We want to write a function that echoes the name of a card. With the aid of rank-name and suit-name we can easily define it. We will first do it in the old way, that is, by invoking the accessor functions to access the rank and suit of a card. Here is the definition.
; card-name : card -> string ; echoes the name of a card (define (card-name c) (string-append (rank-name (card-rank r)) " of " (suit-name (card-suit s)) "s"))
Or we can first use let to name the extracted components and rewrite it like this.
; card-name : card -> string ; echoes the name of a card (define (card-name c) (let [(r (card-rank c)) (s (card-suit c))] (string-append (rank-name r) " of " (suit-name s) "s")))
Having tasted the benefits of pattern matching, we are eager to see how it will be done using pattern matching. Here it is.
; card-name : card -> string ; echoes the name of a card (define (card-name c) (match c [(struct card (r s)) (string-append (rank-name r) " of " (suit-name s) "s")]))
We see again how the pattern (struct card (r s)) tries to mimic the form of the card data structure. In this pattern, struct acts as a literal, indicating that the pattern is a user-defined data structure pattern; card is similar to the role of list in a list pattern, thus also like a literal, indicating that the actual data structure expected is a card, not something else, say a posn. Two variables r and s hold the place for the rank and suit of a card respectively. As before, when a card matches, they will be bound to the rank and suit of the card respectively for later use. This example shows the way to construct a pattern for a user-defined data structure.
Exercise 12. Revise functions that manipulate other data structures you have defined, for example, posn, using pattern matching.
As a last example, we define a function that determines if two cards are the same. But this time we first pair the two cards and then do pattern matching on them both in one place.
; same-cards? : card card -> boolean ; determines if two cards are the same (define (same-cards? c1 c2) (match (cons c1 c2) [(cons (struct card (r1 s1)) (struct card (r2 s2))) (and (string=? r1 r2) (string=? s1 s2))]))
Note that the expression to match is now a cons-ed pair of the two input cards c1 and c2. Since the expression is a pair of two cards, our pattern also need to a pair pattern, with two sub-patterns for card. This is exactly what (cons (struct card (r1 s1)) (struct card (r2 s2))) specifies. Mind that in the pattern cons acts as a literal, indicating a pair pattern.
It seems we are trying to make things more complicated than necessary. Also this pairing and then de-pairing also introduces some extra overheads. So why are we bothering this intead of using nested match-expressions. The reason is that sometimes, such nesting could go vera deep, which makes the code less readable. For same-cards?, it is still not that obvious since it only accepts two arguments. We only need to nest one match-expression inside another.
; same-cards? : card card -> boolean ; determines if two cards are the same (define (same-cards? c1 c2) (match c1 [(struct card (r1 s1)) (match c2 [(struct card (r2 s2)) (and (string=? r1 r2) (string=? s1 s2))])]))
But imagine that we now want to define a function that takes three cards and determine if all of them are the same. Then we have to nest three match-expressions. If you still think it managable, imagine four, five or even more. In these cases the advantage of our technique manifests, even though it means we have to sacriface some efficiency. For example, we can define the function that determines the sameness among three cards as follows.
; same-3-cards? : card card card -> boolean ; determines if three cards are the same (define (same-3-cards? c1 c2 c3) (match (list c1 c2 c3) [(list (struct card (r1 s1)) (struct card (r2 s2)) (struct card (r3 s3))) (and (string=? r1 r2) (string=? r2 r3) (string=? s1 s2) (string=? s2 s3))]))
This time we construct a list from the three input cards and use the list pattern instead. The transitivity of string=? guarantees that once two different pairs of strings are equal, all the three strings are equal.
Exercise 13. Rewrite the pattern-matching version of AND, OR, ANDs and ORs, do not use nested match-expressions.
Exercise 14. Read the Wikipedia article List of poker hands. Suppose we represent a hand as a list of 5 cards, for each poker hand category, write a function that tests whether a hand of cards belong to a specific category. You can find those functions that you may use to accomplish the task in the file card.rkt.
12.3 Matching Argument Lists
The last examples in the previous section shows that sometimes we want the arguments to a function collected in some data structure so that we can handle them, for example, do pattern matching on them, in one place. Of course, we can do this by ourselves, as we did in those examples. But it would be better if it is supported out of the box. Racket does support it. In Racket, when a function is passed in its arguments, it implicitly receives the arguments as a list. This is how a function sees its arguments under the hood. Racket provides ways that allow us to open the hood: getting the argument list. Through this explicit approach, we can handle the arguments collectively rather than individually.
12.3.1 An Explicit Way to Apply a Function
So far, we apply a function by simply enclosing the function and its arguments in a pair of parentheses ( ). For example, we write (+ 1 2 3), (length (list 1 2 3)), and so on. As an alternative, Racket also provides a function apply that can do the same job. It accepts a function you want to apply and a list of arguments you want to apply the function to, and, as its name suggests, apply the function to the arguments collected in the list. For example, instead of (+ 1 2 3), we can write (apply + (list 1 2 3)). As you can see, since we want to apply + to the arguments 1, 2 and 3, we first collect them in a list (list 1 2 3) and then feed the list together with the function + to the function apply. The two expressions, (+ 1 2 3) and (apply + (list 1 2 3)) have the same effect. That is, they both evaluates to 6.
Rewriting (length (list 1 2 3)) using apply is a little tricky. It is easy to put it like (apply length (list 1 2 3)). But this is wrong. Recall that length accepts a single argument which must be some list and returns the length of that input list. Since the second argument to the function apply is supposed to be a list that contains all the arguments we want to feed to the function we want to apply, we should first put the single argument to length in a list. That is, if we want to apply length to the list (list 1 2 3), we should first put this list in a list, (list (list 1 2 3)), then supply it with length to apply. Thus the correct answer is (apply length (list (list 1 2 3))). Again, evaluating both expressions should give the same result, 3.
This more explicit way to apply a function seems redundant. Indeed for most senarios, you do not need it and you are even encouraged not to use it. If you want to apply a function, do it in the usual, more direct way. So, write (+ 1 2 3) instead of (apply + (list 1 2 3)), (length (list 1 2 3)) instead of (apply length (list (list 1 2 3))), for the sake of readability. Though, this indirect way to apply a function by invoking apply on the function and the argument list, fancy or clumsy, has its use. It is one essential part of the magic behind variadic functions, those that can accept an arbitrary number of arguments.
12.3.2 The Magic behind Variadic Functions
You have been curious about how + can accept an arbitrary number of arguments for long. These kind of functions are called variadic functions. Their existence contributes a lot to the brevity of Racket expressions. Suppose that + can only accept two arguments, to add three numbers, say 1, 2 and 3, we have to write it (in one possible way) as (+ 1 (+ 2 3)). If this still looks not bad, imagine how many plus signs and parentheses you have to write to add ten numbers. But with + being variadic, to add ten numbers, say from 1 to 10, we simply write (+ 1 2 3 4 5 6 7 8 9 10). The question is of course how it works. And more importantly, can we define a function like this too? The answer is a certain "yes".
The idea is to identify the sequence of arguments fed to a function as a list.
Since a list could be arbitrarily long, it means the arguments could be
arbitrarily many. With this identification, the eseential turns out to be —
(define (f x y) ; body )
Apparently the function f can accept three arguments since following its name are three variables x, y. Without loss of generality, let us further assume that the function f expectes two numbers as arguments. Suppose f is applied to numbers 1 and2, again in the usual direct way, that is, (f 1 2). According to our knowledge, each variable will be bound to one argument in order, so x to 1 and y to 2. Now it is clear that there is no way in this old syntax that would allow us to express that binding one varible to the whole list of arguments. In particular, inserting an extra variable in any valid position to the header does not work since the resulting definition
(define (f x y z) ; body )
defines a function that can accept three arguments. When it is applied, one variable still gets bound to one argument correspondingly. What we need is a special syntax that allows us to specify a variable intended to be bound to the whole argument list when the function is applied. The Racket syntax to do so is by prefixing this particular variable a dot .. So we write it like this:
(define (f . xs) ; body )
The function f defined thus can accept an arbitrary number of arguments. In particular, we know that when it is applied, all the arguments fed to it will be collected in a list and the variable xs will be bound to this argument list. With this knowledge, in the body of the function definition we can case analyze xs and do things accordingly.
Now we have all the tools in hand to define a variadic function. Let us define a function that sums an arbitrary number of numbers. This is indeed what + does. But in order to show you how you can do the same thing, let us again suppose that + can only add two numbers. The definition of sum goes as follows.
; sum : number ... -> number ; sums an arbitrary number of numbers (define (sum . ns) (cond [(empty? ns) 0] [else (+ (first ns) (apply sum (rest ns)))]))
You see we do case analysis on the argument list. If it is empty, we return 0. If it is not, we first take out the first argument of the list, then apply sum recursively to the rest of the argument list, and finally + the first number to the result of the result returned from the recursive application. The surprise is that the recursive application is done by invoking apply, instead of applying sum to the rest of the argument list directly. A moment’s thought reveals that (sum (rest ns)) indeed would not work. Because what it actually does is supplying the rest of the argument list, which is a list of numbers, as a single argument to sum. This is not what sum expects. Every argument to sum must be a number, instead of a list of numbers. To see more clearly why using apply works, let us see a simple example, say (sum 1 2 3). First, ns will be bound to the the whole argument list (list 1 2 3); then the list is checked to see if it is empty, since apparently not, we reach the else branch; substituting in the result of (rest ns) gives (apply sum (list 2 3)). According to our description of apply, this expression has the same effect as (sum 2 3), which is what we want.
If you have appreciated the benefits of pattern matching, you should be tempted to rewrite sum using match.
Exercise 15. Write a function product that calculates the product of an arbitrary number of numbers using match. Assume the function * can only accept two arguments.
At the end of the previous section, we hinted that sometimes we want to avoid nested pattern matching for the sake of readability when manipulating several data. In particular, we showed how we could do that by first collecting these data in in a pair or a list, and then accordingly provide a pair or list pattern containing sub-patterns corresponding these data. In that way, we can do pattern matching in one place. Our examples there particularly concerned collecting arguments. Now that we see that we do not have to do this argument collection ourselves, we can rewrite, for example, same-cards? like this:
; same-cards? : card card -> boolean ; determines if two cards are the same (define (same-cards? . cs) (match cs [(list (struct card (r1 s1)) (struct card (r2 s2))) (and (string=? r1 r2) (string=? s1 s2))]))
Exercise 16. Rewrite AND, OR and same-3-cards? in a similar way.
You can also put as many variables before the dot . in a function header. (But only one variable is allowed after it.) For example,
(define (f x y . z) ; body )
will define a function that accepts at least two arguments. The first two arguments are mandatory and will be bound to x and y respectively. Then zero or more arguments can follow. They will be collected in a list and bound to z. Since the list can be empty, these arguments can be seen as optional. Below is a simple exmaple showing its usage.
; greet-person : string string ... -> string ; greets persons (define (greet-person g . ps) (match ps [(list) (string-append g "!")] [(list p) (string-append g ", " p "!")] [(list p ps ...) (string-append g ", " p "! " (apply greet-person (cons g ps)))]))
We can use this function to produce greetings for an arbitrary number of persons, for example, (greet-person "Hi" "Kos" "Tir" "Day"). Notice that in the recursive application, (apply greet-person (cons g ps)), we need to cons g into ps, otherwise in the recursive calls, greet-person will no longer receive the first argument it expects. Try to see what will happen with the example if we accidentally write just (apply greet-person ps).
Though allowing variables before the dot . does offer some convenience. We can achieve the same effect without inserting any variable before the dot ., as shown below.
(define (f . xs) (match xs [(list x y z ...) ; body ]))
The point is that we can see this feature as a limited form of pattern matching.