35

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

4

1 回答 1

46

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

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

我们说换能器“变成a” b。是的，右边的a和似乎“倒退”。b这forall意味着 Transducer 必须保留r为通用类型变量，但完全允许专注于aand b。

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

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

（我们也可以使用foldl，但它会在以后扭转事情）。这意味着 aTransducer可用于将ffoldrfrom的第一个参数转换x为y，以便我们可以使用 a 来处理[x]a y -> r -> rusing 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列表的(IMO 更容易理解！) 类型。这更容易理解：forall r. (x -> r -> r) -> r -> r[x]atype 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].

wherefoldr似乎是 aTransducer [x] x现在看来与id :: TransL [x] xwhich 相同，可以在计算过程中简单地执行concat操作；这个代数中的恒等函数实际上return = \a -> [a]也是写(:[])的。唯一的损失是我们不能再用它.来组合这些，但实际上与Control.MonadKleisli 组合运算符一样提供了相同的组合>=>。

长话短说，transducer 是a -> [b]通过一点 Church 编码巧妙转换的函数，因此列表单子的这些 Kleisli 箭头的 Kleisli 组合运算符变得简单(.)。

于 2014-10-30T22:05:46.580 回答