Transducers are coming to Clojure

Post by tel » Thu, Aug 07, 2014, 12:04 AM UTC

richhickey wrote: post #28

tel wrote: post #13

This sort of reminds me of the Church-encoded form of a list. newtype Fold a = Fold (forall r . (a -> r -> r) -> r -> r) fold :: [a] -> Fold a fold xs = Fold (spin xs) where spin [] cons nil = nil spin (a:as) cons nil = cons a (spin as cons nil) refold :: Fold a -> [a] refold (Fold f) = f (:) [] Notably, since `fold` and `refold` are isomorphisms then we can do everything we can do to `[a]` to `Fold a` map :: (a -> b…

Kind of. The idea is to get out of the context of the 'whole job' (the ->r->r bit above) and focus on transformations of the step function (a->r->r) -> (b->r->r) {using your arg order above}. Not talking about the whole job (i.e. the source and result) makes for much more highly reusable components, especially when the jobs don't produce concrete results but, e.g., run indefinitely, like channel transformations.

Post by avernet » Thu, Aug 07, 2014, 12:13 AM UTC

richhickey wrote: post #19

avernet wrote: post #14

Earlier quoted context omitted.

Providing the signature of this new `map` function (e.g. as in Haskell's fmal http://www.haskell.org/hoogle/?hoogle=fmap ), would certainly go a long way towards helping people understand what this `map` does.

These sigs are for the arities below only. map f: (a->b)->(x->b->x)->(x->a->x) filter pred: (a->bool)->(x->a->x)->(x->a->x) flatmap f: (a->[b])->(x->b->x)->(x->a->x) etc.

    type Reducer[X, A] = (X, A) ⇒ X

    def map[X, A, B](f: A ⇒ B): (Reducer[X, B] ⇒ Reducer[X, A]) =
        (redB: Reducer[X, B]) ⇒ (x: X, a: A) ⇒ redB(x, f(a))

    def addup(zero: Int, a: List[Int]) = a.foldLeft(zero)(_ + _)
    def parseList(a: List[String]) = a.map(_.toInt)

    map(parseList)(addup)(1, List("7", "8"))

Post by spion » Thu, Aug 07, 2014, 12:22 AM UTC

dopamean wrote: post #55

vbit wrote: post #45

I'm not quite sure what this means, so here's my attempt to translate this into Python. A reducer is a function such as `add`: def add(sum, num): return sum + num Of course you can plug `add` directly in `reduce(add, [1, 2, 3], 0)` which gives `6`. A transducer is an object returned by a call such as `map(lambda x: x + 1)`. You can now apply the transducer to a reducer and get another reducer. map_inc = map(lambda x:…

I'm also hoping for an informative answer to this question. Anyone?

Post by richhickey » Thu, Aug 07, 2014, 12:35 AM UTC

spion wrote: post #56

dopamean wrote: post #55

Earlier quoted context omitted.

I'm also hoping for an informative answer to this question. Anyone?

I think its just reduce, but in general its possible to write many implementations of reduce. It could be applied to lazy sequences, observables (to get a future or a new observable) and many other reducible things

Post by ww520 » Thu, Aug 07, 2014, 12:49 AM UTC

graycat wrote: post #38

ww520 wrote: post #18

Earlier quoted context omitted.

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 r…

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…

    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

    function fancyTransducer(originalReducer, valueEnhancer, memoEnhancer) {
        return function(memo, value) {
            return memoEnhancer(originalReducer(memo, valueEnhancer(value)));
        }
    }