Reducers a la Rich Hickley in Ruby

This is a draft of an article which translates Rich Hickley’s “reducers” concept into the Ruby language.

http://clojure.com/blog/2012/05/08/reducers-a-library-and-model-for-collection-processing.html

collect, aka map, does:
1. Recursion (apply function to head, then call map recursively on the tail)
2. Consumes an ordered list (guarantees order of execution)
3. Produces an ordered list

reduce, as currently provided in Clojure, is ignorant of the collection structure & allows the collection to implement the coll-reduce protocol. Also, it can produce anything: an aggregate, a map, etc. Still inherently sequential (monotonic) in the order of the operations (left fold with seed).

Don’t create a new collection when we call map or filter… don’t add your result to the collection inside the reduce…

How to produce a result? A Reduction Transformer.

We want to be able to create a recipe for creating pies, maybe even before we have a bag of apples. This implies being able to compose multiple reductions. Composing might look something like: map(take_sticker_off_apple).map(reject_bad_apples)

reducing function: function you pass to reduce… a binary operator, such as addition. Arguments don’t have to be symmetric: order is important. First arg is seed/result/accumulator… second arg is input to process that’s building the result.
mapping a function: you have a reducing function

//f1 is the reducing function (a binary operator, etc. see above)
// f(input) is "mess with that input"
mapping(f) { // this is a reduction transformer
 ->(f1) {
  ->(result, input) {
    f1.call(result, f.call(input)
  }
}

do_stuff_to_input(input) {
  input.label = nil
  return input
}
filter_mapping = mapping(do_stuff_to_input) #we have bound f

reducing_function(result, input) {
  return result + input
}
modified_reducing_function = filter_mapping.call(reduction_transformer) #we have bound f1

bag_of_apples.reduce(modified_reducing_function)

Mapping case: 1->1 case
Filtering case: 1->1/0

filtering(predicate_fn) { // this is a reduction transformer
  ->(reducing_fn) {
    ->(result, input) {
      if(predicate_fn.call(input)) {
        return reducing_fn.call(result, input)
      else
        return result
      }
    }
  }
}

bag_of_apples.reduce(
  filtering(is_good_apple?) //predicate_fn is bound
    .call(array_concat) //reducing_fn is bound
)

takes a reducing function, returns one, and if predicate is true call reducing function on the result with the new input. What if predicate false? Just don’t touch the result. This is the right way to write filter.

One to many case: 1->M eg. mapcat

mapcatting(f) {
  ->(reducing_fn) {
    ->(result, input) {
      reduce(reducing_fn, result, f.call(input))
    }
  }
}

bag_of_apples.reduce(
  mapcatting(slice_apple_into_pieces(5)).call(array_concat)
)

There’s a lot of repeated stuff… we can make a macro to reduce it down to the minimum.
It’s also not pretty. Function that returns a function, for example.

Also, this is not the cake.

TO BE CONTINUED