Haskell Arrow延迟功能

Question

我正在阅读John Hughes的Arrows编程.有一段我真的无法理解的代码.代码如下:

import Control.Arrow.Operations 
import Control.Arrow
import Control.Category
import Prelude hiding ((.),id)

newtype SF a b = SF {runSF :: [a] -> [b]}

instance Category SF where
         id = SF id
         (.) (SF f) (SF g) = SF $ \x -> f (g x)

(.*.) :: (a -> b) -> (c -> d) -> (a,c) -> (b,d)
(.*.) f g (a,c) = (f a, g c)


instance Arrow SF where
         arr f = SF (map f)
         first (SF f) = SF  (uncurry zip . (f .*. id) . unzip)

instance ArrowLoop SF where
         loop (SF f) = SF $ \as -> let (bs,cs) = unzip (f (zip as (stream cs))) in bs
                                       where stream ~(x:xs) = x:stream xs
instance ArrowChoice SF where
     left (SF f) = SF (\xs -> combine xs (f [y | Left y <- xs]))
          where combine (Left y: xs) (z:zs) = Left z : combine xs zs
                combine (Right y :xs) zs = Right y : combine xs zs
                combine [] zs = [] 

instance ArrowCircuit SF where
         delay x = SF (x:)

然后

mapA :: ArrowChoice arr => arr a b -> arr [a] [b]

listcase []     = Left ()
listcase (x:xs) = Right (x,xs)

mapA f = arr listcase >>>
         arr (const []) ||| (f *** mapA f >>> arr (uncurry (:)))

我无法理解的是

> runSF (mapA (delay 0)) [[1,2,3],[4,5],[6],[7,8],[9,10,11],[12,13,14,15]]
[[0,0,0],[1,2],[4],[6,5],[7,8,3],[9,10,11,0]]

我认为结果应该只是添加一个0在每个列表的头部,因为delay 0定义为SF (0:).

更奇怪的是,

diag :: (ArrowCircuit a , ArrowChoice a) => a [b] [b]
diag = arr listcase >>> 
       arr (const []) ||| (arr id *** (diag >>> delay []) >>> arr (uncurry (:)))

runSF diag [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]
[[1],[4,2],[7,5,3],[10,8,6]]

我可以看到是什么diag和mapA (delay 0)做什么,但我不能完全理解使用的计算过程delay.有人可以帮忙吗？谢谢.

Answer 1

考虑箭头的一种方法是作为某种工厂图.如果你SF是公正的,那你就是对的(->).继续尝试; 你应该得到:

Prelude Control.Arrow> mapA (0 :) [[1,2,3],[4,5],[6],[7,8],[9,10,11],[12,13,14,15]]
[[0,1,2,3],[0,4,5],[0,6],[0,7,8],[0,9,10,11],[0,12,13,14,15]]

然而,工厂的机器可以做的事情比简单地发送转换后的输入更复杂,方式->有效.你的SF机器"接收" a并"熄灭"a b,但是它们由一个功能支持,[a] -> [b]它允许你为它们提供一个流,a然后它们可以做一些比这更复杂的事情->.

所以delay 0机器需要一个数字流,并在其前面加上0,如果你想以这样的方式考虑它,那就很容易让原始流"落后"一个"时间步".

类似地,a1 &&& a2机器必须将其输入流馈送到两个子机器,并且当它们都具有值时,它可以将它们"压缩"在一起.它使用它的子机[b] -> [c]和[b] -> [d]对生产[b] -> [(c, d)],毕竟.

该a1 ||| a2机器是相当棘手:它需要相似的子机[b] -> [d]和[c] -> [d]并用它们来形成[Either b c] -> [d].如果看起来完全不言自明,再看一遍!我们没有Either [b] [c],这本来就是完全直截了当(而且是->上面涉及的内容),而是[Either b c].这里做的明显的解决方案是:

1. 抓住左子列表,将其提供给左侧机器
2. 抓住右侧子列表,将其提供给正确的机器
3. [d]以一些复杂的交错顺序返回结果s.

什么顺序？最简单的方法是返回原始列表,每当看到左侧时,d从左侧机器列表中产生一个; 每当你看到一个右边,d从右边的列表中产生一个.

有了这些背景,我们来mapA:

mapA f = arr listcase >>> arr (const []) ||| (f *** mapA f >>> arr (uncurry (:)))

因为SF,listcase将采用传入的列表流并生成一个流Either () (x, [x]),具体取决于该流是否为空.在第一次通过列表时,您的所有条目runSF都是空的,因此每个列表都是一个Right发出一个正确值的分支.

所以我们[Right (1, [2,3]), Right (4, [5]), Right (6, []), ...]得到了扁平化并分成两个列表:[1, 4, 6, ...]和[[2,3], [5], [], ...].

第一个列表被输入到延迟函数中,因此它被添加到前面0.第二个列表被递归地输入mapA f,因此[2,5]前缀也被延迟; 等等.

最后,当您将它们连接在一起时,您会发现列表中的每个嵌套级别都已延迟,因此第一个发出的列表为[0,0,0],第二个为[1,2].