Internals

DefaultInit(op)

DefaultInit is like Init but strictly internal to Transducers.jl. It is used for checking if the bottom reducing function is never called.

AdHocRF(next; oninit, start = identity, complete = identity, combine = next)

Define an ad-hoc reducing function rf.

Arguments

• next: binary function

Keyword Arguments

• oninit: nullary function that generates an initial value for next
• start: unary function that pre-process the initial value for next
• complete: unary function that post-process the accumulator
• combine: (approximately) associative binary function for combining multiple results of next (before post-processed by complete).

Examples

julia> using Transducers
       using Transducers: AdHocRF

julia> rf = AdHocRF(push!, combine = append!);

julia> foldxt(rf, Map(identity), 1:4; basesize = 1, init = OnInit(() -> []))
4-element Vector{Any}:
 1
 2
 3
 4

AdHocXF(f, init, [onlast])

Examples

julia> using Transducers

julia> using Transducers: AdHocXF, @next

julia> using Accessors: @reset

julia> flushlast(rf, result) = rf(@next(rf, result, result.state));

julia> xf = AdHocXF(nothing, flushlast) do rf, result, input
           m = match(r"^name:(.*)", input)
           if m === nothing
               push!(result.state.lines, input)
               return result
           else
               chunk = result.state
               @reset result.state = (name=strip(m.captures[1]), lines=String[])
               push!(result.state.lines, input)
               if chunk === nothing
                   return result
               else
                   return rf(result, chunk)
               end
           end
       end;

julia> collect(xf, split("""
       name: Map
       type: onetoone
       name: Cat
       type: expansive
       name: Filter
       type: contractive
       name: Cat |> Filter
       type: chaotic
       """, "\n"; keepempty=false))
4-element Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}:
 (name = "Map", lines = ["name: Map", "type: onetoone"])
 (name = "Cat", lines = ["name: Cat", "type: expansive"])
 (name = "Filter", lines = ["name: Filter", "type: contractive"])
 (name = "Cat |> Filter", lines = ["name: Cat |> Filter", "type: chaotic"])

Transducers.NoAdjoint(itr)

Bypass the optimization step by retransform.

Transducers.ReduceSplitBy(f, rf, init)

Split chunks by elements evaluated to true by f and reduce each chunk by reducing function rf.

The reducing function rf receives either a Bulk(x) if !f(x) or a End(x) if f(x) returns true. Just just after rf is called with End(x), its accumulator is finalized by complete and then passed to the downstream transducer/reducing function.

Examples

julia> using Transducers
       using Transducers: ReduceSplitBy, Bulk, End

julia> 1:5 |> ReduceSplitBy(isodd, Map(getindex)'(string), "") |> collect
3-element Vector{String}:
 "1"
 "23"
 "45"

julia> function just_bulk(x)
           if x isa Bulk
               Some(x[])
           else
               nothing
           end
       end;

julia> 1:5 |> ReduceSplitBy(isodd, KeepSomething(just_bulk)'(string), "") |> collect
3-element Vector{String}:
 ""
 "2"
 "4"

ReducingFunctionTransform(xf)

The "true" transducer.

UseSIMD{ivdep}()

Tell the reducible to run the inner reducing function using @simd. The reducible can support it using @simd_if.

_set_joiner_value(ps::PrivateState, x) :: PrivateState

Set .state field of the PrivateState of the first "unbalanced" Joiner. A Joiner matched with preceding Splitter would be treated as a regular reducing function node. Thus, private state ps must have one more Joiner than Splitter.

_unzip(xs::Tuple)

Examples

julia> _unzip(((1, 2, 3), (4, 5, 6)))
((1, 4), (2, 5), (3, 6))

air.(broadcasting_expression) :: Broadcasted

Broadcast without materialization.

The idea is taken from @dawbarton's _lazy function: https://discourse.julialang.org/t/19641/20.

Transducers.asfoldable(x) -> foldable

By default, this function does nothing, but it can be overloaded to convert an input into another type before reducing over it. This allows one to implement a foldable in terms of transducers over an existing type. For instance,

struct VectorOfVectors{T}
   v::Vector{Vector{T}}
end

Transducers.asfoldable(vov::VectorOfVectors{T}) = vov.v |> Cat()

Now we can do things like

julia> foldxl(+, VectorOfVectors([[1,2], [3, 4]]))
10

Transducers.combine(rf::R_{X}, state_left, state_right)

This is an optional interface for a transducer. If transducer X is stateful (i.e., wrap is used in start), it has to be able to combine the private states to support fold functions that require an associative reducing function such as foldxt. Typical implementation takes the following form:

function combine(rf::R_{X}, a, b)
    #   ,---- `ua` and `ub` are the private state of the transducer `X`
    #  /  ,-- `ira` and `irb` are the states of inner reducing functions
    # /  /
    ua, ira = unwrap(rf, a)
    ub, irb = unwrap(rf, b)
    irc = combine(inner(rf), ira, irb)
    uc = # somehow combine private states `ua` and `ub`
    return wrap(rf, uc, irc)
end

See ScanEmit, etc. for real-world examples.

Transducers.completebasecase(rf, state)

Process basecase result state before merged by combine.

For example, on GPU, this function can be used to translate mutable states to immutable values for exchanging them through (un-GC-managed) memory. See whencompletebasecase.

extract_transducer(foldable) -> (xf, foldable′)

"Reverse" of eduction.

Examples

julia> using Transducers

julia> double(x) = 2x;

julia> xs = 1:10;

julia> xf, foldable = Transducers.extract_transducer(Iterators.map(double, xs));

julia> xf == Map(double)
true

julia> foldable == xs
true

foldl_basecase(rf, init, coll)

foldl for basecase of parallel reduction. Call __foldl__ without calling complete and then call completebasecase.

foldl_nocomplete(rf, init, coll)

Call __foldl__ without calling complete.

initialize(initializer, op) -> init
initialize(init, _) -> init

Return an initial value for op. Throw an error if initializer (e.g., Init) creates unknown initial value.

Examples

julia> using Transducers
       using Transducers: initialize

julia> initialize(Init, +)
InitialValue(+)

julia> initialize(123, +)
123

julia> unknown_op(x, y) = x + 2y;

julia> initialize(Init, unknown_op)
ERROR: IdentityNotDefinedError: `init = Init` is specified but the identity element `InitialValue(op)` is not defined for
    op = unknown_op
[...]

initvalue(initializer::AbstractInitializer) -> init
initvalue(init) -> init

Materialize the initial value if the input is an AbstractInitializer. Return the input as-is if not.

is_prelude(::T)

Return true if it is better to tail-call when the accumulator or the private state changes its type from T.

Transducers.issmall(reducible, basesize) :: Bool

Check if reducible collection is considered small compared to basesize (an integer). Fold functions such as foldxt switches to sequential __foldl__ when issmall returns true.

Default implementation is amount(reducible) <= basesize.

maybe_usesimd(xform, simd)

Insert UseSIMD to xform if appropriate.

Arguments

• xform::Transducer
• simd: false, true, or :ivdep.

Examples

julia> using Transducers
       using Transducers: maybe_usesimd

julia> maybe_usesimd(reducingfunction(Map(identity), right), false)
Reduction(
    Map(identity),
    BottomRF(
        Transducers.right))

julia> maybe_usesimd(reducingfunction(Map(identity), right), true)
Reduction(
    Transducers.UseSIMD{false}(),
    Reduction(
        Map(identity),
        BottomRF(
            Transducers.right)))

julia> maybe_usesimd(reducingfunction(Cat(), right), true)
Reduction(
    Cat(),
    Reduction(
        Transducers.UseSIMD{false}(),
        BottomRF(
            Transducers.right)))

julia> maybe_usesimd(opcompose(Map(sin), Cat(), Map(cos))'(right), :ivdep)
Reduction(
    Map(sin),
    Reduction(
        Cat(),
        Reduction(
            Transducers.UseSIMD{true}(),
            Reduction(
                Map(cos),
                BottomRF(
                    Transducers.right)))))

julia> maybe_usesimd(
           opcompose(Map(sin), Cat(), Map(cos), Cat(), Map(tan))'(right),
           true,
       )
Reduction(
    Map(sin),
    Reduction(
        Cat(),
        Reduction(
            Map(cos),
            Reduction(
                Cat(),
                Reduction(
                    Transducers.UseSIMD{false}(),
                    Reduction(
                        Map(tan),
                        BottomRF(
                            Transducers.right)))))))

reform(rf, f)

Reset "bottom" reducing function of rf to f.

Transducers.retransform(rf, itr) -> rf′, itr′

Extract transformations in rf and itr and use the appropriate adjoint for better performance.

Note that the reducing function extracted from a comprehension such as (f(x) for x ∈ itr) may not be == to f because of the way generator comprehensions work in Julia. Use Iterators.map to specify an exact mapping function.

Examples

julia> using Transducers

julia> double(x) = 2x;

julia> itr0 = 1:10;

julia> itr1 = Iterators.map(double, itr0);

julia> rf, itr2 = Transducers.retransform(+, itr1);

julia> itr2 === itr0
true

julia> rf == reducingfunction(Map(double), +)
true

simple_transduce(xform, step, init, coll)

Simplified version of transduce. For simple transducers Julia may be able to emit a good code. This function exists only for performance tuning.

usesimd(rf::Reduction, xfsimd::UseSIMD)

Wrap the inner-most loop of reducing function rf with xfsimd. xfsimd is inserted after the inner-most Cat if rf includes Cat.

whencompletebasecase(completebasecase, rf) -> rf′
whencompletebasecase(completebasecase) -> rf -> rf′

Add completebasecase protocol to arbitrary reducing function.

The function completebasecase is used as follows in the basecase implementation of reduce as follows:

init′ = oninit()
acc = start(init′)
for x in collection
    acc += rf(acc, x)
end
result = completebasecase(acc)
return result

The result₁ from basecase 1 and result₂ from basecase 2 are combined using combine protocol:

combine(result₁, result₂)

@default_finaltype(xf::Transducer, coll)

Infer the type of the object that would be fed into the second argument input of the bottom reducing function rf(acc, input).

See: Base.@default_eltype

@simd_if rf for ... end

Wrap for-loop with @simd if the outer most transducer of the reducing function rf is UseSIMD.

(@~ broadcasting_expression) :: Broadcasted

restack(x) -> x

An identity function in the sense restack(x) === x. However, it (recursively) re-construct x to beg the compiler to move everything in the stack.