Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Transducers are coming to Clojure

blog.cognitect.com

Post reply on HN
Print view View original

21–30 of 103 posts

Re: Transducers are coming to Clojure

#21

Post by berdario »

Flow wrote: post #17
dustingetz wrote: post #12

Earlier quoted context omitted.

> isolate the logic of map, filter etc from lists or any particular context so Functors (fmap)? fmap still uses regular old fns, no machinery. http://clojuredocs.org/clojure_contrib/clojure.contrib.gener... http://learnyouahaskell.com/making-our-own-types-and-typecla...

I feel that same confusion as you. In Haskell terms, what is it Rich have implemented or perhaps even invented?

I'm not sure I grok this, but I think that the main points are:

- reducers can work on tree structures, and thus can exploit parallelism. This would be like using a map that requires only the Foldable typeclass

- In Haskell you have stream/vector fusion, but it's not obvious to know when ghc will actually exploit it, you might want to use something like Control.Monad.Stream or Data.Vector. In theory it might be generalized to all Foldables, but in practice for now it might be a good enough compromise to stick to a limited number of types (the one that support such transducers)

So: nothing terribly new/groundbreaking, but it might bring something like stream fusion to the masses (of clojure developers :P )

Re: Transducers are coming to Clojure

#22

Post by mike_ivanov »

richhickey wrote: post #16
graycat wrote: post #15

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 ;;transducer signature (whatever, input -> whatever) -> (whatever, input -> whatever) Or, in mathematics there is some notation f: A --> B where A and B are sets and f is a function. This notation means that for each element x in set A, function f returns value f(x) in set…

a la Haskell: ;;reducing fn x->a->x ;;transducer fn (x->a->x)->(x->b->x)

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?

Re: Transducers are coming to Clojure

#23

Post by drcode »

kazinator wrote: post #10
richhickey wrote: post #9

Earlier quoted context omitted.

Your typical definition of map, filter etc includes concrete usage of e.g. lists. These don't. Transducers are not just currying or partial application of the map function over lists, they isolate the logic of map, filter etc from lists or any particular context, allowing them to be used in very different (e.g. non-collection) contexts.

By "map in a non-collection context", what would be an example? Say, mapping a boolean negation function over the bits of an integer, to produce its complement? How does that look with transducers?

Well, the most obvious value to me is that you can create algorithms that defer their action- So instead of having a function that operates on a collection, you can have a function that will operate on a collection at a future date, even if the collection does not yet exist. (that's what the clojure reducer library does)

(And if you say "deferring an action is just another term for 'functions'" then that's exactly the point, lifting more algorithmic logic into composable functions)

Re: Transducers are coming to Clojure

#24

Post by kazinator »

drcode wrote: post #23
kazinator wrote: post #10

Earlier quoted context omitted.

By "map in a non-collection context", what would be an example? Say, mapping a boolean negation function over the bits of an integer, to produce its complement? How does that look with transducers?

Well, the most obvious value to me is that you can create algorithms that defer their action- So instead of having a function that operates on a collection, you can have a function that will operate on a collection at a future date, even if the collection does not yet exist. (that's what the clojure reducer library does) (And if you say "deferring an action is just another term for 'functions'" then that's exactly th…

Alan Perlis Epigram #2.

Re: Transducers are coming to Clojure

#25

Post by swannodette »

berdario wrote: post #21
Flow wrote: post #17

Earlier quoted context omitted.

I feel that same confusion as you. In Haskell terms, what is it Rich have implemented or perhaps even invented?

I'm not sure I grok this, but I think that the main points are: - reducers can work on tree structures, and thus can exploit parallelism. This would be like using a map that requires only the Foldable typeclass - In Haskell you have stream/vector fusion, but it's not obvious to know when ghc will actually exploit it, you might want to use something like Control.Monad.Stream or Data.Vector. In theory it might be gener…

Comparing transducers to stream fusion is far narrower than the scope of their applicability.

Re: Transducers are coming to Clojure

#26

Post by richhickey »

mike_ivanov wrote: post #22
richhickey wrote: post #16

Earlier quoted context omitted.

a la Haskell: ;;reducing fn x->a->x ;;transducer fn (x->a->x)->(x->b->x)

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?

Precisely the opposite - these functions compose because they are representation-free.

Re: Transducers are coming to Clojure

#27

Post by swannodette »

unlogic wrote: post #20

This looks exciting, but I'm confused about the decision to add extra arity to collection-manipulating functions. "filter" that returns a collection or a transducer depending only on arity seems a little counter-intuitive.

It's a pretty well considered tradeoff in my opinion - no existing code breaks while at the same time all the transformation functions now have the same semantic interpretation when used in different contexts. The alternative would be to replicate the notion of `map`, `filter`, etc. again and again as occurred with reducers and higher level core.async operations on channels.

Re: Transducers are coming to Clojure

#28

Post by richhickey »

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.

Re: Transducers are coming to Clojure

#29

Post by unlogic »

swannodette wrote: post #27
unlogic wrote: post #20

This looks exciting, but I'm confused about the decision to add extra arity to collection-manipulating functions. "filter" that returns a collection or a transducer depending only on arity seems a little counter-intuitive.

It's a pretty well considered tradeoff in my opinion - no existing code breaks while at the same time all the transformation functions now have the same semantic interpretation when used in different contexts. The alternative would be to replicate the notion of `map`, `filter`, etc. again and again as occurred with reducers and higher level core.async operations on channels.

My argument is why not making it look like:

(comp (transducer map inc) (transducer filter even?))

Of course, it's more typing and doesn't look as nice as single-arity map, but it goes along quite well with (partial map inc).

I can be wrong but to this date Clojure didn't have a function that produces completely different things based on arity, did it?

Re: Transducers are coming to Clojure

#30

Post by taliesinb »

swannodette wrote: post #27
unlogic wrote: post #20

This looks exciting, but I'm confused about the decision to add extra arity to collection-manipulating functions. "filter" that returns a collection or a transducer depending only on arity seems a little counter-intuitive.

It's a pretty well considered tradeoff in my opinion - no existing code breaks while at the same time all the transformation functions now have the same semantic interpretation when used in different contexts. The alternative would be to replicate the notion of `map`, `filter`, etc. again and again as occurred with reducers and higher level core.async operations on channels.

We just did exactly the same thing in the Wolfram Language, for similar reasons (we called these things "operator forms" rather than "transducers") [0]

One major side effect has been to mitigate the kinds of heavy nesting you see in functional languages like WL and Clojure. Personally I think the resulting code resembles the phrase structure of English much more closely. It's a huge readability win.

The original motivations for operator forms were in fact writing Queries [1] against Datasets [2], for which you want to represent complex operations independent of their execution.

[0] http://reference.wolfram.com/language/guide/FunctionComposit...

[1] http://reference.wolfram.com/language/ref/Query.html

[2] http://reference.wolfram.com/language/ref/Dataset.html

Post reply on HN