4 ms·

I'm sorry, but from the OP I can't be at all sure I can understand notation such as: ;;reducing function signature whatever, input -> whatever or

• richhickey 12y ago
  a la Haskell: ;;reducing fn x->a->x ;;transducer fn (x->a->x)->(x->b->x)
  • mike_ivanov 12y ago
    So there's some common ground between map, filter, flatmap, etc and these transducers allow you to compose those common-ground representations? I mean, you can define `map` as a callable chain of `(key-by #(true)) -> (map-apply fn) -> (filter-trues)` and `filter` as `(key-by predicate) -> (map-apply identity) -> (filter-trues)` where key-by, map-apply and filter-trues are some low-level primitives? Is that correct?
    • richhickey 12y ago
      Precisely the opposite - these functions compose because they are representation-free.
  • zem 12y ago
    or, to steal ashley yakeley's marvellous quip, "every sufficiently well-documented lisp program contains an ML program in its comments" (:
    • xmonkee 12y ago
      lol
  • FranklinChen 12y ago
    More precisely: -- Left reduce type Reducer a r = r -> a -> r -- Here's where then rank-2 type is needed type Transducer a b = forall r . Reducer a r -> Reducer b r
• 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 ago
    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 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 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.