Haskell 箭头延迟函数

Question

我正在阅读 John Hughes 的 Programing with 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并“输出”一个 b , 但它们由函数 [a] -> [b] 支持这让您可以向他们提供 a 的流s 然后他们可以做一些比 -> 更复杂的事情。做。

所以 delay 0 machine 需要一个数字流并在其前面加上 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] .在这里做什么的明显解决方案是:

抓取left-sub-list，提供给左机

抓取右子列表，提供给正确的机器

返回结果 [d] s 以某种复杂的交错顺序排列。

什么顺序？最简单的方法是返回原始列表，每当您看到 Left 时，产生 d从左侧机器的列表中；每当你看到一个 Right 时，产生一个 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]。