Clojure transducers from the ground up: using them in practice
labs.uswitch.com
labs.uswitch.com
[1] http://dx.doi.org/10.1145/3062341.3062362
When you initialize any transducer it works on all transducer accepting data types. Making a new data type accept transducers is trivially easy and once you do it once, your data type has access to all transducers. Transducers are orthogonally composable to all other transducers so stringing several up and taking them apart is also trivially easy. Transducers do not create intermediate collections during the process.
I believe none of these are particularly anything new. Possibly the orthogonality is something new as you don't find composability quite like Clojure in many other languages as it's at the heart of the language design philosophy.
IEnumerable is more analogous to Clojure's seq abstraction. Transducers have less overhead and are more flexible.
If I understand transducers right (which I may not) I believe that they allow writing code that is agnostic of such details, in a way which LINQ/IEnumerable do not.
The second difference is that transducers make the concept of a fold (collapsing many values into one value) an inherent part of the design, as opposed to LINQ which treats such operations as extension methods built on top of IEnumerable, i.e. as things you do to an IEnumerable rather than being a feature of IEnumerable. E.g. .Aggregate(), .First(), etc.
IMO that's an area LINQ gets wrong, as it makes it awkward to deal with single-item cases; you have to choose between enumerations with one item, or extracting the item. Besides the fact that that could fail if the sequence is empty, it also means that LINQ is not algebraically closed under all of it operations.
The two issues combined lead to certain ways that LINQ, much as I like it, is not always as good as it could be. For instance recently I had a problem of matching controls on a windows dialog up to a list of expected controls from a database, with a fuzzy match of +/- 2 pixels on each rectangle side, and produce four lists: 1-1 matches, ambiguous matches, missing left, missing right. I can express very clearly what I want, declaratively (in fact, I just did - in an ideal object query language that sentence would have almost a direct translation).
However as a LINQ query it gets very messy. Since it's a fuzzy match, I can't simply equi-join the two lists. (Note that the match predicate is not transitive; |A-B|<=2 and |B-C|<=2 does not imply |A-C|<=2.) Since there's 4 dimensions being compared, I can't use just a single sort. On the other hand if the distance in any one dimension is greater than 2, there's no point in comparing the other 3. But I don't want to do N^2 comparisons, either.
So I go with a solution which produces candidate matches on each dimension and joins the two lists. Since LINQ only supports equijoin, and I don't feel like writing an sort-intersect primitive, I just lazily generate all five integers +/-2 of the real value. At least it is 5+5+5+5 rather than 5 * 5 * 5 * 5, because the dimensions are joined on separately not as a tuple. Then I do a group-by using the object itself as the group key, and discard groups which don't match at least once in all four dimensions. I have to do extra work after that to discover ambiguous and missing matches. Maybe not the best way, but the best compromise I could come up with between optimality, readability, and development time.
But notice how many non-essential details I had to think about! The core task that my LINQ expression is doing is only a small part of all the expanding, joining, grouping, and extracting that I had to do. Even if I couldn't just hand the problem off and let the computer figure out to do all this (which I would like to be able to do), just being able to separate the essential and accidental parts of this query would be helpful.
True, I got in the situation because I didn't want to accept the O(N^2) brute force option doing a filter on the cross product. However note that LINQ also didn't do anything for insulating my essential query code from the strategy used to collate the data; instead it mixes them together. I'm still learning about transducers, but my hope is that they will someday allow better separation of concerns than LINQ/IEnumerable by itself.
https://gist.github.com/tomwhoiscontrary/e41d52e9c98a706552b...
?
I've done that in terms of Consumer, but it might also be possible, and perhaps more elegant, in terms of flat-mapping functions (Function<T, Stream<T>>).
If i've understood right, then from a Java point of view, transducers are an attempt to reify the various operations on streams - mapping, filtering, etc. To do that, you have to figure out a type which is general enough to model all those operations.
The need for a general type is where you get the perilously-close-to-general-abstract-nonsense "a transducer is a transformation from one reducing function to another". Here, "a reducing function" is what stands in, in a very oblique way, for the stream - it's ultimately a conduit for values, and transducers take some existing conduit, wrap another layer of processing round it, and give you the resulting conduit. So they're a bit like backward streams, i suppose. If anything, it's like how you go around wrapping up layers of OutputStreams when doing IO:
new PrintStream(new BufferedOutputStream(new GZIPOutputStream(new CipherOutputStream(new FileOutputStream("file.dat"), cipher))));
Relabeling it "Clojure transducers" would help the title in every way. But it's been up for 7 hours now, so we'll see if it changes.