Clojure's Transducers are as fundamental as function composition
thecomputersarewinning.com
Clojure's Transducers are as fundamental as function composition
1–10 of 49 posts
Re: Clojure's Transducers are as fundamental as function composition
#2If you ignore the arities, ignore the internal state, and correctly observe the unwritten rules, yes transducers act like function composition. I looked into this here: http://www.colourcoding.net/blog/archive/2014/08/16/lets-wri...
I think Rich's innovation here is extremely clever and quite subtle, but it's pretty Clojure-specific, both in terms of the problem it solves and the way it solves it.
Re: Clojure's Transducers are as fundamental as function composition
#3If you ignore the arities, ignore the internal state, and correctly observe the unwritten rules, yes transducers act like function composition. I looked into this here: http://www.colourcoding.net/blog/archive/2014/08/16/lets-wri... I think Rich's innovation here is extremely clever and quite subtle, but it's pretty Clojure-specific, both in terms of the problem it solves and the way it solves it.
The overall pattern of map-reduce is possible in most languages, certainly any language that has closures. And the idea of composing multiple reducing functions together is something that comes up in many languages. If a language does not have closures, you could do something similar in any language by walking an accumulating object through multiple loops, but that is awkward and ugly. But you could certainly do something like this in Javascript, through the clever use of multiple closures, composing the closures together. But transducers formalize this as an idiomatic part of Clojure.
Re: Clojure's Transducers are as fundamental as function composition
#4If you ignore the arities, ignore the internal state, and correctly observe the unwritten rules, yes transducers act like function composition. I looked into this here: http://www.colourcoding.net/blog/archive/2014/08/16/lets-wri... I think Rich's innovation here is extremely clever and quite subtle, but it's pretty Clojure-specific, both in terms of the problem it solves and the way it solves it.
The overall pattern of map-reduce is possible in most languages, certainly any language that has closures. And the idea of composing multiple reducing functions together is something that comes up in many languages. If a language does not have closures, you could do something similar in any language by walking an accumulating object through multiple loops, but that is awkward and ugly. But you could certainly do some…
In languages with more leeway on execution order, this problem can be made to go away. For example, Haskell's stream fusion combines back-to-back calls to list processing functions into a single iteration over the list.
Re: Clojure's Transducers are as fundamental as function composition
#5What does "as fundamental as function composition" mean here? The article just appears to describe transducers. Transducers compose via ("reverse") function composition, sure, but that just means that they are functions of a type... and considerably less fundamental than functions since they're a specialization of that class of things.
They're cool and all—I've characterized them (partially, perhaps) as CPS encoded flatmaps over lists and also as stateful left fold transformers, the latter of which being much more general—but they're more like a rich ecosystem for list transformations than any kind of fundamental abstraction.
Re: Clojure's Transducers are as fundamental as function composition
#6Earlier quoted context omitted.
The overall pattern of map-reduce is possible in most languages, certainly any language that has closures. And the idea of composing multiple reducing functions together is something that comes up in many languages. If a language does not have closures, you could do something similar in any language by walking an accumulating object through multiple loops, but that is awkward and ugly. But you could certainly do some…
In languages with more leeway on execution order, this problem can be made to go away. For example, Haskell's stream fusion combines back-to-back calls to list processing functions into a single iteration over the list.
Lazy evaluation can also be encoded fairly easily in strict languages using constructs like lazy stream abstractions.
Re: Clojure's Transducers are as fundamental as function composition
#7If you ignore the arities, ignore the internal state, and correctly observe the unwritten rules, yes transducers act like function composition. I looked into this here: http://www.colourcoding.net/blog/archive/2014/08/16/lets-wri... I think Rich's innovation here is extremely clever and quite subtle, but it's pretty Clojure-specific, both in terms of the problem it solves and the way it solves it.
What's clever is recognizing the "kernel" of a function like map. Hickey answers the question: if we take this list-processing/decimating function like "count-if" or "map" or whatever, and express it with reduce, what is that reducer function which we will need? And how is that reducer derived from or related to the function that goes into the list processing function, like the mapping function in map? He then makes those functions behave as methods (when called with one less argument) which give you that reducer.
Now what if this is done to reduce itself? What should a reduced arity (reduce fun) return? I think that is a noop: nothing needs to be done to fun to make it reduce under reduce, so (reduce fun) -> fun. I.e. to transduce the reducer "fun", an arbitrary function, into a function X such that (reduce X list) will do the job of (reduce fun list), we simply equate X with fun.
Re: Clojure's Transducers are as fundamental as function composition
#8What does "as fundamental as function composition" mean here? The article just appears to describe transducers. Transducers compose via ("reverse") function composition, sure, but that just means that they are functions of a type... and considerably less fundamental than functions since they're a specialization of that class of things. They're cool and all—I've characterized them (partially, perhaps) as CPS encoded f…
I think "as fundamental as function composition" means that the relationship between a function like map and a transducer (map f) is fundamental in some sense that resembles function composition. But it isn't composition: it's something that "wrangles" the "reduce kernel" out of the combination of map and f: when we map something using f, what function instead of f will do the same mapping under reduce? That function inherits logic from map, and from f, but it's not a composition of the two.
Re: Clojure's Transducers are as fundamental as function composition
#9What does "as fundamental as function composition" mean here? The article just appears to describe transducers. Transducers compose via ("reverse") function composition, sure, but that just means that they are functions of a type... and considerably less fundamental than functions since they're a specialization of that class of things. They're cool and all—I've characterized them (partially, perhaps) as CPS encoded f…
This is typical of Closure, as a sort of anti-Haskell. It starts with empirical structures invented by folks without PL theory training, and then wriggles to find an explanation in terms of standard theory. You can see this here on HN when Rich talks to Haskell folks and people translate his writing into standard language.
I would love a comparison in the form of Haskell, converted to Lisp syntax, and wired up to JVM.
Re: Clojure's Transducers are as fundamental as function composition
#10What does "as fundamental as function composition" mean here? The article just appears to describe transducers. Transducers compose via ("reverse") function composition, sure, but that just means that they are functions of a type... and considerably less fundamental than functions since they're a specialization of that class of things. They're cool and all—I've characterized them (partially, perhaps) as CPS encoded f…
I think "as fundamental as function composition" means that the relationship between a function like map and a transducer (map f) is fundamental in some sense that resembles function composition. But it isn't composition: it's something that "wrangles" the "reduce kernel" out of the combination of map and f: when we map something using f, what function instead of f will do the same mapping under reduce? That function…
I think what the author ultimately means is "well behaved transducers are equivalent to functions of the form a->[b] (modulo state) and therefore form a category".
True story: the transducer announcement has mostly made me read up on the Haskell fold and lens libraries...