Transducers

The main part of this library is a wide collection of transducers implemented using the techniques described in the Design section. Many of them borrow the names of their Clojure equivalents, but there are additional ones inspired by Python itertools and other sequence manipulation libraries.

cat

constexpr auto zug::cat = comp(cat_t{})

Flattens the sequence one level. If multiple inputs are received, it flattens all inputs in parallel.

auto v = std::vector<std::vector<int>>{{1, 2}, {3}, {4, 5, 6}};
auto r = into_vector(cat, v);
CHECK(r == (std::vector<int>{1, 2, 3, 4, 5, 6}));

auto v1 = std::vector<std::vector<int>>{{1, 2}, {3, 4}};
auto v2 = std::vector<std::vector<char>>{{'a'}, {'c', 'd'}};
auto r  = into_vector(cat, v1, v2);
using t = std::vector<std::tuple<int, char>>;
CHECK(r == (t{{1, 'a'}, {3, 'c'}, {4, 'd'}}));

chain

template <typename… InputRangeTs>

auto zug::chain(InputRangeTs&&... rs)

Alias for chainr.

template <typename… InputRangeTs>

auto zug::chainr(InputRangeTs... rs)

Transducer produces the sequence passed as parameter after all other input has finished.

auto v1  = std::vector<int>{1, 2};
auto v2  = std::vector<int>{13, 42, 5};
auto res = into_vector(chain(v2), v1);
CHECK(res == (std::vector<int>{1, 2, 13, 42, 5}));

auto v1  = std::vector<int>{1, 2};
auto v2  = std::vector<int>{13, 42, 5};
auto res = into_vector(chain(v2, v1), v1);
CHECK(res == (std::vector<int>{1, 2, 13, 42, 5, 1, 2}));

// This is a limitation of the pure stateful transducer design
auto v1  = std::vector<int>{};
auto v2  = std::vector<int>{13, 42, 5};
auto res = into_vector(chain(v2), v1);
CHECK(res == (std::vector<int>{}));

template <typename… InputRangeTs>

auto zug::chainl(InputRangeTs... rs)

Transducer produces the sequence passed as parameter before processing the first input.

auto v1  = std::vector<int>{1, 2};
auto v2  = std::vector<int>{13, 42, 5};
auto res = into_vector(chainl(v2), v1);
CHECK(res == (std::vector<int>{13, 42, 5, 1, 2}));

auto v1  = std::vector<int>{1, 2};
auto v2  = std::vector<int>{13, 42, 5};
auto res = into_vector(chainl(v2, v1), v1);
CHECK(res == (std::vector<int>{1, 2, 13, 42, 5, 1, 2}));

// This is a limitation of the pure stateful transducer design
auto v1  = std::vector<int>{};
auto v2  = std::vector<int>{13, 42, 5};
auto res = into_vector(chainl(v2), v1);
CHECK(res == (std::vector<int>{}));

count

template <typename InitT = std::size_t, typename DeltaT = InitT>

constexpr auto zug::count(InitT init = InitT{0}, DeltaT delta = DeltaT{1})

Generator transducer produces a sequence:

$$init, init+step, …, init+step*n$$

It is inspired by Python’s itertools.count generator.

auto v  = std::vector<int>{13, 42, 5};
auto r  = into_vector(count(), v);
using t = std::vector<std::tuple<int, std::size_t>>;
CHECK(r == (t{{13, 0u}, {42, 1u}, {5, 2u}}));

auto r = into_vector(count(1.0, 0.5) | take(5));
CHECK(r == (std::vector<double>{{1.0, 1.5, 2.0, 2.5, 3.0}}));

cycle

template <typename… InputRangeTs>

constexpr auto zug::cycle(InputRangeTs&&... rs)

Generator transducer produces the sequence passed as parameter, by cycling over it.

auto v1 = std::vector<int>{13, 42, 5, 6, 15};
auto v2 = std::vector<int>{0, 1};
auto r  = into_vector(cycle(v2), v1);
using t = std::vector<std::tuple<int, int>>;
CHECK(r == (t{{13, 0}, {42, 1}, {5, 0}, {6, 1}, {15, 0}}));

auto v1 = std::vector<int>{0, 1};
auto v2 = std::vector<std::string>{"one", "two", "three"};
auto r  = into_vector(cycle(v1, v2) | take(5));
using t = std::vector<std::tuple<int, std::string>>;
CHECK(r == (t{{0, "one"}, //
              {1, "two"},
              {0, "three"},
              {1, "one"},
              {0, "two"}}));

dedupe

constexpr auto zug::dedupe = comp(dedupe_t{})

Transducer that removes consecutive duplicates from a sequence.

auto v   = std::vector<int>{1, 1, 2, 1, 1, 3, 2, 2, 2, 1};
auto res = into_vector(dedupe, v);
CHECK(res == (decltype(res){1, 2, 1, 3, 2, 1}));

distinct

constexpr auto zug::distinct = comp(distinct_t{})

Transducer that removes duplicates from a sequence.

Note that this transducer uses \( O(n) \) space (with \( n \) being the size of the resulting sequence) since it needs to remember every element in the sequence to mark whether it’s been seen.

auto v   = std::vector<int>{1, 2, 1, 3, 2, 1};
auto res = into_vector(distinct, v);
CHECK(res == (decltype(res){1, 2, 3}));

drop

template <typename IntegralT>

constexpr auto zug::drop(IntegralT n)

Removes the first n elements from the sequence.

auto v   = std::vector<int>{1, 2, 3, 4, 5};
auto res = into_vector(drop(2), v);
CHECK(res == (decltype(res){3, 4, 5}));

drop_while

template <typename PredicateT>

constexpr auto zug::drop_while(PredicateT &&predicate)

Skips every element that passes the predicate, until one element passes it it. From then on it lets everything go through.

auto v   = std::vector<int>{1, 2, 3, 4, 3, 2, 1};
auto res = into_vector(drop_while([](int x) { return x < 4; }), v);
CHECK(res == (decltype(res){4, 3, 2, 1}));

each

template <typename ActionT>

constexpr auto zug::each(ActionT &&action)

Transducer that evaluates the function action on each input, forwarding the input down the original inputs down the transducer chain. The provided function is used only for side-effects.

auto v  = std::vector<int>{1, 2, 3, 6};
auto r1 = std::vector<int>{};
auto r2 = into_vector(each([&](int x) { r1.push_back(x); }), v);
CHECK(v == r1);
CHECK(v == r2);

eager

template <typename Algo>

constexpr auto zug::eager(Algo algo)

Transducer that processes the whole sequence with the eager algorithm algo. algo is a function that takes a vector as an argument a returns a range. It used to implement other transducers, like sorted and reversed.

Note that this transducer produces no output until completion and uses \( O(n) \) space.

constexpr auto zug::sorted = eager(sorted_t{})

Eager transducer that sorts the input sequence.

auto v = std::vector<int>{6, 2, 1, 12, 3};
auto r = into_vector(sorted, v);
CHECK(r == (decltype(r){1, 2, 3, 6, 12}));

constexpr auto zug::reversed = eager(reversed_t{})

Eager transducer that reverses the input sequence.

auto v = std::vector<int>{1, 2, 3, 4, 5};
auto r = into_vector(reversed, v);
CHECK(r == (decltype(r){5, 4, 3, 2, 1}));

enumerate

constexpr auto zug::enumerate = enumerate_from(std::size_t{})

Enumerates elements in the stream, by prepending the index at in which they appear, starting from initial.

auto s = std::string{"hello"};
auto r = into_vector(enumerate, s);
CHECK(r == decltype(r){{0, 'h'}, {1, 'e'}, {2, 'l'}, {3, 'l'}, {4, 'o'}});

template <typename T>

constexpr auto zug::enumerate_from(T &&initial)

Enumerates elements in the stream, by prepending the index at in which they appear, starting from initial.

auto s = std::string{"hello"};
auto r = into_vector(enumerate_from(2), s);
CHECK(r == decltype(r){{2, 'h'}, {3, 'e'}, {4, 'l'}, {5, 'l'}, {6, 'o'}});

filter

template <typename PredicateT>

auto zug::filter(PredicateT &&predicate)

Transducer that removes all inputs that do not pass the predicate.

auto v   = std::vector<int>{1, 2, 3, 4, 5, 6};
auto res = into_vector(filter([](int x) { return x % 2; }), v);
CHECK(res == decltype(v){1, 3, 5});

interleave

constexpr auto zug::interleave = comp(interleave_t{})

Feed every argument of each element individually into the stream.

auto v = std::vector<int>{1, 2, 3, 4, 5};
auto r = into_vector(interleave, v, v);
CHECK(r == decltype(r){1, 1, 2, 2, 3, 3, 4, 4, 5, 5});

interpose

template <typename… ValueTs>

auto zug::interpose(ValueTs&&... xs)

Feeds the values passed as arguments in between the elements of the stream.

auto v   = std::vector<int>{1, 2, 3, 4, 5};
auto res = into_vector(interpose(42), v);
CHECK(res == (decltype(res){1, 42, 2, 42, 3, 42, 4, 42, 5}));

iter

template <typename InputRangeT, typename… InputRangeTs>

constexpr auto zug::iter(InputRangeT &&r, InputRangeTs&&... rs)

Generator transducer produces the sequence passed as parameter, by iterating over it.

auto v   = std::vector<int>{13, 42, 5};
auto res = into_vector(iter(v));
CHECK(res == (std::vector<int>{13, 42, 5}));

auto v1  = std::vector<int>{13, 42, 5, 6, 7};
auto v2  = std::vector<std::string>{"one", "two", "three"};
auto res = into_vector(iter(v1), v2);
CHECK(res == (decltype(res){{"one", 13}, {"two", 42}, {"three", 5}}));

mapcat

template <typename MappingT>

auto zug::mapcat(MappingT &&mapping)

Equivalent to cat | map(mapping).

auto v   = std::vector<std::vector<int>>{{1, 2}, {3}, {4, 5, 6}};
auto res = into_vector(mapcat([](int x) { return x * 2; }), v);
CHECK(res == (std::vector<int>{2, 4, 6, 8, 10, 12}));

map

template <typename MappingT>

constexpr auto zug::map(MappingT &&mapping)

Transforms every input using the mapping function.

auto v = std::vector<int>{1, 2, 3, 6};
auto r = into_vector(map([](int x) { return x * 2; }), v);
CHECK(r == decltype(r){2, 4, 6, 12});

map_indexed

template <typename MappingT>

constexpr auto zug::map_indexed(MappingT &&mapping)

Equivalent to count() | map(mapping).

auto v      = std::vector<std::string>{"1", "2", "3", "6"};
auto timesi = [](std::string x, std::size_t index) {
    return std::stoi(x) * static_cast<int>(index);
};
CHECK(transduce(map_indexed(timesi), std::plus<int>{}, 1, v) == 27);

partition

template <typename SizeT>

auto zug::partition(SizeT size)

Groups elements of the sequence in vectors of size elements.

auto v  = std::vector<int>{1, 2, 3, 4, 5, 6, 7};
auto r  = into_vector(partition(2u), v);
using t = std::vector<std::vector<int>>;
CHECK(r == t{{1, 2}, {3, 4}, {5, 6}, {7}});

partition_by

template <typename MappingT>

auto zug::partition_by(MappingT &&mapping)

Groups consecutive elements for which mapping(x) == mapping(y) in vectors.

auto v   = std::vector<int>{1, 1, 2, 4, 2, 3};
auto res = into_vector(partition_by([](int x) { return x % 2; }), v);
using t  = std::vector<std::vector<int>>;
CHECK(res == t{{1, 1}, {2, 4, 2}, {3}});

auto v   = std::vector<int>{1, 1, 2, 2, 2, 3};
auto res = into_vector(partition_by(identity), v);
CHECK(res == decltype(res){{1, 1}, {2, 2, 2}, {3}});

product

template <typename InputRangeT1, typename… InputRangeTs>

constexpr auto zug::product(InputRangeT1 &&r1, InputRangeTs&&... rs)

Transducer combines every element that passes by with every element in the range that it takes as argument. If multiple ranges are passed, it generates all combinations of elements from all of them.

auto v1  = std::vector<int>{1, 2};
auto v2  = std::vector<int>{3, 4};
auto res = into_vector(product(v2), v1);
using t  = std::vector<std::tuple<int, int>>;
CHECK(res == t{{1, 3}, {1, 4}, {2, 3}, {2, 4}});

auto v1  = std::vector<int>{1, 2};
auto v2  = std::vector<int>{3, 4};
auto v3  = std::vector<char>{'a', 'b'};
auto res = into_vector(product(v2, v3), v1);
using t  = std::vector<std::tuple<int, int, char>>;
CHECK(res == t{{1, 3, 'a'},
               {1, 3, 'b'},
               {1, 4, 'a'},
               {1, 4, 'b'},
               {2, 3, 'a'},
               {2, 3, 'b'},
               {2, 4, 'a'},
               {2, 4, 'b'}});

random_sample

template <typename ProbabilityT, typename GeneratorT = detail::default_generator>

auto zug::random_sample(ProbabilityT prob, GeneratorT gen = GeneratorT{})

Given a random number generator gen and a probability prob let’s elements through when gen() <= prob.

Similar to clojure.core/random-sample.

CHECK(transduce(range(20) | random_sample(0.5),
                std::plus<>{},
                std::size_t{}) == 100);

CHECK(transduce(range(20) | random_sample(1),
                std::plus<>{},
                std::size_t{}) == 190);

CHECK(transduce(range(20) | random_sample(0), //
                std::plus<>{},
                std::size_t{}) == 0);

range

template <typename StopT>

constexpr auto zug::range(StopT &&stop)

template <typename StartT, typename StopT>

constexpr auto zug::range(StartT &&start, StopT &&stop)

template <typename StartT, typename StopT, typename StepT>

constexpr auto zug::range(StartT &&start, StopT &&stop, StepT &&step)

Produces numbers in the range \( [start, stop) \) in steps of size \( step \). start and step are optional.

auto res = into_vector(range(3));
CHECK(res == std::vector<std::size_t>{{0, 1, 2}});

auto res = into_vector(range(2, 6));
CHECK(res == std::vector<int>{2, 3, 4, 5});

auto res = into_vector(range(2, 6, 2));
CHECK(res == std::vector<int>{2, 4});

auto s   = std::string{"hello"};
auto res = into_vector(range(2, 6, 2), s);
CHECK(res == std::vector<std::tuple<char, int>>{{'h', 2}, {'e', 4}});

readbuf

template <std::size_t N, typename InputStreamT>

auto zug::readbuf(InputStreamT &stream)

Generator transducer that reads buffers of size N from , and passes them into the sequence. It passes them into the sequence as an range with char* iterators.

auto as_str = map([](auto buf) {
    return std::string{buf.begin(), buf.end()};
});
auto stream = std::stringstream{"12345"};
auto res    = into_vector(readbuf<3>(stream) | as_str);
CHECK(res == std::vector<std::string>{"123", "45"});

template <typename InputStreamT>

auto zug::readbuf(InputStreamT &stream, std::size_t n)

Like readbuf(stream) but with runtime specified size.

auto as_str = map([](auto buf) {
    return std::string{buf.begin(), buf.end()};
});
auto stream = std::stringstream{"12345"};
auto res    = into_vector(readbuf(stream, 3) | as_str);
CHECK(res == std::vector<std::string>{"123", "45"});

read

template <typename T1, typename… Ts, typename InputStreamT>

auto zug::read(InputStreamT &stream)

Generator transducer that produces a sequence of values of type T read from the given stream using the operator >>. If more than one type is passed, it reads multiple values producing a T0, T1, ..., Tn on each step.

auto stream = std::stringstream{"1 2 3 4 5 6"};
auto res    = into_vector(read<int>(stream));
CHECK(res == std::vector<int>{1, 2, 3, 4, 5, 6});

auto stream = std::stringstream{"1 hello 2 my 3 friend 4 !!"};
auto res    = into_vector(read<int, std::string>(stream));
CHECK(res == std::vector<std::tuple<int, std::string>>{
                 {1, "hello"}, {2, "my"}, {3, "friend"}, {4, "!!"}});

remove

template <typename PredicateT>

auto zug::remove(PredicateT &&pred)

Removes elements that pass the predicate.

auto v      = std::vector<int>{1, 2, 3, 6};
auto times2 = [](int x) { return x * 2; };
auto odd    = [](int x) { return x % 2 == 0; };
auto res    = transduce(remove(odd) | map(times2), std::plus<int>{}, 1, v);
CHECK(res == 9);

repeat

template <typename ValueT, typename… ValueTs>

constexpr auto zug::repeat(ValueT &&r, ValueTs&&... rs)

Generator transducer produces the values passed as parameter infinitely.

auto res = into_vector(repeat('a') | take(3));
CHECK(res == (std::vector<char>{{'a', 'a', 'a'}}));

auto v   = std::vector<int>{1, 2, 3};
auto res = into_vector(repeat('a'), v);
CHECK(res == decltype(res){{1, 'a'}, {2, 'a'}, {3, 'a'}});

template <typename IntegralT, typename… ValueTs>

constexpr auto zug::repeatn(IntegralT &&n, ValueTs&&... rs)

Generator transducer produces the values passed as parameter up to n times.

auto res = into_vector(repeatn(3, 'a'));
CHECK(res == (std::vector<char>{{'a', 'a', 'a'}}));

replace

template <typename TableT>

auto zug::replace(TableT &&table)

Transducer that replaces elements by those in the table, a mapping providing a find() method returning an iterator comparable with end(). If an input is not found, it is left untouched in the sequence.

Similar to clojure.core/replace.

auto table = std::map<std::string, std::string>{{"hola", "adios"}};
auto v     = std::vector<std::string>{"hola", " ", "amigo"};
CHECK(transduce(replace(table), std::plus<>{}, std::string{}, v) ==
      "adios amigo");

template <typename TableT>

auto zug::replace_all(TableT table)

Transducer that replaces all elements by table[tuplify(inputs)].

auto table = std::map<std::string, int>{{"hola", 1}, {"amigo", 2}};
auto v     = std::vector<std::string>{"hola", " ", "amigo"};
CHECK(transduce(replace_all(table), std::plus<>{}, int{}, v) == 3);

template <typename TableT>

auto zug::replace_all_safe(TableT &&table)

Transducer that replaces all elements by table.at(tuplify(inputs))

auto table = std::map<std::string, int>{{"hola", 1}, {"amigo", 2}};
auto v     = std::vector<std::string>{"hola", "amigo"};
CHECK(transduce(replace_all_safe(table), std::plus<>{}, int{}, v) == 3);

auto table = std::map<std::string, int>{{"hola", 12}, {"amigo", 42}};
auto v     = std::vector<std::string>{"hola", "oops", "amigo"};
CHECK_THROWS_AS(transduce(replace_all_safe(table), std::plus<>{}, int{}, v),
                std::out_of_range);

sink

template <typename ActionT>

auto zug::sink(ActionT &&action)

Transducer that evaluates action on each input. The input is forwarded into the action and discarded. The next transducer is excited for every input, but with no arguments.

auto v = std::vector<int>{1, 2, 3, 6};
auto r = std::vector<int>{};
run(sink([&](int x) { r.push_back(x); }), v);
CHECK(v == r);

auto v = std::vector<int>{1, 42, 13, 6};
auto r = into_vector(sink([&](int x) {}) | enumerate, v);
CHECK(r == std::vector<std::size_t>{0, 1, 2, 3});

Note

This is very similar to each, but can perform better since the arguments can be moved into the action. If we are not interested in the inputs after the action, this one should be preferred.

scan

template <typename State, typename ReducingFunction>

constexpr auto zug::scan(State init, ReducingFunction rf)

For each input use the provided reducing function to combine items into a value that will be fed into the sequence. Inspired by rxcpp::operators::scan.

The reducing function may use the state interface that this library provide, allowing it to be combined with stateful transducers. The state is passed unwrapped into the sequence, so the state of the transducers is not visible into the outter stream. However, when the inner reduction completes, it completes the outter reduction as well.

auto v = std::vector<int>{1, 2, 3, 4, 5, 6};
auto r = into_vector(scan(0, std::plus<>{}), v);
CHECK(r == (std::vector<int>{1, 3, 6, 10, 15, 21}));

auto r = into_vector(count(1) | scan(0, take(6)(std::plus<>{})));
CHECK(r == std::vector<int>{1, 3, 6, 10, 15, 21});

take

template <typename IntegralT>

constexpr auto zug::take(IntegralT n)

Lets n elements through and finishes.

auto v   = std::vector<int>{1, 2, 3, 4, 5};
auto res = into_vector(take(3), v);
CHECK(res == std::vector<int>{1, 2, 3});

take_nth

template <typename IntegralT>

auto zug::take_nth(IntegralT nth)

Lets every nth elements of the sequence through.

Similar to clojure.core/take-nth.

auto v   = std::vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
auto res = into_vector(take_nth(3), v);
CHECK(res == std::vector<int>{1, 4, 7, 10});

take_while

template <typename PredicateT>

constexpr auto zug::take_while(PredicateT predicate)

Lets items through until the predicate does not pass, then stops.

auto v    = std::vector<int>{1, 2, 3, 4, 5};
auto pred = std::bind(std::less<>{}, _1, 4);
auto res  = into_vector(take_while(pred), v);
CHECK(res == decltype(res){1, 2, 3});

unzip

constexpr auto zug::unzip = comp(unzip_t{})

Transducer that expands all unzipable inputs into the sequence. Unzipable inputs are std::tuple, std::pair and std::array.

auto v = std::vector<std::tuple<int, int>>{{1, 10}, {2, 20}, {3, 30}};
auto r = into_vector(unzip | map(std::plus<>{}), v);
CHECK(r == std::vector<int>{11, 22, 33});

writebuf

template <typename OutputStreamT>

auto zug::writebuf(OutputStreamT &stream)

Generator transducer that writes buffers into the stream and passes them into the sequence. A buffer shall be a range with char* iterators. Lets n elements through and finishes.

auto v      = std::vector<std::string>{"123", "4", "56"};
auto stream = std::stringstream{};
run(writebuf(stream), v);
CHECK(stream.str() == "123456");

write

template <typename OutputStreamT, typename InSeparatorT, typename ArgSeparatorT>

auto zug::write(OutputStreamT &stream, InSeparatorT in_sep, ArgSeparatorT arg_sep)

Transducer that writes the into a given stream using the operator <<. It also forwards the values for further processing.

Note that in_sep and arg_sep are optional separators. The former is used to separate inputs, and the latter is used to spearate arguments of one single input. If arg_sep is not specified but in_sep is, the latter is used also to separate arguments. By default, no separator is used.

auto v      = std::vector<int>{1, 2, 3, 4};
auto stream = std::stringstream{};
run(write(stream), v);
CHECK(stream.str() == "1234");

auto v      = std::vector<int>{1, 2, 3, 4};
auto stream = std::stringstream{};
run(write(stream, ' '), v);
CHECK(stream.str() == "1 2 3 4");

auto v1     = std::vector<int>{1, 2, 3, 4};
auto v2     = std::vector<char>{'y', 'e', 'a', 'h'};
auto stream = std::stringstream{};
run(write(stream, ' '), v1, v2);
CHECK(stream.str() == "1 y 2 e 3 a 4 h");

auto v1     = std::vector<int>{1, 2, 3, 4};
auto v2     = std::vector<char>{'y', 'e', 'a', 'h'};
auto stream = std::stringstream{};
run(write(stream, ' ', ','), v1, v2);
CHECK(stream.str() == "1,y 2,e 3,a 4,h");

zip

constexpr auto zug::zip = map(tuplify)

Transducer that, if more than one argument is passed, forwards all of them as a single tuple.

auto v1  = std::vector<int>{13, 42, 5};
auto v2  = std::vector<double>{1.1, 2.2, 3.3};
auto res = transduce(
    zip,
    [](double x, std::tuple<int, double> t) {
        return x + std::get<0>(t) + std::get<1>(t);
    },
    1.0,
    v1,
    v2);
CHECK_THAT(res, Catch::Matchers::WithinAbs(67.6, 0.001));