Scala Match Case structure and traversing a List with odd terms cs and m?

Question

I am trying to understand this piece of code here

  def countChange(money: Int, coins: List[Int]): Int = (money, coins) match {
     case (0, _) => 1
     case (m, _) if m < 0 => 0
     case (_, cs)  if cs.isEmpty => 0
     case (m, cs) => countChange(m - cs.head, cs) + countChange(m, cs.tail) 
  }
}

where I cannot understand the pairs (0,_), (m,_), (_,cs) and (m,cs) because the terms m and cs are undefined in the body of the code.

What is this construction in traversing the List called? A pair of some matching patterns?

Answer 1

The list is being traversed recursively. This construct is called pattern matching

You can read it like:

If the tuple (money, coins) is a tuple whose first value is 0 then return 1 ignore the second value of the tuple

If the tuple (money, coins) is a tuple has a first value below 0 then return 0 ignore the second value of the tuple.

And so on...

The _ is used in pattern matching to simbolize that we don't care what that parameter is, it can be anything

Pattern matching in Scala is backed by the unapply method of Objects, read more about extractors. Meaning that for each case the method unapply will be called with the tuple (money, coins) as argument and if determines that it is a match it will pass the respective first value and second value to the case clauses.

Example:

The statement case (m, _) => ... will lead to the call Tuple2.unapply((money, coins))

Note

Case classes already define unapply methods for us. That's why you can use them in pattern matching 'out of the box'. Tuple2 is a case class.

Answer 2

This is an example of pattern matching, which is being used to recursively traverse your list of coins. Here is the same code re-written with comments, the important thing to know is that each case statement is matching a possible pattern of the tuple, and the _ are used for ignoring pieces of the tuple.

def countChange(money: Int, coins: List[Int]): Int = {

  // Construct a tuple for pattern matching on
  val tuple: (Int, List[Int])  = (money, coins)

  tuple match {

    // Check to see if money == 0
    case (0, _) => 1

    // m represents money, use a guard to check if m is negative 
    case (m, _) if m < 0 => 0

    // cs represents coins, use a guard statement check for empty list
    case (_, cs) if cs.isEmpty => 0

    // Recursive step.  Since the patterns are tried in order, we 
    // now know that if we make it to here m (money) is non-zero 
    // and non-negative, and we know that cs (coins) is a non-empty 
    // list.  Now we can  call the recursive function safely on 
    // the head of the list
    case (m, cs) => countChange(m - cs.head, cs) + countChange(m, cs.tail)
  }

}

Answer 3

This construct is often used to match on more than one variable at the same time. At the top of the match, you see (money, coins). This means that it's matching on the pair of both money and coins. It doesn't have a name, because it's perfectly ordinary matching on two values simultaneously.

I cannot understand the pairs (0,_), (m,_), (_,cs) and (m,cs) because the terms m and cs are undefined in the body of the code.

These terms are defined in the code. The cases define them. That's what matching and destructuring is all about.

(money, coins) match {
   case (0, _) => 1 // If money == 0, then coins is ignored and we return 1
   case (m, _) if m < 0 => 0 // m = money, coins is ignored. If m < 0, return 0
   case (_, cs)  if cs.isEmpty => 0 // money is ignored, cs = coins.
                                    // If we have no coins, return 0.
   case (m, cs) => countChange(m - cs.head, cs) + countChange(m, cs.tail)
   // Otherwise, m = money, cs = coins. Recurse down the list with
   // countChange(money - coins.head, coins) + countChange(money, coins.tail)
}

The reason for the tupling (money, coins) is because these patterns depend on both money and coins. You'd either need to nest matchs (ugly) or do even more ugly boolean logic in order to replicate these semantics.