Glossary
foldl(step, xf, input, init=...)
# | | | |
# | | | `-- reducible
# | | |
# | | `-- transducer
# | |
# | `-- "bottom" (inner most) reducing function
# |
# `-- transducible process
Reducing step function
Reducing function or Reducing step (function): A reducing function combines result-so-far with the input. It in a narrow sense is a "callable" op
of the signature op(::X, ::Y) :: X
(or op(::X, ::X) :: X
in case for foldxt
) or schematically:
It is the function that can be passed to the classic (non-Transducers.jl) Base.foldl
or Base.reduce
. It is sometimes referred to as a step
or op
. In Transducers.jl, next(rf, ::X, ::Y) :: X
is used instead of a "bare" callable. Furthermore, a reducing function in a loose sense also includes other interfaces such as start(rf, ::X)
and complete(rf, ::X)
.
Transducer
A transducer in Transducers.jl is a transformation xf
that
- transforms an iterator with
xf(itr)
(iterator transformation) - transforms a reducing step function with
xf'(rf)
(reducing function transformation)
Common variable names for transducers are xf
and xform
.
The idea of generalizing the transducer as two kinds of transformation is due to Jan Weidner @jw3126
. See the discussion in JuliaFolds/Transducers.jl#67.
Iterator transformation
As of Transducers.jl 0.4.39, the call overload of Transducer
is interpreted as an iterator transformation. That is to say, the iterator transformation using Base.Iterators
julia> ixf₁ = itr -> Iterators.filter(isodd, itr);
and the iterator transformation in Transducers.jl
julia> ixf₂ = Filter(isodd);
behaves identically:
julia> collect(ixf₁(1:10)) == collect(ixf₂(1:10))
true
Filter(isodd)(1:10)
is an eduction
.
Reducing function transformation
Transducers.jl 0.4.39 also exposes reducing function (RF) transformation with xf'(rf)
(adjoint
):
julia> rf = Filter(isodd)'(+); # equivalent to (acc, x) -> isodd(x) ? acc + x : acc
julia> rf(0, 2) # `2` filtered out
0
julia> rf(0, 1) # `1` not filtered out
1
Transducer in the narrow sense (Clojure)
The transducer as originally introduced by Rich Hickey is a transformation of reducing step function. Thus, what is referred to as a transducer $\mathrm{xf}$ in Clojure and many other languages is the reducing function transformation xf'
in Transducer.jl.
Since a transducer in the narrow sense maps a reducing function to a reducing function, it can be composed with simple function composition $∘$. When a composite transducer $\mathrm{xf} = \mathrm{xf}_1 \circ \mathrm{xf}_2 \circ ... \circ \mathrm{xf}_n$ to a "bottom" reducing function $\mathrm{rf}_0$, it is processed from right to left just like normal functions:
which is equivalent to the following forms in Transducers.jl
rf = xf₁'(xf₂'(...(xfₙ'(rf₀))))
rf = (xf₁' ∘ xf₂' ∘ ... ∘ xfₙ')(rf₀)
rf = (xfₙ ∘ ... ∘ xf₂ ∘ xf₁)'(rf₀)
rf = (xf₁ ⨟ xf₂ ⨟ ... ⨟ xfₙ)(rf₀)
Inner transducer
Given a composition xf₁' ∘ xf₂'
, transducer xf₂
is said to be the inner transducer of xf₁' ∘ xf₂'
. Likewise, xf₂'(rf₀)
is an inner reducing function of xf₁'(xf₂'(rf₀))
.
Reducible collection
Reducible collection (or just Reducible): Any object that can be passed to foldl
and alike is reducible. A reducible collection knows how to apply reducing function to its elements. Iterators are automatically reducible as this is the canonical fallback implementation.
Transducible process
A function that can foldxt reducible collections using transducers is a transducible process. Examples are foldl
and foldxt
. Find more in Transducible processes.