Scala, a small example of Euclid's Algorithm

A small posting today, a simple example of Euclid's algorithm in Scala. This algorithm can be expressed very concisely and simply using recursion. This example demonstrates the use of tuples and map in the Scala language.

If you don't know, Euclid's algorithm is a ancient, simple algorithm for finding the greatest common divisor (GCD) for two integers, without factoring either of the two integers in question.

The algorithm can be expressed recursively thus:

function gcd(x, y)
  if (y == 0) x
  else gcd(y, x mod y)

The particular construction worth noting in this example is the use of tuples.

Tuples are like records, structures or groupings of variables that can be constructed using a (x, y, z) syntax when x, y and z are variables. A tuple can be decomposed by accessing its elements using the t _1 syntax, where t is the tuple and _1 is a method that accesses the first element in tuple. Tuple elements are therefore indexed using a base of 1.

The example defines numbers as a list of tuples, each tuple contains a pair of integers - the two integers to be applied to the GCD algorithm (Euclid's Algorithm).

The list of tuples is then "mapped" using the map function that takes each tuple and calls the function x => ((Int, Int), Int, Boolean), where x will be each tuple in the list in turn.

The tuple x is decomposed into its two integer component parts using the x _1 and x _2 syntax.

The returned tuple ((Int, Int), Int, Boolean) contains the original tuple of integers to be tested, the gcd values and a boolean indicating if the numbers are co-prime. The numbers are co-prime if the GCD is equal to 1.

I've included a few different ways to represent the function used by map, to use and decompose the tuple. The first solution using the tuple argument directly and accesses its members using the _1, _2 syntax directly. The second solution uses a function literal and the _ placeholder syntax on the map argument. The function literal uses the val (a, b) = x; sytax to decompose the tuple into and and b, but this is a bit clumsey/verbose. The 3rd solution is essentially the same as a the 2nd but the function is defined in-line.

The last solution is probably the nicest, it uses the case(a, b) syntax to decompose the tuple into a and b using pattern matching.


Example Code:

package test

object EuclidsAlgorithm {

 def main(arg : Array[String]) = {

   // define a list of tuples (Int, Int), pairs to test for coprimeness
   val numbers = (3, 6) :: (3, 7) :: (4, 8) :: (5, 45) :: (5, 43) :: (1071, 1029) :: (1071, 1023) :: (1071, 1021) :: Nil

   // #1. Working with the tuple directly, using the tuple _1, _2 syntax
   val res1 = numbers map ( x => ((x _1, x _2),  gcd(x _1, x _2), gcd(x _1, x _2) == 1 )  )

   // #2. Defining a function literal
   val f = (x : (Int, Int)) => { val (a, b) = x;  ((a, b), gcd(a, b), gcd(a, b) == 1) }

   // and using it with the _ placeholder syntax for the parameter representing each element of the list
   val res2 = numbers map ( f(_) )

   // #3. Using the #2 above but in-line
   val res3 = numbers map ( x => { val (a, b) = x; ((a, b), gcd(a, b), gcd(a, b) == 1) }  )

   // #3. Using a case match on the tuple to expose its components a and b. This is probably the nicest and most concise way
   val res4 = numbers map ( { case (a, b) => ((a, b), gcd(a, b), gcd(a, b) == 1) } )

   res4.foreach(println)
 }

 // Euclids algorithm, finds the GCD
 def gcd(a : Int, b : Int) : Int = {

   if (b == 0)
     a
   else
     gcd(b, a % b)
 }
}

Results:

((3,6),3,false)
((3,7),1,true)
((4,8),4,false)
((5,45),5,false)
((5,43),1,true)
((1071,1029),21,false)
((1071,1023),3,false)
((1071,1021),1,true)

.