APattern-Match-Oriented Programming Exercises

To help you experience pattern-match-oriented programming, we have prepared problems in quiz format.

The member Function

Fill in the blank below to complete the member function.

def member x xs :=
  match xs as list eq with
  | `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}1\vphantom{0}\hspace{5em}}` -> True
  | _ -> False

member 1 [1,2,3,4]
-- True

member 5 [1,2,3,4]
-- False

The concat Function

Fill in the blanks below to complete the concat function.

def concat xss :=
  matchAllDFS xss as `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}1\vphantom{0}\hspace{5em}}` with
  | `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}2\vphantom{0}\hspace{5em}}` -> `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}3\vphantom{0}\hspace{5em}}`

concat [[1,2],[3],[4,5]]
-- [1,2,3,4,5]

Quadruplet Primes

Write a program that enumerates quadruplet primes. Quadruplet primes are quadruples of primes of the form \((p,p + 2,p + 6,p + 8)\).

take 4 (matchAll primes as list integer with
        | `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}1\vphantom{0}\hspace{5em}}` -> (p, p + 2, p + 6, p + 8))
-- [(5, 7, 11, 13), (11, 13, 17, 19), (101, 103, 107, 109), (191, 193, 197, 199)]

Prime Pairs with Difference \(6\)

Fill in the blank below to extract prime pairs \((p, p+6)\).

take 6 (matchAll primes as list integer with
        | `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}1\vphantom{0}\hspace{5em}}` -> (p, p + 6))
-- [(5, 11), (7, 13), (11, 17), (13, 19), (17, 23), (23, 29)]

The intersect Function

Fill in the blanks below to complete the intersect function, which extracts the intersection of two collections.

def intersect xs ys :=
  matchAllDFS (xs, ys) as `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}1\vphantom{0}\hspace{5em}}` with
  | `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}2\vphantom{0}\hspace{5em}}` -> `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}3\vphantom{0}\hspace{5em}}`

intersect [1,2,3,4] [2,4,5]
-- [2,4]

The difference Function

Fill in the blanks below to complete the difference function, which extracts only the elements of the first collection that are not contained in the second collection.

def difference xs ys :=
  matchAllDFS (xs, ys) as `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}1\vphantom{0}\hspace{5em}}` with
  | `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}2\vphantom{0}\hspace{5em}}` -> `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}3\vphantom{0}\hspace{5em}}`

difference [1,2,3,4] [2,4,5]
-- [1,3]

The doubles Function

Complete the doubles function, which extracts only the elements that appear exactly \(2\) times in a collection.

def doubles xs :=
  matchAllDFS xs as `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}1\vphantom{0}\hspace{5em}}` with
  | `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}2\vphantom{0}\hspace{5em}}` -> `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}3\vphantom{0}\hspace{5em}}`

doubles [1,2,3,2,1,1,4,5,3]
-- [2,3]

The tails Function

Define the tails function using pattern matching. Try to find two solutions: one using loop patterns and one without.

def tails xs :=
  matchAll xs as list something with
  | `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}1\vphantom{0}\hspace{5em}}`
  -> ts

tails [1,2,3,4]
-- [[1, 2, 3, 4], [2, 3, 4], [3, 4], [4], []]

Multiset Equality Check

Define a two-argument predicate equalMultiset that checks multiset equality using pattern matching.

def equalMultiset xs ys :=
  match (xs, ys) as (list eq, multiset eq) with
  | ([], [])
  -> True
  | `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}1\vphantom{0}\hspace{5em}}`
  -> equalMultiset xs' ys'
  | _
  -> False

equalMultiset [1,1,2] [2,1,1]
-- True

equalMultiset [1,1,2] [1,2,2]
-- False

Try writing it without recursion using loop patterns.

def equalMultiset xs ys :=
  match (xs, ys) as (list eq, multiset eq) with
  | `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}2\vphantom{0}\hspace{5em}}`
  -> True
  | _
  -> False

Poker Hand Evaluation Considering Jokers

Without modifying the implementation of the poker hand evaluation pattern matching (poker function) from Chapter 3, Section 3.2.2 at all, modify only the definition of the card matcher to enable poker hand evaluation that accounts for jokers.

def card := matcher
  | card $ $ as (suit, mod 13) with
    | Card $s $n -> [(s, n)]
    | Joker -> `\fcolorbox{black}[gray]{1.0}{\vphantom{0}\hspace{5em}1\vphantom{0}\hspace{5em}}`
  | $ as something with
    | $tgt -> [tgt]

poker [Card Spade 5, Card Spade 6, Joker, Card Spade 8, Card Spade 9]
-- "Straight flush"
poker [Card Spade 5, Card Diamond 5, Joker, Card Club 5, Card Heart 7]
-- "Four of a kind"