3 ms·

Thanks. I just looked up "map/reduce" on Wikipedia. Gee, I've been speaking 'prose' (an old joke) all along! So, I was procrastinating from working on my cod

• ww520 12y ago
  Actually "transducer" can be done with straight function composition. It would work in any language supporting high order function, a fancy way of saying passing function around as argument or return value. e.g. in Javascript (I'll be overly verbose for illustration) function mySumReducer(sum, value1) { return sum + value1; } function myTimesReducer(product, value1) { return product * value1; } [1, 2, 3, 4].reduce(mySumReducer, 0) gives 10 [1, 2, 3, 4].reduce(myTimesReducer, 1) gives 24 function myDoubler(x) { return x * 2; } function valueTransducer(originalReducer, valueEnhancer) { var newReducer = function(memo, value) { var newMemo = originalReducer(memo, valueEnhancer(value)); return newMemo; } return newReducer; } var myDoubleSumReducer = valueTransducer(mySumReducer, myDoubler); var myDoubleTimesReducer = valueTransducer(myTimesReducer, myDoubler); [1, 2, 3, 4].reduce(myDoubleSumReducer, 0) gives 19 [1, 2, 3, 4].reduce(myDoubleTimesReducer, 1) gives 192 valueTransducer is a generic transducer that can be used to apply an extra function to the value during the reduction process. Voila, you got a transducer in Javascript! To make it more useful, function fancyTransducer(originalReducer, valueEnhancer, memoEnhancer) { return function(memo, value) { return memoEnhancer(originalReducer(memo, valueEnhancer(value))); } } This generic transducer can transform the value and memo of the original reducer. Also since the transducer returns another reducer, you can chain it up by calling transducer again with it using different enhancers. The wonder of functional composition. It's nothing fancy once it's laid out. It's just a useful programming pattern.
  • defen 12y ago
    Actually this doesn't really capture the idea properly - you need a "reducerComposer" function that can compose any functions that look like mySumReducer / myTimesReducer (take a memo and a value). You've just manually composed them in myDoublingTransducer, which indeed is just straight function composition. Your reducerComposer needs to function if the first reducer returns nothing (e.g. filter) or multiple values (e.g. flattening a list of lists). One way to think of it is that you are "pushing" values through a chain of reducers, and at any step you might produce 0, 1, or multiple values for the next step.
    • ww520 12y ago
      Sorry I was editing before I saw your comment. Note: There was a myDoublingTransducer before. On a separate note, a reducer returns nothing doesn't make sense. A reducer might not add the current value to the memo (filter) but it always returns some memo for the next step. Also a reducer would not return multiple values. It returns just one value, the memo. If there are multiple values produced at a step, they would have been added to the memo. The function signature of a reducer is (s,v)->s, that means it always returns one thing.
      • defen 12y ago
        > A reducer might not add the current value to the memo (filter) but it always returns some memo for the next step. I think the idea is that your reducer function shouldn't have to care about steps or memos. e.g. I should be able to do filter(function(x) { return x < 10; }); and get back some thing that I can then pass in to map, or to reduce, or compose with other things.
        • ww520 12y ago
          Hmm, isn't that just the filter predicate function? Not the reducer itself? Looks like the filter() function constructs a reducer using the predicate. The new reducer adds the filtering functionality with the predicate. Looking at the code for filter (copied from above) filter: ([pred] (fn [f1] <-- builds the new reducer; f1 is the inner reducer (fn <-- this is the new outer reducer ([result input] <-- outer's params: result is memo; input is value (if (pred input) <-- pred is user provided, your function (f1 result input) <-- calls the inner reducer; returns its result. result))))) <-- call filtered, returns result unchanged. The reducer still behaves as reducer, returning one result. A Javascript version would be: function filterTransducer(innerReducer, pred) { return function(memo, value) { if (pred(value)) return innerReducer(memo, value) return memo; } }