haskell - 换能器与部分应用函数有何不同？

Question

在阅读了这篇关于 Clojure (http://blog.podsnap.com/ducers2.html) 介绍传感器的文章后，我对传感器是什么感到困惑。是部分应用 map在 Haskell 中，例如 map (+1)换能器？起初我认为这是使用部分应用程序的 Clojure 方式，但随后文章继续在 Haskell 中使用显式类型实现它。它在 Haskell 中有什么用？

Answer 1

在 Clojure (map inc)是一个转换器，但在 Haskell 中不是，因为 Haskell 必须遵守柯里化(Currying)，但无类型的 Lisp 可以打破默认柯里化(Currying)的约定。换能器的类型是:

type Transducer a b = forall r . (b -> r -> r) -> (a -> r -> r)

我们说换能器'转a进入 b '。是的，a和 b在右侧看起来“向后”。 forall表示 Transducer 必须离开 r作为通用类型变量，但完全允许专门化 a和 b .

让我反转 foldr 中的两个论点:

-- cf. with foldr :: (x -> r -> r) -> r -> [x] -> r
ffoldr :: (x -> r -> r) -> [x] -> r -> r
ffoldr = flip . foldr

(我们也可以使用foldl，但它会在稍后扭转局面)。这意味着 Transducer可用于转换 ffoldr 的第一个参数来自 x至y , 这样我们就可以处理 [x]与 y -> r -> r使用 foldr .传感器“位于”输入之间 ([x], r)和最终处理器 (y, r) -> r .

我翻转了后两个论点来强调，令人惊讶的是，ffoldr :: Transducer [x] x .通过使用参数的对称性，我们还有一个通用的转换器组合，它恰好是函数组合:

(.) :: Transducer a b -> Transducer b c -> Transducer a c

(如果您认为给出这些 forall r 术语让我们反转您通常使用 . 的方式很酷，您可以通过一种称为“连续传递”的技术任意做到这一点。)

例如，这是滤波器转换器:

tfilter :: (a -> Bool) -> (a -> r -> r) -> a -> r -> r 
    -- or: (a -> Bool) -> Transducer a a
tfilter predicate f a = if predicate a then f a else id

这应用了归约函数 f至a和 r仅当谓词成立时。还有一个映射转换器:

tmap :: (a -> b) -> (b -> r -> r) -> a -> r -> r 
tmap ba f a = f (ba a)

这为任何“可转换”类型提供了可组合的映射/过滤器语义:一个映射/过滤器 fn 可以用于多个上下文。

Transducer 类型有一个可爱的同构:foldr列表中的 forall r. (x -> r -> r) -> r -> r完全等同于该列表 [x] (它是该列表的“Church 编码”)，因此交换参数 a转换器定义的最前面为我们提供(IMO 更容易理解!)类型 type TransL a b = a -> [b] .这更容易理解:

tl_map f = \a -> [f a]
tl_filter predicate = \a -> if predicate a then [a] else []

要在列表上运行这些，请使用 concatMap ...恰好是 >>= !所以你只需写collection >>= transducer你有转导的集合。 TransL a b的含义然后，“取 a 的原始列表中的每个元素，并给我 0 个或多个 b 类型的元素以拼接到我的传出列表中。”当谓词不起作用时，它通过拼接0个元素进行过滤；它通过为每个输入元素产生 1 个输出元素来映射；另一个操作 tl_dupe = \a -> [a, a]是一个转换器，它复制列表中的元素，[1,2,3] >>= tl_dupe变成 [1,1,2,2,3,3] .

在哪里 foldr似乎是 Transducer [x] x现在可以看到它与 id :: TransL [x] x 相同它可以简单地执行 concat计算中间的操作；这个代数中的恒等函数实际上是 return = \a -> [a] ，也写成 (:[]) . 仅限 损失是我们不能再使用 .组成这些，但实际上 Control.Monad 中提供了相同的组成作为 Kleisli 组合运算符 >=> .

长话短说，传感器是函数a -> [b]巧妙地用一点 Church 编码进行转换，使得列表 monad 的这些 Kleisli 箭头的 Kleisli 组合运算符变为简单的 (.) .