Funzione di ritardo della freccia di Haskell

Question

Sto leggendo la programmazione di John Hughes con le frecce. C'è un pezzo di codice che non riesco davvero a capire. Il codice è il seguente:

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:) 

e poi

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 (:))) 

Quello che non riesco a capire è che

> 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]] 

ho pensato che il risultato dovrebbe essere solo l'aggiunta di un 0 a capo di ogni l'elenco dal delay 0 è definito come SF (0:).

E ancora più strano,

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]] 

posso vedere quali sono diag e mapA (delay 0) fare, ma non riesco a capire il processo di calcolo con l'utilizzo di delay. Qualcuno può aiutarti? Grazie.

Answer 1

Un modo per pensare alle frecce è come una sorta di diagramma di fabbrica. Avresti ragione se il tuo SF fosse solo (->). Vai avanti e provalo; si dovrebbe ottenere:

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]] 

Tuttavia, le macchine in fabbrica possono fare le cose più complicate che semplicemente inviando il loro contributo trasformato, il modo in cui -> opere. Le tue macchine SF "prendono" un a e "mettono fuori" un b, ma sono supportate da una funzione [a] -> [b] che ti consente di dar loro un flusso di a s e quindi possono fare qualcosa di più sofisticato di ->.

Quindi la macchina delay 0 prende un flusso di numeri e ne antepone uno 0, facilmente pacchiano, "ritardando" il flusso originale di un "passo temporale" se si vuole pensarlo in quel modo.

Analogamente la macchina a1 &&& a2 dovrà alimentare il proprio flusso di input su entrambe le macchine secondarie e, quando entrambi hanno dei valori, può "comprimerle" insieme. Usa le sue sub-macchine [b] -> [c] e [b] -> [d] per produrre [b] -> [(c, d)], dopotutto.

Il a1 ||| a2 macchina è più complicato: ci vuole simili secondarie macchine [b] -> [d] e [c] -> [d] e li utilizza per formare [Either b c] -> [d]. Se quello sembrava completamente auto-esplicativo, guarda di nuovo! Non avevamo Either [b] [c], che sarebbe stato del tutto semplice (ed è ciò che tratta -> sopra), ma piuttosto [Either b c]. La soluzione più ovvia per quello da fare qui è:

1. Grab sinistra-sotto-list, forniscono alla macchina sinistra
2. Afferra il diritto-sub-list, forniscono alla macchina giusta
3. Restituire i risultanti [d] s in qualche complicato ordine interfogliato.

Quale ordine?Il modo più semplice consiste nel tornare indietro nell'elenco originale e, ogni volta che si vede una sinistra, produrre un d dall'elenco della macchina a sinistra; ogni volta che vedi un diritto, produci uno d dall'elenco a destra.

Con tutte queste premesse, veniamo mapA:

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

Per SF, il listcase prenderemo il flusso in entrata di liste e di produrre un flusso di Either() (x, [x]), a seconda che tale flusso è vuoto. Nel primo passaggio nell'elenco, nessuna delle voci nel tuo runSF è vuota, quindi ogni elenco è un ramo Right che emette un valore corretto.

Quindi abbiamo [Right (1, [2,3]), Right (4, [5]), Right (6, []), ...] che viene appiattito e diviso in due elenchi: [1, 4, 6, ...] e [[2,3], [5], [], ...].

Questo primo elenco viene inserito nella funzione di ritardo, quindi viene anteposto allo 0. Il secondo elenco viene alimentato in modo ricorsivo in mapA f, quindi anche i prefissi [2, 5] vengono ritardati; e così via.

Alla fine quando vi unite a loro, scoprirete che ogni livello di nidificazione nelle liste è stato ritardato, in modo che la prima lista emessa sia [0, 0, 0] e la seconda sia [1, 2].