Map Reduce example in R. Demonstrates applying a map and reduce function to an input array, resulting in a hash of key/value pairs. This example maps a method to find prime divisors of each input value and then reduces the result by summing the input value for each prime divisor. See demo at http://www.r-fiddle.org/#/fiddle?id=tyir23SG&version=1

mapReduce.R

is.prime <- function(num) {
  if (num == 2) {
    TRUE
  } else if (any(num %% 2:(num-1) == 0)) {
    FALSE
  } else { 
    TRUE
  }
}

divisors <- function(x){
  #  Vector of numberes to test against
  y <- seq_len(x)
  #  Modulo division. If remainder is 0 that number is a divisor of x so return it
  y[ x%%y == 0 ]
}

primeDivisors <- function(input) {
  # Get divisors of the value.
  d <- divisors(input)
  
  # Get only those divisors that are prime.
  d[sapply(d, is.prime) == TRUE]
}

mapReduce <- function(input, map, reduceFunc) {
  # Apply the map function to the input.
  intermediate <- sapply(input, function(i) {
    results <- map(i)
    
    # Format the result as (result, input).
    sapply(results, function(r) {
      list(r, i)
    })
  })
  
  # Apply the reduce function to the intermediate result.
  reduce(intermediate, reduceFunc)
}

reduce <- function(input, reduceFunc) {
  # Reduce values to a hash by key.
  hash <- new.env()
  
  # Iterate over the input.
  sapply(input, function(i) {
    # Unlist the mapReduce result, so we look at each key/value pair.
    a <- unlist(i)
    
    # Iterate over the key/value pairs in the first group.
    sapply(seq(from=1, to=length(a), by=2), function(index) {
      # Get the key.
      key <- as.character(a[index])
      # Get the value.
      value <- a[index + 1]
      
      # Initialize the hash value.
      if (is.null(hash[[key]])) {
        hash[[key]] <- 0
      }
      
      # Apply reduce method to the existing hash value for the key and the new value.
      #hash[[key]] <- hash[[key]] + value
      hash[[key]] <- reduceFunc(hash[[key]], value)
    })    
  })  
  
  hash
}

#
# The map function takes an integer i and produces the list of pairs (p,i) such that p is a prime divisor of i. For example, map(12) = [(2,12), (3,12)].
# The reduce function is addition. That is, reduce(p, [i1, i2, ...,ik]) is (p,i1+i2+...+ik).
#
# Detail: The map function returns a list of prime divisors for the input. For example, for 15, the prime divisors are 3 and 5.
# The reduce function joins the same prime divisors together by summing their original inputs.
# For example, for the prime divisor 2, we add 24 + 30 = 54, resulting in a hash of [2, 54].
#
# Compute the output, if the input is the set of integers 15, 21, 24, 30, 49.
#
# Input: 15, 21, 24, 30, 49
#
# map(15) = [(3, 15), (5, 15)]
# map(21) = [(3, 21), (7, 21)]
# map(24) = [(2, 24), (3, 24)]
# map(30) = [(2, 30), (3, 30), (5, 30)]
# map(49) = [(7, 49)]
#
# reduce(2, 54)
# reduce(3, 90)
# reduce(5, 45)
# reduce(7, 70)
#

m <- mapReduce(c(15, 21, 24, 30, 49), primeDivisors, sum)

# Show result.
sapply(ls(m), function(key) {
  m[[key]]
})