Scala Transducers和Clojure Transducers之间有哪些相似之处和不同之处？

Question

Paul Chiusano和Rúnar Óli写了一本很棒的书Scala函数式编程。他们在书中提到了一个在Scala社区中鲜有人谈及的概念 - Transducers。

在Clojure社区中，转换器受到了一些 更多的 关注。

我的问题是：Scala Transducers（来自Scala函数式编程书籍）和Clojure Transducers之间有哪些相似之处和不同之处？ 假设： 我知道

1. 转换器是电气工程中的常用术语（点击链接查看）

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

3. 在生物学和心理学中，有一个先例采用了单词转导（点击链接查看）

4. 已经有一些技术书籍（点击链接查看）采用了类似于《SICP》的其他技术书籍使用单词转换器（点击链接查看）。

- hawkeye

Answer 1

我将为您翻译编程相关内容。以下是需要翻译的文本：

来自Scala函数式编程（FPiS）和Clojure的transducers的流转换器非常相似。它们是将“机器”（步骤函数）用于处理输入流以生成输出流的想法的一般化。FPiS的转换器称为Processes。Rich Hickey在他关于Clojure中transducers的介绍性演讲中也使用了术语process。

起源

FPiS转换器的设计基于Mealy机器。据说Mealy机器具有以下特点：

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

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

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

在这里，很容易看出步进函数作用于机器的当前状态和下一个输入项，以产生机器的下一个状态和输出项。

FPiS中的组合器之一使用了这样的步进函数：

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

这个loop函数本质上就是Rickey在这张幻灯片中提到的种子左规约。

与上下文无关

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

在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的表示形式不仅仅是底层函数。它是一个带有三个变量（等代数数据类型）的案例类：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函数的角色。
• Halt扮演Clojure中的reduced的角色。
• Emit代替在Clojure中调用下一步函数。

提前终止

两者都支持提前终止。Clojure使用了一个特殊的值叫做reduced，可以通过reduced?谓词进行测试。

FPiS使用了一种更静态类型的方法，Process可以处于三种状态之一：Await，Emit或Halt。当"步骤函数"返回一个状态为Halt的进程时，处理函数知道要停止。

效率

在某些方面，它们又很相似。两种类型的转换器都是按需驱动的，并且不生成中间集合。然而，我想象FPiS的转换器在管道/组合时不像内部表示那样高效，因为其转换器的内部表示方式不仅仅是"只是一个函数调用的堆栈", Hickey如此描述。不过，关于效率/性能，这只是我的猜测。

请查看 fs2（以前称为scalaz-stream）了解一种基于FPiS中transducers设计的、可能更高效的库。

示例

以下是两个实现中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，数据库结果）
• 需求驱动/提前终止
• 完成/结束（为了资源安全性）
• tasty :)

它们在底层表示上略有不同。Clojure风格的变换器似乎更注重效率，而FPiS变换器则更注重正确性和组合性。

- Steven Shaw

Answer 2

我不是很熟悉Scala中转换器的概念，也不知道这个术语有多普遍，但从您上面发布的文本片段和我的转换器知识来看，我可以说：

• 它们非常不同
• 它们只在一个方面相似，即它们都与如何将一个集合转换为另一个集合相关

关于Scala转换器的说明：

从上面的定义中可以看出，任何具有类似以下签名的函数或可调用对象：

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的转换器是用于流（而不是其他Scala集合）的集合处理函数，而Clojure的转换器实际上是一种机制，用于统一不同集合类型的集合处理函数的实现。因此，可以这样说：如果Scala有Clojure的转换器概念，那么Scala的转换器概念可以基于Clojure的转换器概念实现，后者是更抽象/通用的可重复使用于多个集合类型的处理函数。

- metasoarous