Haskell Arrow延遲功能

我正在閱讀John Hughes的用箭頭編程。有一段我實在無法理解的代碼。代碼如下：Haskell Arrow延遲功能

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計算過程。有人可以幫忙嗎？謝謝。

來源

2015-02-09 Song Zhang

要了解您真正需要了解'ArrowChoice'，特別是您未包含在代碼中的'ArrowChoice SF'實例。 'mapA'僅適用於具有'ArrowChoice'實例，'mapA :: ArrowChoice a => a b c - > a [b] [c]'的箭頭。 'diag'中的'|||'是'Arrow'的'&&&'的'ArrowChoice'類似物。 – Cirdec 2015-02-09 07:10:26

抱歉忽略了ArrowChoice，我添加了它。這對您的評論很有幫助。謝謝〜 – 2015-02-10 00:35:00

思考箭的一種方法就像某種工廠圖。如果您的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]。對於在這裏做什麼明顯的解決方案是：

抓住左子列表，它提供給左側機
抓住右子列表，它提供給合適的機器
以一些複雜的交錯順序返回結果[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]。

來源

2015-02-09 19:59:24

您的回答非常有幫助。我會再次查看類型類的定義！非常感謝 – 2015-02-10 00:56:45

Haskell Arrow延遲功能

回答

相關問題