Clojure Transducers

A co-worker pointed me to an article about Clojure and transducers:

He wasn't sure what the purpose was, as the explanations have all been quite technical. Here's my attempt at an explanation.

Disclaimer: I don't know clojure, but I know haskell fairly well and read those articles on transducers and think I understand them. To start, you need to understand common higher order functions like map or filter. Map takes a transform function as an argument and a list as an argument, applies the transform function to each item in the list, and returns the results accumulated into a list. Filter takes a predicate function and a list, and returns a new list consisting only of items for which the predicate function returned true. There are many other common high level functions; learning haskell will expose you to them, and you will eventually realize that in most cases the "for" loops you write in procedural code are just verbosely reimplementing these higher order functions over and over again. Note that I just defined map and filter on a list container, but you could implement them (and other common higher order functions) for other types of containers as well: for example a tree structure. Going further, you could generalize the concept of map and filter even more so that these functions could be applied to any type of container, which is done by making up a sort of interface function that you'd need to implement for each type, and then the generic map/filter would work on it. There are various approaches to this, and he's calling his "transducers".

The concepts he's laid out start with a class of function he's calling a reducer, which is just a function that takes a container plus an item to add to the container, and returns the new container. You can imagine writing a simple reducer that just takes a new item and an existing list and adds the item to the end of the list. You could write other basic reducers for other containers. This is his interface function that allows generalization of map/filter/etc across multiple types of containers. The class of functions he's calling transducers are the generalized map/filter/etc and take a reducer function as input (plus usually other inputs) and return a new reducer function. So in place of a list or other container in a normal map/filter/etc argument list is a reducer function. His generic map function is a "transducer" that takes a transform function as an argument and a reducer as an argument. His generic map outputs a reducer function that applies the transform function before passing piping the result to the input reducer function. That is, the resulting output reducer function will automatically transform input items before adding to its container. His generic filter function is a transducer that takes a predicate function as an argument and a reducer as an argument. It outputs a reducer function that tests an input against the predicate and, if it passes, pipes the input through the reducer (thus adding the item to the container), otherwise is a no-op reducer (leaves the container unmodified).

So instead of operating directly on containers like other generalizations of map/filter/etc, the transducer concept operates on functions that modify the containers. It's another step removed, essentially acting as a way to defer the actions on the containers while still encapsulating the operation you're performing. In practice, you also need to define a function to actually execute all the reducers. For a simple list, this probably means starting with an empty list and then applying each reducer in order. However, it could be whatever you want. This makes the transducer approach useful versus traditional generalizations because traditional map/filter/etc still imply some ordering of operations on the container. He's interested in asynchronous operations, which may require operations on the container in some other ordering. Traditional generalizations abstract away the high level function from the container. With transducers, you also abstract the application of operations from the high level function.

Comments are closed.

Dev Journal and Project Hosting