In che modo mapA funziona con una freccia della funzione di flusso in Haskell?

Question

Sfondo

Vado attraverso John Hughes' Programming with Arrows, e ho sentito che avevo tutto dritto nella mia testa fino a quando il seguente esempio di utilizzo MAPA:

>runSF (mapA (delay 0)) [[1,2,3],[4,5,6],[7,8,9]] 
[[0,0,0],[1,2,3],[4,5,6]] 

Dove runSF estrae la funzione di corrente dalla freccia funzione di corrente definita come:

newtype SF a b = SF {runSF :: [a]->[b]} 

e il ritardo è definito come:

delay x = SF (init . (x:)) 

SF è un'istanza di ArrowChoice (che dichiara mapA) e quindi un'istanza di Arrow.

mia comprensione

mapA :: arr a b -> arr [a] [b] 
delay :: SF a b 

tale che delay antepone semplicemente il suo secondo argomento con il suo primo.

Così, mapA (delay 0) dovrebbe restituirci una freccia SF che prende [[a]] e restituisce [[b]]

mapA (delay 0) :: SF [[a]] [[b]] 

mi aspetterei che il "circuito" che questo si tradurrebbe in è:

Dove i numeri indicano parti del processo:

1. Per qualsiasi valore non vuoto list x, listcase emetterà Right(x, xs). Per la lista vuota, listcase emetterà Left(), la custodia del terminale.
2. I valori codificati Right verranno passati alla parte inferiore. I valori taggati Left verranno passati a const[], che in sostanza interrompe l'iterazione.
3. Con ingresso (x, xs), saranno passati x a (delay 0), mentre xs sarà passato indietro attraverso listcase.
4. L'output di 3 sarà (z, zs), che viene passato a uncurry (:), che unisce la tupla alla lista.

Ecco la mia comprensione del flusso, con il contributo [[1,2,3],[4,5,6],[7,8,9]]:

• primo passaggio

  1. Right ([1,2,3],[[4,5,6],[7,8,9]])
  2. ([1,2,3], [[4,5,6],[7,8,9]]) viene passato alla parte inferiore
  3. (delay 0) è chiamato a [1,2,3], res ulting in [0,1,2].[[4,5,6],[7,8,9]] viene passato al listcase

• Secondo passaggio

  1. Right ([4,5,6], [[7,8,9]])
  2. ([4,5,6], [[7,8,9]]) viene passata alla porzione inferiore
  3. (delay 0) è invitato [4,5,6], con conseguente [0,4,5]. [[7,8,9]] viene passato al listcase

• Terzo passaggio

  1. Right ([7,8,9], [])
  2. ([7,8,9], []) viene passata alla porzione inferiore
  3. (delay 0) è invitato [7,8,9], con conseguente [0,7,8]. [] è passato a listcase.

• quarto passaggio

  1. Left(), caduto sul pavimento.

A questo punto, si arriva a parte 4, che prende l'uscita 3 e concats tutto insieme. Noi costruiamo essenzialmente di un'operazione di:

[0,1,2] : [[0,4,5] : [[0,7,8] : []]]

Il che ci [[0,1,2],[0,4,5],[0,7,8]] darebbe.

mia confusione

Chiaramente, il mio flusso sopra è sbagliato.

Come si chiama runSF (mapA (delay 0)) [[1,2,3],[4,5,6],[7,8,9]] in [[0,0,0],[1,2,3],[4,5,6]]?

Answer 1

Trovo che questi esempi siano difficili da ragionare. Ci sono due liste in questo esempio di , la lista esterna è lo stream su cui opera la tua freccia, mentre gli elenchi interni sono ciò che mapA esegue. Considera un esempio più semplice, quindi per il momento è possibile ignorare il caso ricorsivo. Dato

runSF (mapA (delay 0)) [[1], [2]] 

Vediamo che il primo passo

1. pipe l'ingresso attraverso la freccia listcase ci dà l'uscita [Right (1, []), Right (2, [])]. I primi elementi di ciascuna coppia vengono inviati alla freccia delay 0, mentre i secondi elementi vengono restituiti a .
2. Quindi, abbiamo quello [1, 2] => delay 0 e [[], []] => mapA f. alimentazione [1,2] in delay 0 dà il risultato [0, 1], e alimentando le liste vuote per mapA f rese più elenchi vuoti [[], []].

3. Questi due risultati sono alimentati arr (uncurry (:)), che agisce come zipWith (:), poiché queste funzioni sono tutti mappati sulle liste, quindi unisce i due ingressi elenchi elemento saggio.

   [0, 1] 
       | 
       v 
   arr (uncurry (:)) => [ 0:[], 1:[] ] == [[0], [1]] 
   ^
       | 
   [[], []] 
   

La chiave è quello di riconoscere che tutto il materiale costruito con arr opera sul set interno di liste, in modo da gestire l'input iniziale attraverso arr listcase non produce Right ([1,2,3],[[4,5,6],[7,8,9]]), ma [Right (1, [2, 3]), Right (4, [5,6]), Right (7, [8,9])]. Questo è il mio tentativo di disegnarlo in un diagramma.

 [Right (1, [2, 3]), Right (4, [5,6]), Right (7, [8,9])] 
    ======================================================= 
       |  [1, 4, 7]  +-----------+ [0, 1, 4] 
    +----------+ |  +----=--------->| delay |-----=------| 
    | listcase |---=------>|    +-----------+   | +-------------------+ 
    +----------+   |          +-->| arr (uncurry (:)) |---> [[0,0,0],[1,2,3],[4,5,6]] 
         |          | +-------------------+ 
         |    +-----------+   | 
         +-------=------>| mapA f |------=-----| 
           |  +-----------+  | 
           |       | 
          [[2,3],[4,5],[6,7]]   [[0,0], [2,3],[4,5]] 
                 * what will be 
                 returned if you 
                 trace it through 

Mi dispiace che non riesco a disegnare meglio. In effetti, mapA dà una visione trasposto della lista di input, così si può pensare di mapA (delay 0) come operante come transpose . map (init . (0:)) . transpose, dal momento che init . (0:) è la definizione di delay.