Cosa c'è di sbagliato in questa istanza: ArrowApply Automaton?

Question

Desidero che Automaton abbia l'istanza ArrowApply, ma Control.Arrow.Transformer.Automaton no. Credo che il seguente codice si comporterà bene:

data Automaton b c = Auto {runAuto :: b -> (c, Automaton b c) } 

app :: Automaton (Automaton b c, b) c 
app = Auto $ \(f,x) -> let 
    (u, m) = runAuto f x 
    nextApp m = Auto $ \(_,x) -> let 
     (u', n) = runAuto m x 
     in (u', nextApp n) 
    in (u, nextApp m) 

Probabilmente, l'esistenza di argomento non utilizzato non sarebbe buono. Tuttavia non posso avere alcuna idea concreta di cattivo esempio, per favore dimmelo.

Answer 1

Non soddisferà ArrowApply laws,

essa si guasti con la prima legge:

first (arr (\x -> arr (\y -> (x,y)))) >>> app = id 
    :: ArrowApply a => a (t, d) (t, d) 

prima definire una funzione di supporto del Let:

iterateAuto :: [b] -> Auto b c -> [c] 
iterateAuto [] _ = [] 
iterateAuto (x:xs) a = let (y, a') = runAuto a x 
        in y : iterateAuto xs a' 

Sul lato destro otteniamo :

*Main> iterateAuto [(0,0), (1,0)] (id :: Auto (Int, Int) (Int, Int)) 
[(0,0),(1,0)] 

Ma sul lato sinistro (qui ho dovuto chiamare l'implementazione app')

iterateAuto [(0,0), (1,0)] (first (arr (\x -> arr (\y -> (x,y)))) >>> app' :: Auto (Int, Int) (Int, Int)) 
[(0,0),(0,0)] 

Sono abbastanza sicuro che se ArrowApply per Automaton fosse possibile, sarebbe in arrows pacchetto. È difficile spiegare perché non può esserlo. Cerco di spiegare la mia intuizione. Il ArrowApply equivale a Monad e app è un tipo di monade join. Il Automaton è un tipo di computazione stateful, tuttavia ogni Automaton ha il proprio stato, non lo stato globale come in State monade. Nell'impostazione pura, il prossimo stato dell'automa ci viene dato su ogni iterazione nella coppia di risultati. Tuttavia, se avessimo lo app, lo stato dell'automa interno andrebbe perso.

Un'altra implementazione ingenuo di app:

app'' :: Auto (Auto b c, b) c 
app'' = Automaton $ \(f,x) -> let 
    (u, m) = runAuto f x 
    nextApp = app'' 
    in (u, nextApp) 

fallirà sulla seconda legge

first (arr (g >>>)) >>> app = second g >>> app 

Diamo uno stateful incr come g

incr :: Auto Int Int 
incr = incr' 0 
    where incr' n = Automaton $ \x -> (x + n, incr' $ n + 1) 

e metodo di supporto

helper :: Arrow a => (Int, Int) -> (a Int Int, Int) 
helper (x, y) = (arr (+x), y) 

Poi vediamo che equazione non tenere per un semplice ingresso così:

*Main> iterateAuto (map helper [(0,0),(0,0)]) $ first (arr (incr >>>)) >>> app'' 
[0,0] 
*Main> iterateAuto (map helper [(0,0),(0,0)]) $ second incr >>> app'' 
[0,1] 

Ho the runnable code as a gist

Un'idea empio sarebbe quello di fare una versione di automa sfruttando IOREF o STRef

data STAutomaton s a b c = STAutomaton (STRef s (Automaton a b c)) 

ma che è probabilmente il modo goffo di utilizzare Kleisli (ST s) o Kleisli IO.