4 ms·
I believe there are two fundamental differences between transducers and LINQ/IEnumerable. First, IEnumerable only abstracts "where" input is demanded from, but
by phaedrus 9y ago
I believe there are two fundamental differences between transducers and LINQ/IEnumerable. First, IEnumerable only abstracts "where" input is demanded from, but it doesn't abstract "when" or "who" initiates it. For example, consider the difficulty of producing one LINQ expression which can be used either in "pull mode" (ask the expression as a whole for items) or "push mode" (tell the expression to react to an item of a specific input stream). Or consider the difficulty of writing a LINQ primitive "Zip(a,b)" that is flexible with respect to the details of its usage may actually require all of "a" be read+cached before combining with "b", or perhaps where "a" and "b" are actually the same stream, or else they're independent and you really can just read each one alternating. Now imagine doing so without knowing in advance which case it will be and without using if-statements or some other kind of dispatching based on situation.
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.