I think Transducers are a fundamental primitive that decouples critical logic from list/sequence processing, and if I had to do Clojure all over I would put them at the bottom.
– Rich Hickey
Transducers are an ergonomic and extremely memory-efficient way to process a data source. Here “data source” means simple collections like Lists or Vectors, but also potentially large files or generators of infinite data.
Transducers…
- allow the chaining of operations like
mapandfilterwithout allocating memory between each step. - aren’t tied to any specific data type; they need only be implemented once.
- vastly simplify “data transformation code”.
- have nothing to do with “lazy evaluation”.
- are a joy to use!
Example: While skipping every second line of a file, sum the lengths of only evenly-lengthed lines.
(t-transduce
;; How do we want to process each element?
(t-comp (t-step 2) (t-map #'length) (t-filter #'cl-evenp))
;; How do we want to combine all the elements together?
#'+
;; What's our original data source?
(t-file-read "README.org"))11888
Looking for Transducers in other Lisps? Check out the Common Lisp and Fennel implementations!
Originally invented in Clojure and later adapted to other Lisps, Transducers are an excellent way to think about - and efficiently operate on - collections or streams of data. Transduction operations are strict and don’t involve “laziness” or “thunking” in any way, yet only process the exact amount of data you ask them to.
This library is mostly a port of the Common Lisp implementation, with a few alterations to account for the minor differences between Common Lisp and Emacs Lisp.
This package is available on MELPA.
Since this is just a library, you can import it as usual:
(require 'transducers)Every function in the library is prefixed by transducers- but you’re encouraged
to use read-symbol-shorthands to shorten this to t-. This can be done
interactively in your own files via add-file-local-variable, which you
can use to set this at the bottom of your file:
;; Local Variables:
;; read-symbol-shorthands: (("t-" . "transducers-"))
;; End:After this, you can make relatively clean calls like:
(t-transduce (t-map #'1+) #'t-vector '(1 2 3))[2 3 4]
This can also be done in .org files, so that Transducers can be used in their
short forms even in Babel source blocks. That’s exactly what this README does!
The remaining examples below use t- for brevity.
;; The fundamental pattern.
(t-transduce <transducer-chain> <reducer> <source>)Data processing largely has three concerns:
- Where is my data coming from? (sources)
- What do I want to do to each element? (transducers)
- How do I want to collect the results? (reducers)
Each full “transduction” requires all three. We pass one of each to the
t-transduce function, which drives the process. It knows how to pull values from
the source, feed them through the transducer chain, and wrap everything together
via the reducer.
- Typical transducers are
t-map,t-filter, andt-take. - Typical reducers are
+,t-count,t-cons, andt-fold. - Typical sources are lists, vectors, strings, hash tables, and files.
Generators are a special kind of source that yield infinite data. Typical
generators are t-repeat, t-cycle, and t-ints.
Let’s sum the squares of the first 1000 odd integers:
(t-transduce
(t-comp (t-filter #'cl-oddp) ;; (2) Keep only odd numbers.
(t-take 1000) ;; (3) Keep the first 1000 filtered odds.
(t-map (lambda (n) (* n n)))) ;; (4) Square those 1000.
#'+ ;; (5) Reducer: Add up all the squares.
(t-ints 1)) ;; (1) Source: Generate all positive integers.1333333000
Two things of note here:
t-compis used here to chain together different transducer steps. Notice that the order appears “backwards” from usual function composition. It may help to imagine thatt-compis acting like thethread-lastmacro here.- The reduction via
+is listed as Step 5, but really it’s occuring throughout the transduction process. Each value that makes it through the composed transducer chain is immediately added to an internal accumulator.
Explore the other transducers and reducers to see what’s possible! You’ll never
write a loop again.
The examples here use show each symbol prefixed by t-, but recall that you’ll
need to set an explicit shorthand for this to work. When searching in-editor
documentation, each symbol is prefixed fully by transducers-.
Transducers describe how to alter the items of some stream of values. Some
transducers, like t-take, can short-circuit.
Multiple transducer functions can be chained together with t-comp.
Just pass along each value of the transduction.
(t-transduce #'t-pass #'t-cons '(1 2 3))(1 2 3)
Apply a function F to all elements of the transduction.
(t-transduce (t-map #'1+) #'t-cons '(1 2 3))(2 3 4)
Only keep elements from the transduction that satisfy PRED.
(t-transduce (t-filter #'cl-evenp) #'t-cons '(1 2 3 4 5))(2 4)
Apply a function F to the elements of the transduction, but only keep results that are non-nil.
(t-transduce (t-filter-map #'cl-first) #'t-cons '(() (2 3) () (5 6) () (8 9)))(2 5 8)
Only allow values to pass through the transduction once each. Stateful; this uses a hash table internally so could get quite heavy if you’re not careful.
(t-transduce #'t-unique #'t-cons '(1 2 1 3 2 1 2 "abc"))(1 2 3 "abc")
Remove adjacent duplicates from the transduction.
(t-transduce #'t-dedup #'t-cons '(1 1 1 2 2 2 3 3 3 4 3 3))(1 2 3 4 3)
Drop the first N elements of the transduction.
(t-transduce (t-drop 3) #'t-cons '(1 2 3 4 5))(4 5)
Drop elements from the front of the transduction that satisfy PRED.
(t-transduce (t-drop-while #'cl-evenp) #'t-cons '(2 4 6 7 8 9))(7 8 9)
Keep only the first N elements of the transduction.
(t-transduce (t-take 3) #'t-cons '(1 2 3 4 5))(1 2 3)
Keep only elements which satisfy a given PRED, and stop the transduction as soon as any element fails the test.
(t-transduce (t-take-while #'cl-evenp) #'t-cons '(2 4 6 8 9 2))(2 4 6 8)
Split up a transduction of cons cells.
(t-transduce #'t-uncons #'t-cons '((:a . 1) (:b . 2) (:c . 3)))(:a 1 :b 2 :c 3)
Concatenate all the sublists, subvectors, or substrings in the transduction.
(t-transduce #'t-concatenate #'t-cons '((1 2 3) [4 5 6] (7 8 9)))(1 2 3 4 5 6 7 8 9)
(t-transduce (t-comp #'t-concatenate (t-intersperse ?!))
#'t-string '("hello" "there"))"h!e!l!l!o!t!h!e!r!e"
Entirely flatten all lists/arrays/strings in the transduction, regardless of nesting.
(t-transduce #'t-flatten #'t-cons '((1 2 3) 0 (4 (5) 6) 0 (7 [8] 9) 0))(1 2 3 0 4 5 6 0 7 8 9 0)
Partition the input into lists of N items. If the input stops, flush any accumulated state, which may be shorter than N.
(t-transduce (t-segment 3) #'t-cons '(1 2 3 4 5))((1 2 3) (4 5))
Yield N-length windows of overlapping values. This is different from segment
which yields non-overlapping windows. If there were fewer items in the input
than N, then this yields nothing.
(t-transduce (t-window 3) #'t-cons '(1 2 3 4 5))((1 2 3) (2 3 4) (3 4 5))
Group the input stream into sublists via some function F. The cutoff criterion is whether the return value of F changes between two consecutive elements of the transduction.
(t-transduce (t-group-by #'cl-evenp) #'t-cons '(2 4 6 7 9 1 2 4 6 3))((2 4 6) (7 9 1) (2 4 6) (3))
Insert an ELEM between each value of the transduction.
(t-transduce (t-intersperse 0) #'t-cons '(1 2 3))(1 0 2 0 3)
Index every value passed through the transduction into a cons pair. Starts at 0.
(t-transduce #'t-enumerate #'t-cons '("a" "b" "c"))((0 . "a") (1 . "b") (2 . "c"))
Only yield every Nth element of the transduction. The first element of the transduction is always included.
(t-transduce (t-step 2) #'t-cons '(1 2 3 4 5 6 7 8 9))(1 3 5 7 9)
Build up successsive values from the results of previous applications of a given function F.
(t-transduce (t-scan #'+ 0) #'t-cons '(1 2 3 4))(0 1 3 6 10)
Inject some ITEM onto the front of the transduction.
(t-transduce (t-comp (t-filter (lambda (n) (> n 10)))
(t-once 'hello)
(t-take 3))
#'t-cons (t-ints 1))(hello 11 12)
Call some LOGGER function for each step of the transduction. The LOGGER must accept the running results and the current element as input. The original items of the transduction are passed through as-is.
(t-transduce (t-log (lambda (_ n) (print! "Got: %d" n))) #'t-cons '(1 2 3 4 5))Got: 1 Got: 2 Got: 3 Got: 4 Got: 5
These are STDOUT results. The actual return value is the result of the reducer,
in this case cons, thus a list.
Interpret the data stream as CSV data.
The first item found is assumed to be the header list, and it will be used to construct useable hashtables for all subsequent items.
Note: This function makes no attempt to convert types from the original parsed strings. If you want numbers, you will need to further parse them yourself.
(t-transduce (t-comp #'t-from-csv
(t-map (lambda (hm) (gethash "Name" hm))))
#'t-cons '("Name,Age" "Alice,35" "Bob,26"))("Alice" "Bob")
Given a sequence of HEADERS, rerender each item in the data stream into a CSV string. It’s assumed that each item in the transduction is a hash table whose keys are strings that match the values found in HEADERS.
(t-transduce (t-comp #'t-from-csv
(t-into-csv '("Name" "Age")))
#'t-cons '("Name,Age,Hair" "Alice,35,Blond" "Bob,26,Black"))("Name,Age" "Alice,35" "Bob,26")
Reducers describe how to fold the stream of items down into a single result, be it either a new collection or a scalar.
Some reducers, like t-first, can also force the entire transduction to
short-circuit.
Collect all results as a list.
(t-transduce #'t-pass #'t-cons '(1 2 3))(1 2 3)
Collect all results as a list, but results are reversed. In theory, slightly
more performant than t-cons since it performs no final reversal.
(t-transduce #'t-pass #'t-snoc '(1 2 3))(3 2 1)
Collect a stream of values into a vector.
(t-transduce #'t-pass #'t-vector '(1 2 3))[1 2 3]
Collect a stream of characters into to a single string.
(t-transduce (t-map #'upcase) #'t-string "hello")"HELLO"
Collect a stream of key-value cons pairs into a hash table.
(t-transduce #'t-enumerate #'t-hash-table '("a" "b" "c"))#s(hash-table size 65 test equal rehash-size 1.5 rehash-threshold 0.8125 data (0 "a" 1 "b" 2 "c"))
Count the number of elements that made it through the transduction.
(t-transduce #'t-pass #'t-count '(1 2 3 4 5))5
Calculate the average value of all numeric elements in a transduction.
(t-transduce #'t-pass #'t-average '(1 2 3 4 5 6))3.5
Calculate the median value of all elements in a transduction, provided that they are numbers, strings, or characters. The elements are sorted once before the median is extracted.
(t-transduce #'t-pass #'t-median '(1 1 1 0 2 4 1 4 9))1
Yield t if any element in the transduction satisfies PRED. Short-circuits the transduction as soon as the condition is met.
(t-transduce #'t-pass (t-anyp #'cl-evenp) '(1 3 5 7 9 2))t
Yield t if all elements of the transduction satisfy PRED. Short-circuits with NIL if any element fails the test.
(t-transduce #'t-pass (t-allp #'cl-oddp) '(1 3 5 7 9))t
Yield the first value of the transduction. As soon as this first value is yielded, the entire transduction stops.
(t-transduce (t-filter #'cl-oddp) #'t-first '(2 4 6 7 10))7
Yield the last value of the transduction.
(t-transduce #'t-pass #'t-last '(2 4 6 7 10))10
Find the first element in the transduction that satisfies a given PRED. Yields NIL if no such element were found.
(t-transduce #'t-pass (t-find #'cl-evenp) '(1 3 5 6 9))6
t-fold is the fundamental reducer. t-fold creates an ad-hoc reducer based on
a given 2-argument function. An optional SEED value can also be given as the
initial accumulator value, which also becomes the return value in case there
were no input left in the transduction.
Functions like + and * are automatically valid reducers, because they yield sane
values even when given 0 or 1 arguments. Other functions like max cannot be used
as-is as reducers since they can’t be called without arguments. For functions
like this, t-fold is appropriate.
(t-transduce #'t-pass (t-fold #'max) '(1 2 3 4 1000 5 6))1000
With a seed:
(t-transduce #'t-pass (t-fold #'max 0) '())0
In Clojure this function is called completing.
Run through every item in a transduction for their side effects. Throws away all results and yields t.
(t-transduce (t-map (lambda (n) (message "%s" n))) #'t-for-each [1 2 3 4])t
Data is pulled in an on-demand fashion from Sources. They can be either finite or infinite in length. A list is an example of a simple Source, but you can also pull from files and endless number generators.
Yield all integers, beginning with START and advancing by an optional STEP value
which can be positive or negative. If you only want a specific range within the
transduction, then use t-take-while within your transducer chain.
(t-transduce (t-take 10) #'t-cons (t-ints 0 :step 2))(0 2 4 6 8 10 12 14 16 18)
Yield an endless stream of random numbers, based on a given LIMIT.
(t-transduce (t-take 20) #'t-cons (t-random 10))(3 9 9 2 2 3 6 3 7 3 3 6 3 6 0 7 5 4 9 5)
(t-transduce (t-take 3) #'t-cons (t-random 1.0))(0.47136199474334717 0.10177326202392578 0.2851991653442383)
Yield the values of a given SEQ endlessly.
(t-transduce (t-take 10) #'t-cons (t-cycle '(1 2 3)))(1 2 3 1 2 3 1 2 3 1)
Endlessly yield a given ITEM.
(t-transduce (t-take 4) #'t-cons (t-repeat 9))(9 9 9 9)
Endlessly yield random elements from a given vector.
(t-transduce (t-take 5) #'t-cons (t-shuffle ["Alice" "Bob" "Dennis"]))("Dennis" "Alice" "Alice" "Dennis" "Alice")
Recall also that strings are vectors too:
(t-transduce (t-take 15) #'t-string (t-shuffle "Númenor"))"rúmnmonNroenmnN"
Yield key-value pairs from a Property List, usually known as a ‘plist’. The pairs are passed as a cons cell.
(t-transduce (t-map #'cdr) #'+ (t-plist '(:a 1 :b 2 :c 3)))6
See also the t-uncons transducer for another way to handle incoming cons cells.
Yield a vector’s elements in reverse order.
(t-transduce (t-take 2) #'t-cons (t-reversed [1 2 3 4]))(4 3)
Recall that strings are also vectors.
(t-transduce #'t-pass #'t-string (t-reversed "Hello"))"olleH"
Function composition. You can pass as many functions as you like and they are applied from right to left.
(funcall (t-comp #'length #'reverse) [1 2 3])3
For transducer functions specifically, they are composed from right to left, but
their effects are applied from left to right. This is due to how the reducer
function is chained through them all internally via t-transduce.
Notice here how t-drop is clearly applied first:
(t-transduce (t-comp (t-drop 3) (t-take 2)) #'t-cons '(1 2 3 4 5 6))(4 5)
Return a function that ignores its argument and returns ITEM instead.
(funcall (t-comp (t-const 108) (lambda (n) (* 2 n)) #'1+) 1)108
When writing your own transducers and reducers, these functions allow you to short-circuit the entire operation.
Here is a simplified definition of t-first:
(defun t-first (&rest vargs)
(pcase vargs
(`(,_ ,input) (t-reduced input))
(`(,acc) acc)
(_ nil)))You can see t-reduced being used to wrap the return value. t-transduce sees this
wrapping and immediately halts further processing.
t-reduced-p and t-reduced-val can similarly be used (mostly within transducer
functions) to check if some lower transducer (or the reducer) has signaled a
short-circuit, and if so potentially perform some clean-up. This is important
for transducers that carry internal state.
(t-transduce (t-comp (t-map #'split-string)
#'t-concatenate)
#'t-count
(t-file-read "README.org"))1101
Transducing over a string yields its characters:
(t-transduce #'t-pass #'t-count "hello\nworld!")12
If you want to transduce over its lines instead, create a temporary buffer first:
(with-temp-buffer
(insert "hello\nworld!")
(t-transduce #'t-pass #'t-cons (current-buffer)))("hello" "world!")
This library also provides two transducers for processing CSV data: t-from-csv
and t-into-csv. The original data can come from any source, like a file, open
buffer, or raw string.
t-from-csv reads the data into a stream of Hash Tables with each value keyed to
the fields provided in the first line. t-into-csv reverses the process, given a
sequence of headers to select.
(t-transduce (t-comp #'t-from-csv
(t-into-csv ["Age" "Name"]))
#'t-cons
["Name,Age,Hair" "Alice,35,Blond" "Bob,26,Black"])("Age,Name" "35,Alice" "26,Bob")
Here we’re immediately converting back into CSV strings, but with t-comp we’re
free to add as many intermediate steps as we like.
It is also possible to read from and write to JSON buffers. Reading assumes that
the buffer contains a top-level array. By default, yielded objects are plists,
but this can be customized via the :object-type keyword.
(with-temp-buffer
(insert "[{\"name\": \"Colin\"},{\"name\": \"Jack\"}]")
(t-transduce #'t-pass #'t-cons (t-from-json-buffer (current-buffer))))((:name "Colin") (:name "Jack"))
Note that t-from-json-buffer is a “source”.
Likewise, t-into-json-buffer is a reducer that writes a stream of lisp values
back into the current buffer.
(with-temp-buffer
(t-transduce #'t-pass #'t-into-json-buffer '((:name "Colin") (:name "Jack")))
(buffer-string))[{"name":"Colin"},{"name":"Jack"}]
Note that t-into-json-buffer makes no assumptions about where point initially is
the current buffer, nor is the buffer automatically saved. Such concerns are the
responsibility of the user.
There is no special reducer function for plists, because none is needed. If you
have a stream of cons cells, you can break it up with t-uncons and then collect
with t-cons as usual:
(t-transduce (t-comp (t-map (lambda (pair) (cons (car pair) (1+ (cdr pair)))))
#'t-uncons)
#'t-cons
(t-plist '(:a 1 :b 2 :c 3)))(:a 2 :b 3 :c 4)
Likewise, Association Lists are already lists-of-cons-cells, so no special treatment is needed:
(t-transduce #'t-pass #'t-cons '((:a . 1) (:b . 2) (:c . 3)))((:a . 1) (:b . 2) (:c . 3))
One of the advantages of the Transducers pattern is that there is no “magic”. As you’ll see below, it’s all just function composition.
A Transducer is a function that continues the stream. It operates on one element at a time. It receives input, optionally does something to it, and then optionally continues by calling the next function in the chain, or it ignores the current input, or it short-circuits the stream entirely. We’ll see examples of all of these below.
Here is how map is implemented in the library. Let’s study it to learn the
overall structure of transducers in general.
(defun t-map (f) ;; (1) Top-level arguments needed throughout.
(lambda (reducer) ;; (2) The rest of the composed function chain.
(lambda (result &rest inputs) ;; (3) The main body of the transducer.
(if inputs
(funcall reducer result (apply f inputs)) ;; (4) The primary logic and a call to the next stage.
(funcall reducer result))))) ;; (5) The finalisation pass.Recall that map would be called like:
(t-transduce (t-map #'1+) #'t-cons '(1 2 3 4 5))(2 3 4 5 6)
So we can see at (1) that the f corresponds to the function we’re passing in,
which we expect to be applied to all elements of the stream.
(2) might be a surprise. What is reducer and where does it come from? Is it the
cons call seen above? Well, it’s actually the transducer chain (possibly
combined via comp), followed by the reducer. Like this:
It is the call to transduce that puts this all together for you.
(3) is what actually gets called during the iteration. Unlike Clojure and Scheme
which can pattern match on the number of arguments directly, or Common Lisp
which at least can use special syntax with &optional, Emacs Lisp has no way to
cleverly detect how many arguments it was passed. So instead we accept them all
as a &rest. If the inputs list is empty, we know the Transduction is over.
(4) should be clear; apply f and then call the reducer the continue the chain.
(5) will become clearer once we’ve learned about the structure of Reducers. For
now, just know that this is the last thing that the top-level t-transduce call
attempts as it is finalising the result.
With t-map fresh in your mind, now stare at this:
(defun t-filter (pred)
(lambda (reducer)
(lambda (result &rest inputs)
(if inputs
;; vvv (4) vvv
(if (apply pred inputs)
(apply reducer result inputs)
result)
;; ^^^ (4) ^^^
(funcall reducer result)))))Point (4) in the previous example was the “meat”, the actual logic of the
transducer. Here we see it expanded a bit. Notice that we only continue the
chain at (4a) if the predicate passed. Otherwise, we yield the result we were
given and directly return, going no further for this particular input element.
Then, t-transduce will supply the next one. The effect is what we’d expect of
t-filter; some elements make it through the stream and some don’t.
Similar to t-filter is t-take-while, except that the latter halts the stream
entirely as soon as an element fails the predicate.
(defun t-take-while (pred)
(lambda (reducer)
(lambda (result &rest inputs)
(if inputs
;; vvv (4) vvv
(if (not (apply pred inputs))
(t-reduced result)
(apply reducer result inputs))
;; ^^^ (4) ^^^
(funcall reducer result)))))Here t-reduced makes its debut. This wraps the given value in a special type
that signals to t-transduce that the transduction has been short-circuited and
must end. Nothing further will be pulled from the Source.
Despite just being a group of composed functions, individual transducers can
hold state. Consider t-unique, which is called like:
(t-transduce #'t-unique #'t-cons '(1 2 1 3 2 1 2 "abc"))(1 2 3 "abc")
Here’s its definition:
(defun t-unique (reducer)
(let ((seen (make-hash-table :test #'equal)))
(lambda (result &rest inputs)
(if inputs
;; vvv (4) vvv
(if (gethash (car inputs) seen)
result
(progn (puthash (car inputs) t seen)
(funcall reducer result (car inputs))))
;; ^^^ (4) ^^^
(funcall reducer result)))))There are two immediate differences here:
- Since
t-uniquerequires no top-level argument (liket-maport-filter), it is passed directly tot-transduceas#'t-unique. This means we don’t need another innerlambdaand can accept thereducerdirectly. - We can open a
letbefore Point (3), and theseenHash Table is then captured by thelambda. This has the effect of persisting it between every call of thelambdaon each element.
Once again we notice a bare result being returned if we’ve seen the current
element already.
A Reducer is a function that consumes a stream. It accepts two, one, or no arguments.
An example of t-count being called:
(t-transduce #'t-pass #'t-count '(1 2 3 4 5))5
Here is its definition:
(defun t-count (&rest vargs)
(pcase vargs
(`(,acc ,_) (1+ acc)) ;; (I) Iterative case. The stream is still running.
(`(,acc) acc) ;; (D) We're done! Do any post-processing here.
(`() 0))) ;; (M) "Monoidal" / base case.Similar to the Transducer functions, we use the &rest trick and then pattern
match via pcase to test how many arguments we were given.
Let’s start from the bottom with the (M) base case. t-transduce calls this
internally in order to generate an initial value. This corresponds to the result
seen in the Transducer examples. Since each Reducer behaves differently and we
are not using a static type system, we must define the Reducer’s unique “zero
value” here.
(D) is what was hinted at before - this case is called last by transduce in
order to allow the Reducer to do any post-processing before the final value is
yielded to the user. This is necessary as occasionally the acc value grown by
the Reducer can be a complicated structure and we may want to sort it, unwrap
it, etc.
(I) is the usual case and corresponds to some Transducer calling down into the
Reducer with the cumulative state thusfar and the current stream element. The
Reducer then decides what to do with them. In the case of t-count, the element
itself is ignored and we just add 1 to our growing acc.
(defun t-cons (&rest vargs)
(pcase vargs
(`(,acc ,input) (cons input acc)) ;; (I)
(`(,acc) (reverse acc)) ;; (D)
(`() '()))) ;; (M)
Here in (I) we see the input actually being saved. This then loops back around
within t-transduce, which pulls the next value from the Source and calls the
Transducer chain again.
In (D) we see some realistic post-processing. Since (I) was naively consing, the order of our elements is backwards from what we intend. Thus they must be reversed once before being yielded to the user.
In (M) our “zero value” is the empty list. Otherwise, what would we be consing onto on the first pass of (I)?
t-anyp stops as soon as anything satisfies its predicate.
(t-transduce #'t-pass (t-anyp #'cl-evenp) '(1 3 5 2 7 9))t
Usage of t-reduced isn’t limited to Transducers; Reducers can short-circuit the
stream as well.
(defun t-anyp (pred)
(lambda (&rest vargs)
(pcase vargs
(`(,_ ,input)
;; vvv (I) vvv
(if (funcall pred input)
(t-reduced t)
nil))
;; ^^^ (I) ^^^
(`(,acc) acc)
(_ nil))))Like with t-filter, this Reducer requires a top-level predicate, so we add an
inner lambda.
Within (I) we can see t-reduced employed. Seeing this, t-transduce will not
continue and will instead go right to the (D) case. The final acc is T.
t-transduce is a cl-defgeneric, and so can be called on anything that has a
corresponding cl-defmethod for it. There are many “natural” Sources like lists
and vectors, but we can easily define our own and then supply a transduce method
to add it to the family of things we can iterate over.
Let’s review the t-reversed Source, a means by which to iterate over a vector in
reverse order.
(t-transduce #'t-pass #'t-string (t-reversed "Hello"))"olleH"
In order to have a distinct type to associate a t-transduce method with, we need
a wrapper type:
(cl-defstruct t-reversed
"A wrapper around an array/vector/string type."
(array nil :type array))We also supply a prettier constructor:
(defun t-reversed (array)
"Source: Yield an ARRAY's elements in reverse order."
(make-transducers-reversed :array array))Now come a trio of functions that drive the iteration:
(cl-defmethod t-transduce (xform f (source t-reversed))
(t--reversed-transduce xform f source))
(defun t--reversed-transduce (xform f coll)
(let* ((init (funcall f)) ;; (1) The (M) case of the Reducer.
(xf (funcall xform f)) ;; (2) Putting the transducer/reducer chain together.
(result (t--reversed-reduce xf init coll))) ;; (3) The work.
(funcall xf result))) ;; (7) The (D) case of the Reducer.
(defun t--reversed-reduce (f identity rev)
(let* ((arr (t-reversed-array rev))
(len (length arr)))
;; Simple recursion to drive the iteration.
(cl-labels ((recurse (acc i)
(if (< i 0)
acc ;; (4) We're done.
(let ((acc (funcall f acc (aref arr i))))
(if (t-reduced-p acc) ;; (5a) Short-circuiting occured. Time to go home.
(t-reduced-val acc)
(recurse acc (1- i))))))) ;; (5b) Otherwise, keep going.
(recurse identity (1- len)))))All types follow this pattern. In (1) and (2) we do initial setup. In (4) we’ve reached the natural end of the Source (e.g. the end of the vector).
At (5a) we see that we always need to check if the result of the current call was “reduced”, i.e. short-circuited.
That’s it! The beauty of cl-defgeneric is that its methods can be defined in other
packages, meaning you’re free extend this library in your own code.