In Haskell one can write seemingly sub-optimal code like
take 5 $ map (+ 1) $ map (* 10) [1 .. 100]
and generally trust that this won't produce two list traversals under the hood. Due to fusion, this might actually compile to something like
map ((+ 1) . (* 10)) [1 .. 5]
where all the constituent functions are composed against one another prior to iteration, ensuring a single traversal—and not a complete one at that; only five iterations will take place.
We have laziness to thank as usual, but we're only a couple of lambdas away from implementing this in other languages.
When I first encountered the term "transducer," I assumed it was another word for "iterator." Both are composable nodes in a data-processing stream, but iterators are "pulled from" and allocate small internal buffers of inbetween state. I've never been that interested in them, so I can't comment further. Transducers, on the other hand, map very cleanly to the notion of fusion. They exist as pure step functions that don't allocate anything until the entire transformation pipeline runs and yields its final output. A given transducer might be defined as follows
(define-syntax λ (syntax-rules () ((_ . ω) (lambda . ω))))
(define (transducer f) (λ (reduce) (λ (acc ω) (reduce acc (f ω)))))
where
f is a unary transformation function that one might map with, like (+ 1).reduce is a dyadic reducer function that one might fold with, like + or append.(acc ω) is the usual internals one might expect in a fold, with acc representing all the previous accumulated values, and ω being the current value under transformation.The nested lambdas look a bit messy, so it'd help to partially apply things.
(define (string-length-transducer) (transduce string-length))
This will eventually apply string-length to every stream item it encounters, but it requires a dyadic reduce function to tell it how exactly to combine its transformed output with previous values.
(λ (reduce) (λ (acc ω) (reduce acc (string-length ω))))
Applying a dyadic function will simplify things further.
(string-length-transducer +)
becomes
(λ (acc ω) (+ acc (string-length ω)))
This is looking very familiar—like a suspended step in a fold. You can actually plug in an accumulator and a value to run it now.
((string-length-transducer +) 0 "aaa")
3
((string-length-transducer +) 5 "aaa")
8
There is only one other function needed to run this against a full sequence.
There is one other cool Haskellism at play; transducers are agnostic across data structures. Much like how one can exploit the Foldable typeclass to reduce a list, a tree, or whatever, you can choose what specific traversal function and datasource you wish to run your pipeline against. No type magick required here. Just inject more functions.
(define (transduce traversal pipeline reduce acc ωs)
(traversal (pipeline reduce) acc ωs))
where
traversal is the driving function across the datastructure: foldl for lists, read-lines for files, etc.pipeline is the transducer(s) that will manipulate the stream.reduce is the aforementioned dyadic reduction function over a given step.acc is the starting value.ωs is the datastructure: a list, a port, whatever.Kind of abstract, but the genius will reveal itself.
If one wanted the total length of all strings in a literal list, he or she would plug in foldl with +.
(transduce foldl string-length-transducer + 0 (list "aaa" "bb" "c"))
6
But if the individual string lengths were desired, it'd be simple to reduce with conj instead.
(transduce foldl string-length-transducer (λ (acc ω) `(,@acc ,ω)) '() (list "aaa" "bb" "c"))
(3 2 1)
And if it weren't a list at all, but a shell command ls over the current directory?
(define (cmd→stream ω)
(let ((port (open-input-pipe ω)))
(λ () (let ((α (read-line port)))
(if (eof-object? α) (begin (close-input-pipe port) α) α)))))
(define (fold-stream f acc ωs)
(let ((ω (ωs))) (if (eof-object? ω) acc (fold-stream f (f acc ω) ωs))))
(transduce fold-stream string-length-transducer (lambda (acc x) `(,@acc ,x)) '() (cmd→stream "ls"))
(8 10 10 16 2 14 15 14 8 6 9 3 6)
The input and output datastructures remain entirely generic, allowing you to focus on the transformation pipeline itself, but it's not much of a pipeline, seeing how it's one string-length function.
When you define (transducer f), its immediate output lambda is unary: awaiting reduce as its next argument.
(λ (reduce) (λ (acc ω) (reduce acc (f ω))))
A chain of unary functions can be composed, of course. It's everywhere in Haskell, and Chicken has it built in too.
(define ∘ compose)
(define increment-transducer (transducer (λ (n) (+ n 1))))
(define pipeline (∘ string-length-transducer increment-transducer increment-transducer))
In composing the unary increment-transducer against the unary string-length-transducer, the reduce value of string-length-transducer becomes increment-transducer itself! Their valences check out, so why not? You're left with a solitary lambda, still awaiting its ultimate reduce function, that will apply all the other transducers before reifying the output. The composition is the pipeline.
(transduce foldl pipeline (λ (acc ω) `(,@acc ,ω)) '() (list "aaa" "bb" "c"))
(5 4 3)
This applies increment twice, as expected. The whole thing is just one big function that runs exactly three times: once for each list element, just like Haskell.
Transducer pipelines are curious. Despite being right-to-left function compositions, they apply their transformations left-to-right. This makes sense if you follow the composition in its expected order. The body of the first increment becomes the reduce of the next increment, which becomes the reduce of string-length. When presented with its first input, string-length performs its f before calling reduce on the output, which in turn calls its f and its reduce—all backwards up the composition chain.
I believe this is known as contravariance. I see it here and there in functional programming, but I'm doomed to forget it as soon as I grasp it. If a normal covariant Functor "maps a function into a structure, changing what output it contains", then a contravariant Functor "maps a function backwards, changing what input the structure expects."
The processing order reminded me of lenses—also evaluated right-to-left, also composed. I'm left wondering if a Profunctor is somehow encoded in this reduction operation, however curried. I don't have the heart to work out dimap here.
"I wonder" is the extent of my rigor for now. Still, it's nice to have a practical example of contravariance.
Two functions gets you fusion and generics. Not bad, but practical transducers are likely more complicated. Think about filtering, or chunking operations like the take that began this article. Some statefulness and "buffer flushing" will inevitably enter the picture. I'm working on that now, but this article is already messy enough.