换能器与部分应用的功能有何不同？

Question

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

Answer 1

在Clojure中(map inc)是一个传感器,但不在Haskell中,因为Haskell必须遵守currying,但是一个无类型的Lisp可以打破默认的咖喱惯例.换能器的类型是:

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

我们说,传感器"转a成b".是的,a和b似乎"向后"在右手边.在forall一个传感器必须离开手段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)

这为任何"transducable"类型提供了可组合的map/filter语义:一个map/filter fn可以用于多个上下文.

传感器类型具有可爱的同构性:事实证明foldr列表forall r. (x -> r -> r) -> r -> r的完全等同于该列表[x](它是该列表的"教会编码"),因此将参数交换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]巧妙地用一些教会编码转换的功能,因此列表monad的这些Kleisli箭头的Kleisli合成运算符变得简单(.).