Haskell Arrow延迟功能

Question

我正在阅读John Hughes的用箭头编程。有一段我实在无法理解的代码。代码如下：

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机器需要一串数字并将其前置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]。