Transducers and Transducible processes

mapfoldl(xf, step, reducible; init, simd) :: T
transduce(xf, step, init, reducible; simd) :: Union{T, Reduced{T}}

Compose transducer xf with reducing step function step and reduce itr using it.

This API is modeled after transduce in Clojure.

Arguments

• xf::Transducer: A transducer.
• step: A callable which accepts 1 or 2 arguments. If it only accepts 2 arguments, wrap it with Completing to "add" 1-argument form (i.e., complete protocol).
• reducible: A reducible object (array, dictionary, any iterator, etc.).
• init: An initial value fed to the first argument to reducing step function step.
• simd: If true or :ivdep, enable SIMD using Base.@simd. If :ivdep, use @simd ivdep for ... end variant. Read Julia manual of Base.@simd to understand when it is appropriate to use this option. For example, simd = :ivdep must not be used with stateful transducer like Scan. This option has no effect if false (default).

Examples

julia> using Transducers

julia> function step_demo(state, input)
           @show state, input
           state + input
       end;

julia> function step_demo(state)
           println("Finishing with state = ", state)
           state
       end;

julia> mapfoldl(Filter(isodd), step_demo, 1:4, init=0.0)
(state, input) = (0.0, 1)
(state, input) = (1.0, 3)
Finishing with state = 4.0
4.0

transduce(xf, step, init, reducible) :: Union{T, Reduced{T}}

See mapfoldl.

foldl(step, xf::Transducer, reducible; init, simd)
foldl(step, ed::Eduction; init, simd)

The first form is a shorthand for mapfoldl(xf, Completing(step), reducible). It is intended to be used with a do block. It is also equivalent to foldl(step, eduction(xf, itr)).

foldl(step, ed) is useful when calling transducers in a tight loop where setup cost for foldl(step, xf, reducible), mapfoldl(xf, step, reducible), etc. is not negligible. See setinput for how to reset input collection of an Eduction.

See: mapfoldl.

Examples

julia> using Transducers

julia> foldl(Filter(isodd), 1:4, init=0.0) do state, input
           @show state, input
           state + input
       end
(state, input) = (0.0, 1)
(state, input) = (1.0, 3)
4.0

foreach(eff, xf::Transducer, reducible; simd)
foreach(eff, ed::Eduction; simd)

Feed the results of xf processing items in reducible into a unary function eff. This is useful when the primary computation at the bottom is the side-effect. It is also equivalent to foreach(eff, eduction(xf, coll)). Note that

foreach(eduction(xf, coll)) do x
    ...
end

can be more efficient than

for x in eduction(xf, coll)
    ...
end

as the former does not have to translate the transducer protocol to the iterator protocol.

Statements in native for loop can be translated as follows:

See: mapfoldl, reduced, setinput.

Examples

julia> using Transducers

julia> foreach(eduction(Filter(isodd), 1:4)) do input
           @show input
       end
input = 1
input = 3

julia> foreach(Filter(!ismissing), [1, missing, 2, 3]) do input
           @show input
           if iseven(input)
               return reduced()
           end
       end
input = 1
input = 2

mapreduce(xf, step, reducible; init, simd) :: T

Possibly parallel version of mapfoldl. The "bottom" reduction function step(::T, ::T) :: T must be associative and init must be its identity element.

Transducers composing xf must be stateless and non-terminating (e.g., Map, Filter, Cat, etc.) except for ScanEmit. Note that Scan is not supported (although possible in theory).

See mapfoldl.

eduction(xf::Transducer, coll)

Create a iterable and reducible object.

• Iterable.
• Reducible; i.e., it can be handled by transduce efficiently.

This API is modeled after eduction in Clojure.

Examples

julia> using Transducers

julia> for x in eduction(Filter(isodd) |> Take(3), 1:1000)
           @show x
       end
x = 1
x = 3
x = 5

map!(xf::Transducer, dest, src; simd)

Feed src to transducer xf, storing the result in dest. Collections dest and src must have the same shape. Transducer xf may contain filtering transducers. If some entries src are skipped, the corresponding entries in dest will be unchanged. Transducer xf must not contain any expansive transducers such as MapCat.

See also copy!.

Examples

julia> using Transducers

julia> xs = collect(1:5)
       ys = zero(xs)
       map!(Filter(isodd), ys, xs)
5-element Array{Int64,1}:
 1
 0
 3
 0
 5

julia> ans === ys
true

copy!(xf::Transducer, dest, src)

Feed src to transducer xf, storing the result in dest. Collections dest and src may have the same shape. Source src must be iterable. Destination dest must implement empty! and push!.

See also map!.

Examples

julia> using Transducers

julia> copy!(PartitionBy(x -> x ÷ 3) |> Map(sum), Int[], 1:10)
4-element Array{Int64,1}:
  3
 12
 21
 19

append!(xf::Transducer, dest, src)

This API is modeled after into in Clojure.

Examples

julia> using Transducers

julia> append!(Drop(2), [-1, -2], 1:5)
5-element Array{Int64,1}:
 -1
 -2
  3
  4
  5

collect(xf::Transducer, itr)

Process an iterable itr using a transducer xf and collect the result into a Vector.

Examples

julia> using Transducers

julia> collect(Interpose(missing), 1:3)
5-element Array{Union{Missing, Int64},1}:
 1
  missing
 2
  missing
 3

Channel(xf::Transducer, itr; kwargs...)
Channel(ed::Eduction; kwargs...)

Pipe items from an iterable itr processed by the transducer xf through a channel. Channel(xf, itr) and Channel(eduction(xf, itr)) are equivalent. Note that itr itself can be a Channel.

Keyword arguments are passed to Channel(function; kwargs...). ctype is inferred from xf if not specified.

Examples

julia> using Transducers

julia> ch1 = Channel(Filter(isodd), 1:5);

julia> ch2 = Channel(Map(x -> 2x - 1), ch1);

julia> ed = eduction(Map(x -> 1:x), ch2);

julia> ch3 = Channel(Cat(), ed);

julia> typeof(ch1) === typeof(ch2) === typeof(ch3) === Channel{Int}
true

julia> foreach(PartitionBy(isequal(1)), ch3) do input
           @show input
       end
input = [1, 1]
input = [2, 3, 4, 5]
input = [1]
input = [2, 3, 4, 5, 6, 7, 8, 9]

Cat()

Concatenate/flatten nested iterators.

This API is modeled after cat in Clojure.

Examples

julia> using Transducers

julia> collect(Cat(), [[1, 2], [3], [4, 5]]) == 1:5
true

Count([start[, step]])

Generate a sequence start, start + step, start + step + step, and so on.

Note that input is ignored. To use the input in the downstream reduction steps, use Zip.

start defaults to 1 and step defaults to oneunit(start).

See also: Iterators.countfrom. Enumerate

Examples

julia> using Transducers

julia> collect(Zip(Map(identity), Count()), -3:-1)
3-element Array{Tuple{Int64,Int64},1}:
 (-3, 1)
 (-2, 2)
 (-1, 3)

julia> using Dates

julia> collect(Zip(Map(identity), Count(Day(1))) |> Map(xs -> *(xs...)), 1:3)
3-element Array{Day,1}:
 1 day
 4 days
 9 days

Dedupe()

De-duplicate consecutive items.

This API is modeled after dedupe in Clojure.

Examples

julia> using Transducers

julia> collect(Dedupe(), [1, 1, 2, 1, 3, 3, 2])
5-element Array{Int64,1}:
 1
 2
 1
 3
 2

Drop(n)

Drop first n items.

This API is modeled after drop in Clojure.

Examples

julia> using Transducers

julia> collect(Drop(3), 1:5)
2-element Array{Int64,1}:
 4
 5

DropLast(n)

Drop last n items.

This API is modeled after drop-last in Clojure.

Examples

julia> using Transducers

julia> collect(DropLast(2), 1:5)
3-element Array{Int64,1}:
 1
 2
 3

julia> collect(DropLast(2), 1:1)
0-element Array{Int64,1}

julia> collect(DropLast(2), 1:0)
0-element Array{Int64,1}

DropWhile(pred)

Drop items while pred returns true consecutively. It becomes a no-op after pred returns a false.

This API is modeled after drop-while in Clojure.

Examples

julia> using Transducers

julia> collect(DropWhile(x -> x < 3), [1:5; 1:2])
5-element Array{Int64,1}:
 3
 4
 5
 1
 2

Enumerate([start[, step]])

Transducer variant of Base.enumerate. The start and step arguments are optional and have the same meaning as in Count.

Examples

julia> using Transducers

julia> collect(Enumerate(), ["A", "B", "C"])
3-element Array{Tuple{Int64,String},1}:
 (1, "A")
 (2, "B")
 (3, "C")

julia> start=2; step=3;

julia> collect(Enumerate(start, step), ["A", "B", "C"])
3-element Array{Tuple{Int64,String},1}:
 (2, "A")
 (5, "B")
 (8, "C")

Filter(pred)

Skip items for which pred is evaluated to false.

This API is modeled after filter in Clojure.

Examples

julia> using Transducers

julia> collect(Filter(iseven), 1:3)
1-element Array{Int64,1}:
 2

FlagFirst()

Output (isfirst, input) where isfirst::Bool is true only for the first iteration and input is the original input.

See also: IterTools.flagfirst

Examples

julia> using Transducers

julia> collect(FlagFirst(), 1:3)
3-element Array{Tuple{Bool,Int64},1}:
 (true, 1)
 (false, 2)
 (false, 3)

Interpose(sep)

Interleave input items with a sep.

This API is modeled after interpose in Clojure.

Examples

julia> using Transducers

julia> collect(Interpose(missing), 1:3)
5-element Array{Union{Missing, Int64},1}:
 1
  missing
 2
  missing
 3

Iterated(f, init[, T::Type])

Generate a sequence init, f(init), f(f(init)), f(f(f(init))), and so on.

Note that input is ignored. To use the input in the downstream reduction steps, use Zip.

Use the third argument T to specify the output type of f.

An Initializer object can be passed to init for creating a dedicated (possibly mutable) state for each fold.

See also: Scan, ScanEmit.

The idea is taken from IterTools.iterated

Examples

julia> using Transducers

julia> collect(Iterated(x -> 2x, 1), 1:5)
5-element Array{Int64,1}:
  1
  2
  4
  8
 16

julia> collect(Zip(Map(identity), Iterated(x -> 2x, 1)), 1:5)
5-element Array{Tuple{Int64,Int64},1}:
 (1, 1)
 (2, 2)
 (3, 4)
 (4, 8)
 (5, 16)

Keep(f)

Pass non-nothing output of f to the inner reducing step.

This API is modeled after keep in Clojure.

Examples

julia> using Transducers

julia> xf = Keep() do x
           if x < 3
               x + 1
           end
       end;

julia> collect(xf, 1:5)
2-element Array{Int64,1}:
 2
 3

Map(f)

Apply unary function f to each input and pass the result to the inner reducing step.

This API is modeled after map in Clojure.

Examples

julia> using Transducers

julia> collect(Map(x -> 2x), 1:3)
3-element Array{Int64,1}:
 2
 4
 6

MapCat(f)

Concatenate output of f which is expected to return an iterable.

This API is modeled after mapcat in Clojure.

Examples

julia> using Transducers

julia> collect(MapCat(x -> 1:x), 1:3)
6-element Array{Int64,1}:
 1
 1
 2
 1
 2
 3

MapSplat(f)

Like Map(f) but calls f(input...) for each input and then pass the result to the inner reducing step.

Examples

julia> using Transducers

julia> collect(MapSplat(*), zip(1:3, 10:10:30))
3-element Array{Int64,1}:
 10
 40
 90

NotA(T)

Skip items of type T. Unlike Filter(!ismissing), downstream transducers can have a correct type information for NotA(Missing).

See also: OfType

Examples

julia> using Transducers

julia> collect(NotA(Missing), [1, missing, 2])
2-element Array{Int64,1}:
 1
 2

julia> collect(Filter(!ismissing), [1, missing, 2])  # see the eltype below
2-element Array{Union{Missing, Int64},1}:
 1
 2

OfType(T)

Include only items of type T.

See also: NotA

Examples

julia> using Transducers

julia> collect(OfType(Int), [1, missing, 2])
2-element Array{Int64,1}:
 1
 2

julia> collect(Filter(!ismissing), [1, missing, 2])  # see the eltype below
2-element Array{Union{Missing, Int64},1}:
 1
 2

Partition(size, step = size, flush = false)
Partition(size; step = size, flush = false)

Sliding window of width size and interval step.

This API is modeled after partition-all in Clojure.

Examples

julia> using Transducers

julia> collect(Partition(3) |> Map(copy), 1:8)
2-element Array{Array{Int64,1},1}:
 [1, 2, 3]
 [4, 5, 6]

julia> collect(Partition(3; flush=true) |> Map(copy), 1:8)
3-element Array{Array{Int64,1},1}:
 [1, 2, 3]
 [4, 5, 6]
 [7, 8]

julia> collect(Partition(3; step=1) |> Map(copy), 1:8)
6-element Array{Array{Int64,1},1}:
 [1, 2, 3]
 [2, 3, 4]
 [3, 4, 5]
 [4, 5, 6]
 [5, 6, 7]
 [6, 7, 8]

PartitionBy(f)

Group input sequence into chunks in which f returns a same value consecutively.

This API is modeled after partition-by in Clojure.

Examples

julia> using Transducers

julia> collect(PartitionBy(x -> (x + 1) ÷ 3) |> Map(copy), 1:9)
4-element Array{Array{Int64,1},1}:
 [1]
 [2, 3, 4]
 [5, 6, 7]
 [8, 9]

Replace(assoc)

Replace each input with the value in the associative container assoc (e.g., a dictionary, array, string) if it matches with a key/index. Otherwise output the input as-is.

This API is modeled after replace in Clojure.

Examples

julia> using Transducers

julia> collect(Replace(Dict('a' => 'A')), "abc")
3-element Array{Char,1}:
 'A'
 'b'
 'c'

julia> collect(Replace([:a, :b, :c]), 0:4)
5-element Array{Union{Int64, Symbol},1}:
 0
  :a
  :b
  :c
 4

julia> collect(Replace("abc"), 0:4)
5-element Array{Union{Char, Int64},1}:
 0
  'a'
  'b'
  'c'
 4

Scan(f, [init])

Accumulate input with binary function f and pass the accumulated result so far to the inner reduction step.

The inner reducing step receives the sequence y₁, y₂, y₃, ..., yₙ, ... when the sequence x₁, x₂, x₃, ..., xₙ, ... is fed to Scan(f).

y₁ = f(init, x₁)
y₂ = f(y₁, x₂)
y₃ = f(y₂, x₃)
...
yₙ = f(yₙ₋₁, xₙ)

This is a generalized version of the prefix sum also known as cumulative sum, inclusive scan, or scan.

Note that the associativity of f is not required when the transducer is used in a process that gurantee an order, such as mapfoldl.

Unless f is a function with known identity element such as +, *, min, max, and append!, the initial state init must be provided.

An Initializer object can be passed to init for creating a dedicated (possibly mutable) state for each fold.

See also: ScanEmit, Iterated.

Examples

julia> using Transducers

julia> collect(Scan(*), 1:3)
3-element Array{Int64,1}:
 1
 2
 6

julia> collect(Map(x -> x + im) |> Scan(*), 1:3)
3-element Array{Complex{Int64},1}:
 1 + 1im
 1 + 3im
 0 + 10im

julia> collect(Scan(*, 10), 1:3)
3-element Array{Int64,1}:
 10
 20
 60

ScanEmit(f, init[, onlast])

Accumulate input x with a function f with the call signature (u, x) -> (y, u) and pass the result y to the inner reduction step.

The inner reducing step receives the sequence y₁, y₂, y₃, ..., yₙ, ... computed as follows

u₀ = init
y₁, u₁ = f(u₀, x₁)
y₂, u₂ = f(u₁, x₂)
y₃, u₃ = f(u₂, x₃)
...
yₙ, uₙ = f(uₙ₋₁, xₙ)
...
yₒₒ = onlast(uₒₒ)

when the sequence x₁, x₂, x₃, ..., xₙ, ... is fed to ScanEmit(f).

An Initializer object can be passed to init for creating a dedicated (possibly mutable) state for each fold.

See also: ScanEmit, Iterated.

Examples

julia> using Transducers

julia> collect(ScanEmit(tuple, 0), 1:3)
3-element Array{Int64,1}:
 0
 1
 2

Take(n)

Take n items from the input sequence.

This API is modeled after take in Clojure.

Examples

julia> using Transducers

julia> collect(Take(2), 1:10)
2-element Array{Int64,1}:
 1
 2

julia> collect(Take(5), 1:2)
2-element Array{Int64,1}:
 1
 2

TakeLast(n)

Take last n items from the input sequence.

Examples

julia> using Transducers

julia> collect(TakeLast(2), 1:10)
2-element Array{Int64,1}:
  9
 10

julia> collect(TakeLast(5), 1:2)
2-element Array{Int64,1}:
 1
 2

TakeNth(n)

Output every n item to the inner reducing step.

This API is modeled after take-nth in Clojure.

Examples

julia> using Transducers

julia> collect(TakeNth(3), 1:9)
3-element Array{Int64,1}:
 1
 4
 7

TakeWhile(pred)

Take items while pred returns true. Abort the reduction when pred returns false for the first time.

This API is modeled after take-while in Clojure.

Examples

julia> using Transducers

julia> collect(TakeWhile(x -> x < 3), [1, 2, 3, 1, 2])
2-element Array{Int64,1}:
 1
 2

Unique()

Pass only unseen item to the inner reducing step.

This API is modeled after distinct in Clojure.

Examples

julia> using Transducers

julia> collect(Unique(), [1, 1, 2, 1, 3, 3, 2])
3-element Array{Int64,1}:
 1
 2
 3

Zip(xforms...)

Zip outputs of transducers xforms in a tuple and pass it to the inner reduction step.

Examples

julia> using Transducers

julia> collect(Zip(Map(identity), Map(x -> 10x), Map(x -> 100x)), 1:3)
3-element Array{Tuple{Int64,Int64,Int64},1}:
 (1, 10, 100)
 (2, 20, 200)
 (3, 30, 300)

TeeZip(xform::Transducer)

Branch input into two "flows", inject one into xform and then merge the output of xform with the original input.

To illustrate how it works, consider the following usage

xf0 |> TeeZip(xf1) |> xf2

where xf0, xf1, and xf2 are some transducers. Schematically, the output yn from xfn flows as follows:

xf0      xf1                       xf2
---- y0 ------ y1 ---.-- (y0, y1) ----->
      |              |
       `-------------'
    "Tee"          "Zip"

Examples

julia> using Transducers
       using Transducers: TeeZip

julia> collect(TeeZip(Filter(isodd) |> Map(x -> x + 1)), 1:5)
3-element Array{Tuple{Int64,Int64},1}:
 (1, 2)
 (3, 4)
 (5, 6)

GetIndex(array)
GetIndex{inbounds}(array)

Transform an integer input i to array[i].

Examples

julia> using Transducers
       using Transducers: GetIndex

julia> collect(GetIndex(1:10), [2, 3, 4])
3-element Array{Int64,1}:
 2
 3
 4

julia> collect(GetIndex{true}(1:10), [2, 3, 4])
3-element Array{Int64,1}:
 2
 3
 4

SetIndex(array)
SetIndex{inbounds}(array)

Perform array[i] = v for each input pair (i, v).

Examples

julia> using Transducers
       using Transducers: SetIndex

julia> ys = zeros(3);

julia> mapfoldl(SetIndex(ys), first ∘ tuple, [(1, 11.1), (3, 33.3)], init=nothing)

julia> ys
3-element Array{Float64,1}:
 11.1
  0.0
 33.3

Inject(iterator)

Inject the output from iterator to the stream processed by the inner reduction step.

Examples

julia> using Transducers
       using Transducers: Inject

julia> collect(Inject(Iterators.cycle("hello")), 1:8)
8-element Array{Tuple{Int64,Char},1}:
 (1, 'h')
 (2, 'e')
 (3, 'l')
 (4, 'l')
 (5, 'o')
 (6, 'h')
 (7, 'e')
 (8, 'l')

julia> collect(Inject(Iterators.repeated([1 2])), 1:4)
4-element Array{Tuple{Int64,Array{Int64,2}},1}:
 (1, [1 2])
 (2, [1 2])
 (3, [1 2])
 (4, [1 2])

julia> collect(Inject(Iterators.product(1:2, 3:5)), 1:100)
6-element Array{Tuple{Int64,Tuple{Int64,Int64}},1}:
 (1, (1, 3))
 (2, (2, 3))
 (3, (1, 4))
 (4, (2, 4))
 (5, (1, 5))
 (6, (2, 5))

Reduced

The type signaling transducible processes to abort.

See reduced, unreduced.

Examples

julia> using Transducers

julia> function step_demo(y, x)
           if x > 5
               return reduced(y)
           else
               return y + x
           end
       end;

julia> result = transduce(Map(identity), Completing(step_demo), 0, 1:10)
Reduced{Int64}(15)

julia> result isa Reduced
true

julia> unreduced(result)
15

julia> result = transduce(Map(identity), Completing(step_demo), 0, 1:4)
10

julia> result isa Reduced
false

julia> unreduced(result)
10

reduced([x = nothing])

Stop transducible process with the final value x (default: nothing). Return x as-is if it's already is a reduced value.

See Reduced, unreduced.

This API is modeled after ensure-reduced in Clojure.

Examples

julia> using Transducers

julia> foldl(Enumerate(), "abcdef"; init=0) do y, (i, x)
           if x == 'd'
               return reduced(y)
           end
           return y + i
       end
6

julia> foreach(Enumerate(), "abc") do (i, x)
           println(i, ' ', x)
           if x == 'b'
               return reduced()
           end
       end
1 a
2 b

unreduced(x)

Unwrap x if it is a Reduced; do nothing otherwise.

See Reduced, reduced.

This API is modeled after unreduced in Clojure.

Completing(function)

Wrap a function to add a no-op complete protocol. Use it when passing a function without 1-argument arity to transduce etc.

This API is modeled after completing in Clojure.

Initializer(f)

Wrap a factory function to create an initial value for transducible processes (e.g., mapfoldl) and "stateful" transducers (e.g., Scan). Factory function f takes the input type to the transducer or the reducing function.

Initializer must be used whenever using in-place reduction with mapreduce.

Examples

julia> using Transducers

julia> xf1 = Scan(push!, [])
Scan(push!, Any[])

julia> mapfoldl(xf1, right, 1:3)
3-element Array{Any,1}:
 1
 2
 3

julia> xf1
Scan(push!, Any[1, 2, 3])

Notice that the array is stored in xf1 and mutated in-place. As a result, second run of mapfoldl contains the results from the first run:

julia> mapfoldl(xf1, right, 10:11)
5-element Array{Any,1}:
  1
  2
  3
 10
 11

This may not be desired. To avoid this behavior, create an Initializer object which takes a factory function to create a new initial value.

julia> xf2 = Scan(push!, Initializer(T -> T[]))
Scan(push!, Initializer(##9#10()))

julia> mapfoldl(xf2, right, 1:3)
3-element Array{Int64,1}:
 1
 2
 3

julia> mapfoldl(xf2, right, [10.0, 11.0])
2-element Array{Float64,1}:
 10.0
 11.0

Keyword argument init for transducible processes also accept an Initializer:

julia> mapfoldl(Map(identity), push!, "abc"; init=Initializer(T -> T[]))
3-element Array{Char,1}:
 'a'
 'b'
 'c'

right([l, ]r) -> r

It is simply defined as

right(l, r) = r
right(r) = r

This function is meant to be used as step argument for mapfoldl etc. for extracting the last output of the transducers. Note that init for right is set to nothing if not provided.

Examples

julia> using Transducers

julia> mapfoldl(Take(5), right, 1:10)
5

julia> mapfoldl(Drop(5), right, 1:3) === nothing
true

julia> mapfoldl(Drop(5), right, 1:3; init=0)  # using `init` as the default value
0

setinput(ed::Eduction, coll)

Set input collection of eduction ed to coll. This is efficient than re-creating an Eduction with a new coll if eltype of old and new input collections are the same.

Examples

julia> using Transducers

julia> ed = eduction(Map(x -> 2x), Float64[]);

Here, we created an Eduction with input container whose eltype is Float64. It can be used later with different container.

julia> using Test

julia> xs = ones(2, 3);

julia> foldl(+, @inferred setinput(ed, xs))
12.0

Note that we changed the container type from Vector to Matrix while using the same eltype. In this case, setinput is inferrable and thus can be compiled away. It is also possible to set container with different eltype although not inferrable in this case:

julia> xs = ones(Int, 2, 3);

julia> foldl(+, setinput(ed, xs))
12

julia> foldl(+, @inferred setinput(ed, xs))
ERROR: return type Transducers.Eduction{...} does not match inferred return type ...
[...]