Haskell Arrow延迟函数

Question

我在看约翰休斯的节目。有一段代码我真的无法理解。守则如下：

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流，然后它们可以做一些比->更复杂的事情。

因此，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]。

什么命令？最简单的方法是返回原始列表，每当您看到左侧时，从左边机器的列表中生成一个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。