Lib.rs

› Rust 模式
#transducer #channel #higher-order #stream #applications #iterator #clojure

rs_transducers

Rust 中 transducer 的实现

作者：Ben Ashford

3 个版本

使用旧的 Rust 2015

0.0.3 2016 年 5 月 22 日
0.0.2 2016 年 5 月 18 日
0.0.1 2016 年 5 月 2 日

#1326 在 Rust 模式 中

MIT/Apache

43KB
1K SLoC

rs-transducers

Build Status

在 Rust 中尝试实现 Clojure 风格的 transducer

什么是 transducer？

当第一次引入 Clojure 时，transducer 的概念引起了很多混淆。最佳的概述是Clojure 参考的一部分。

本质上，transducer 将函数应用于数据与数据结构分离。例如，像 map 这样的高阶函数可以表达为可以应用于向量、迭代器，甚至包含线程间传递数据的通道。

此库包含两部分

  1. 一组常见的 transducer。
  2. 那些 transducer 的应用实现。

在两种情况下，这些集合都可以扩展。可以定义自定义 transducer，并且可以将 transducer 应用于任何自定义数据结构或流。

警告：由于简化，可能存在一些混乱的术语。在开发的这个早期阶段，我愿意纠正这些术语，即使这意味着重命名库的很大一部分。

Transducers

一个过滤奇数的 transducer 示例

extern crate rs_transducers;

use rs_transducers::transducers;
use rs_transducers::applications::vec::Into;

let source = vec![1, 2, 3, 4, 5];
let transducer = transducers::filter(|x| x % 2 == 0);
println!(source.transduce_into(transducer));

这将打印：[2, 4]。

transducer 可以组合，因此复杂的 map/filter 等. 操作可以简单地表达。

let transducer = rs_transducers::compose(transducers::drop(5),
                                         transducers::filter(|x| x % 2 == 0));

提供的 transducer

map - 接受一个类型为 Fn(I) -> O 的函数，并返回一个实现 Transducer<I, O> 的 MapTransducer。还有 map_indexed，它接受一个类型为 Fn(usize, I) -> O 的函数。

mapcat - 接受一个类型为 Fn(I) -> OI 的函数，其中 OI 实现 IntoIterator<Item=O>，并返回一个实现 Transducer<I, O> 的 MapcatTransducer。

filter 和 remove - 接受一个类型为 Fn(I) -> bool 的函数，并返回一个实现 Transducer<I, I> 的 FilterTransducer。 filter 保留符合条件的数据，而 remove 则相反。

keep - 接受一个类型为 Fn(I) -> Option<O> 的函数，并返回一个产生所有 O 的 KeepTransducer。还有 keep_indexed，它接受一个类型为 Fn(usize, I) -> Option<O> 的函数。

partition 和 partition_all - 接受一个确定每个分区大小的 usize，并返回一个实现 Transducer<I, Vec<I>> 的 PartitionTransducer。两者的区别在于 partition_all 将返回一个不完整的最终分区，而 partition 则不会。还有 partition_by，它会根据提供的函数返回相同的值将数据分组在一起。

take 和 drop - 接受一个 usize，并返回一个实现 Transducer<I, I> 的转换器，该转换器将取或删除适当数量的元素。

take_while 和 drop_while - 当谓词保持为真时取或删除值。

replace - 接受一个 HashMap<T, T>（其中 T 必须实现 Clone）并返回一个将给定键的每个实例替换为相应值的克隆的 ReplaceTransducer。

interpose - 接受一个可克隆的值 T，并返回一个转换器，当应用时，会在每个通过减少函数的值之间插入该值。

dedupe - 删除连续重复的项。

这里未实现的唯一一个 clojure.core 转换器是 random-sample，这是因为我在尝试避免从这个包中引入所有依赖。然而，在任何应用程序中实现这样的转换器都是非常简单的。

实现转换器

这个库的初始版本试图通过提取“归约函数”的需求来简化对转换器的理解（请参阅Clojure文档中这些术语的定义）。由于没有这样的函数，我们实际上并没有转换器，而只是可以用于类似目的的东西。但很快就很明显，归约函数和转换器都是需要的；这是因为这是某些转换器（例如 mapcat）能够应用于某些事物（例如通道）的唯一方式。

因此，实现一个转换器需要实现两个特质：为转换器本身实现 Transducer，为转换器返回的归约函数实现 Reducing。

转换器

待定

归约

待定

应用

转换器需要应用于数据源才能产生效果。初始示例使用了 Into 特质，将 transduce_into 添加到向量中；正如其名所示，这类似于 into_iter()，它消耗原始数据，应用转换器并返回一个新的向量。

提供的应用

到目前为止实现的是以下转换器应用：

Vec<T>

这有两种形式 Into，它向向量添加一个 transduce_into，这会消耗原始向量；以及 Ref 特质，它向向量添加 transduce_ref，这不会改变原始向量，而是根据通过转换器传递到源数据的引用返回一个新的向量。

迭代器

特质 TransduceIter 向迭代器添加一个 transduce，它返回一个新的迭代器。

通道

与仅定义在迭代器上的操作不同，转换器可以应用于任何数据序列，包括线程之间通过通道的数据流。

由于Rust的通道是具体的 Sender 和 Receiver 类型，而不是实现任何特质，我们无法实现这些通道之一（如果不是创建两对通道，但这需要额外的线程来在它们之间传递消息）。因此，我们用一个新的 TransducingSender 包装 Sender 类型。

例如（来自测试）

let transducer = super::compose(transducers::partition_all(6),
                                transducers::filter(|x| x % 2 == 0));
let (mut tx, rx) = transducing_channel(transducer);
thread::spawn(move|| {
    for i in 0..10 {
        tx.send(i).unwrap();
    }
    tx.close().unwrap();
});
assert_eq!(vec![0, 2, 4, 6, 8], rx.recv().unwrap());

实现应用

任何自定义数据结构/通道/序列等都可以应用转换器。

为了做到这一点，需要提供一个 Reducing 的实现，以构建所需的数据结构。然后

  1. 通过将其传递给转换器的 new 函数，返回一个新的归约函数。
  2. 在归约函数上调用 init。
  3. 对每条数据调用 step。
  4. 最后调用 complete。

保留对构建的数据结构的访问是实现的职责。

许可

许可方式为以下之一

根据您的选择。

贡献

除非您明确表示，否则根据 Apache-2.0 许可证定义的，您有意提交以包含在作品中的任何贡献，将按上述方式双重许可，不附加任何额外条款或条件。

无运行时依赖