4 ms·
It's not a formal notation. It's talking about a pattern in function signature. The function takes in some parameters (whatever, input) and spits out an outpu
by ww520 12y ago
It's not a formal notation. It's talking about a pattern in function signature. The function takes in some parameters (whatever, input) and spits out an output ( -> whatever ).
The "reducing function signature" basically is just the function signature of a "reducer" (or "fold") function in the map/reduce (or map/fold) pattern.
The "whatever" is kind of sloppy and confusing. It's the accumulating memo parameter of a reducer function. To be precise, the reduce(list, reducer, init_value)->list function takes in another function - the reducer, which has the function signature of reducer(current_element, accumulating_memo)->new_memo to run against each element of the list.
The "transducer" is basically a function to take in a reducer and spit out another reducer.
e.g. you have a reducer to sum up all the elements of a list. A doubling transducer would take that reducer and produces another one that doubles each element before summing them up.
- graycat 12y agoThanks. 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 code, and there I have some data base data split, for some positive integer n, into n 'partitions'. The intention, later, is to use n servers, one server for one partition. Then I have some data X to be 'applied' to all the data in all the partitions, and from each partition I get back some data, say, for partition i = 1, 2, ..., n, from partition i I get back data Y(i). Then I combine all the data Y(i) to get my final results Z that I really want. I've programmed the communications, etc., but it looks like I've just reinvented the wheel, i.e., map/reduce. Looks like a library of good map/reduce software could save me from programming the low level details (serialize to an array of byte an instance of a class and send the array via TCP/IP sockets) and also get some fault tolerance. Sounds good. So, I reinvented the 'pattern'. For the OP, I'm not so clear on how in most compiled languages the 'transducer' could work; that is, it sounds like the programming language would need some means of 'reflection', 'entry variables', 'delegates', dynamically written, compiled, and linked code, interpretative code, or some such. There, 'static analysis' of 'dynamic code' seems a bit clumsy!
- ww520 12y agoActually "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 agoActually 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.