Coding Ruby’s Enumerable#reduce in Golang

Problem: I have an array containing pairs of integers, except for one solo straggler: [9, 9, 3, 9, 7, 9, 5, 5]. What’s the easiest way to identify it?

The XOR Operator

In the binary number system, one can quickly and efficiently compare the bits of each number using a variety of operators. The XOR operator is very prevalent, often used in cryptographic algorithms, and is a kind of “logically exclusive OR” operation. When comparing two sets of bits, when both numbers are 1 or 0, the result is 0. If only one of the numbers is a 1, the result is also 1.

Examples

    1011      0101      0010      0000      1010
XOR 0110 XOR 1001 XOR 1110 XOR 1111 XOR 1010
-------- -------- -------- -------- --------
= 1101 = 1100 = 1100 = 1111 = 0000

Notice that XOR’ing an identical number against itself always returns 0. Going back to the original problem, we can XOR members of an array as part of a reduce function, quickly eliminating the pairs.

In Ruby, it can’t get much simpler than:

some_array = [1, 1, 2, 3, 3]
some_array.reduce(:^)
=> 2

The reduce method is part of the Enumerable module. The symbol notation signifies that the following element is a function that should be applied to each member of the collection. By passing Ruby’s XOR operator (the caret symbol), the reduce method will XOR the binary representation of each member. To better illustrate, here’s another version of the same method:

some_array.reduce do |memo, object|
memo^object
end

Golang, as powerful as it is, doesn’t include niceties such as reduce, so we’ll have to roll up our sleeves and write our own.

func Reduce(array []int, memo int, fn func(int, int) int) int {
for i := 0; i < len(array); i++ {
memo = fn(array[i], memo)
}
return memo
}

The function requires three arguments:

  1. An array of integers
  2. An integer to keep track of the calculated value between calls, or “memo”
  3. A function that applies an operation to reduce by. If you haven’t seen this before, Golang accepts functions as arguments and the use of closures. In our Ruby example, recall this function was the XOR operator:^.

So to use Reduce to calculate the unpaired member of the array, we can create a re-usable function:

func Unpaired(array []int) int { 
return Reduce(array, 0, func(val int, memo int) int {
return memo ^ val
})
}

And finally, the calculation in our main function correctly returns 2.

func main() {
a := []int{1, 1, 2, 3, 3}
item := Unpaired(a)
fmt.Println(item)
}

Have a better implementation in mind? Please share your feedback.