9

Paul Chiusano和Rúnar Óli写了一本很棒的书《Scala 函数式编程》。在其中，他们提到了 Scala 社区中一个很少被引用的概念——Transducers。

Scala 中的函数式编程一书中的 Scala 转换器

在 Clojure 社区中，Transducers得到了更多的 关注 。

我的问题是： Scala Transducers **（来自《Scala 中的函数式编程》一书）和 Clojure Transducers之间有什么异同？**

假设：

我知道

  1. 换能器是电气工程概念中的常见说法

  2. 计算机科学中有一个预先存在的概念，称为有限状态传感器

  3. 生物学和心理学有先例采用转导一词

  4. 其他技术书籍（如SICP）已经采用Transducers这个词的历史。

4

2 回答 2

11

Function Programming in Scala (FPiS)一书中的流转换器和 Clojure 的转换器非常相似。它们是使用“机器”（阶跃函数）将输入流处理成输出流的概念的概括。FPiS 的传感器称为Processes。Rich Hickey在他关于 Clojure 中的传感器的介绍性演讲中也使用了过程这个术语。

起源

FPiS 传感器的设计基于Mealy 机器。据说 Mealy 机器具有：

transition function T : (S, I) -> S
output function     G : (S, I) -> O

这些函数可以融合在一起形成：

step: (S, I) -> (S, O)

这里很容易看出，step 函数对机器的当前状态和下一个输入项进行操作，以产生机器的下一个状态和输出项。

FPiS 中的一个组合器使用了这样一个阶跃函数：

trait Process[I, O] {
  ...
  def loop[S, I, O](z: S)(f: (I,S) => (O,S)): Process[I, O]
  ...
}

这个函数本质上是 Rickey在这张幻灯片中loop谈到的种子左缩减。

上下文不可知论

两者都可以在许多不同的上下文中使用（例如列表、流、通道等）。

在 FPiS 传感器中，过程类型为：

trait Process[I, O]

它所知道的只是它的输入元素和输出元素。

在 Clojure 中，情况类似。Hickey 称之为“完全解耦”。

作品

两种类型的换能器都可以组合。

FPiS 使用“管道”运算符

map(labelHeavy) |> filter(_.nonFood)

Clojure 使用comp

(comp
  (filtering non-food?)
  (mapping label-heavy))

表示

在 Clojure 中：

reducer:    (whatever, input) -> whatever
transducer: reducer -> reducer

在 FPiS 中：

// The main type is
trait Process[I, O]

// Many combinators have the type
Process[I, O] ⇒ Process[I, O]

然而，FPiS 的表示不仅仅是底层的功能。它是具有 3 个变体的案例类（代数数据类型）：Await、Emit 和 Halt。

case class Await[I,O](recv: Option[I] => Process[I,O])
case class Emit[I,O](head: O, tail: Process[I,O]
case class Halt[I,O]() extends Process[I,O]
  • Await 扮演 Clojure 的 reducer->reducer 函数的一部分。
  • Haltreduced在 Clojure 中扮演角色。
  • Emit 代替调用 Clojure 中的下一步函数。

提前终止

两者都支持提前终止。Clojure 使用一个reduced可以通过reduced?谓词进行测试的特殊值来执行此操作。

FPiS 使用更静态类型的方法，进程可以处于 3 种状态之一：Await、Emit 或 Halt。当“步进函数”返回状态为 Halt 的过程时，处理函数知道停止。

效率

在某些方面，它们再次相似。这两种类型的转换器都是需求驱动的，不会生成中间集合。但是，我认为 FPiS 的转换器在流水线/组合时效率不高，因为内部表示不仅仅是 Hickey 所说的“只是一堆函数调用”。我只是在这里猜测效率/性能。

查看fs2（以前scalaz-stream）寻找基于 FPiS 中的传感器设计的可能性能更高的库。

例子

filter这是两种实现的示例：

Clojure，来自 Hickey 的演讲幻灯片：

(defn filter
  ([pred]
    (fn [rf]
      (fn
        ([] (rf))
        ([result] (rf result))
        ([result input]
          (if (prod input)
            (rf result input)
            result)))))
  ([pred coll]
    (sequence (filter red) coll)))

在 FPiS 中，这是实现它的一种方法：

def filter[I](f: I ⇒ Boolean): Process[I, I] =
  await(i ⇒ if (f(i)) emit(i, filter(f))
            else filter(f))

如您所见，filter这里是从其他组合子（例如await和）构建的emit。

安全

在实现 Clojure 转换器时，有许多地方必须小心。这似乎是一种有利于效率的设计权衡。然而，这种不利因素似乎主要影响图书馆生产者，而不是最终用户/消费者。

  • 如果转换器reduced从嵌套的步骤调用中获取值，则它绝不能再次使用输入调用该步骤函数。
  • 需要状态的转换器必须创建唯一的状态，并且不能有别名。
  • 所有阶跃函数都必须具有不接受输入的 arity-1 变体。
  • 转换器的完成操作必须调用其嵌套的完成操作，恰好一次，并返回它返回的内容。

FPiS 的换能器设计有利于正确性和易用性。管道组成和flatMap操作确保完成动作迅速发生，错误得到适当处理。这些问题对转换器的实现者来说不是负担。也就是说，我认为该库可能不如 Clojure 库那么高效。

概括

Clojure 和 FPiS 传感器都具有：

  • 相似的起源
  • 能够在不同的上下文中使用（列表、流、通道、文件/网络 io、数据库结果）
  • 需求驱动/提前终止
  • 最终确定/完成（为了资源安全）
  • 好吃:)

它们的基本表示方式有所不同。Clojure 风格的转换器似乎有利于效率，而 FPiS 转换器有利于正确性和组合性。

于 2016-05-14T05:25:58.787 回答
1

我对 Scala 的换能器概念或该术语的普遍性并不是特别熟悉，但从您在上面发布的文本片段（以及我对换能器的知识）来看，我可以说：

  • 他们非常不同
  • 它们的相似之处仅在于它们都与一个集合如何转换为另一个集合有关

关于 Scala Transducers，我能说些什么：

从上面的定义看来，任何带有签名的函数或可调用的函数都大致沿着

Stream[A] -> Stream[B]

因此，例如，在这种情况下，处理流的映射函数将被视为转换器。

而已; 真的很简单。

Clojure 传感器：

Clojure转换器是将一个归约函数转换为另一个的函数。归约函数是可以与reduce一起使用的函数。也就是说，如果 Clojure 有签名，它就会有一个签名

(x, a) -> x

在英语中，给定一些起始集合x，并且集合中的“下一件事”a被归约，我们的归约函数返回“正在构建的集合的下一次迭代”。

所以，如果这是一个归约函数的签名，一个转换器有签名

((x, a) -> x) -> ((x, b) -> x)

转换器被添加到 Clojure 的原因是，通过添加或core.async通道，Rich Hickey 和他的朋友们发现他们重新实现了所有标准集合函数以使用通道（map、filter、take等）。RH 想知道这里是否有更好的方法，然后开始思考如何从手头的集合类型机制中解构这些各种集合处理函数的逻辑。然而，我认为准确解释传感器如何做到这一点超出了这个问题的范围，所以我会回到正题。但如果你有兴趣，有很多关于这方面的文献很容易找到和研究。

那么这些东西有什么关系呢？

显然，这些是非常不同的概念，但我是这样看待它们的：

虽然 Scala 转换器是 Streams 的集合处理函数（与其他 Scala 集合相对），但 Clojure 的转换器实际上是一种跨不同集合类型统一集合处理函数实现的机制。因此，一种说法是，如果 Scala 具有 Clojure 的转换器概念，Scala 的转换器概念可以根据 Clojure 的转换器概念来实现，后者是更抽象/通用的处理函数，可重用于多种集合类型。

于 2015-01-08T21:47:51.610 回答