What is wrong with this instance : ArrowApply Automaton?

Question

I want Automaton to have instance ArrowApply, but Control.Arrow.Transformer.Automaton hasn't. I think the following code will behave well :

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)

Probably, The existence of unused argument would be not good. However I can't have any concrete idea of bad example, please tell me any of it.

Answer 1

It will not satisfy ArrowApply laws,

it actually fails with the first law:

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

Let's first define a helper function:

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

On the right hand side we get:

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

But on the left hand side (here I had to name your implementation app')

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

I'm quite sure that if ArrowApply for Automaton were possible, it would be in arrows package. It's hard to explain why there can't be one. I try to explain my intuition. The ArrowApply is equivalent to Monad, and app is kind of monadic join. The Automaton is kind of stateful computation, yet every Automaton carries it's own state, not the global state as in State monad. In pure setting the next state of the automaton is given to us on each iteration in the result pair. Yet if we would have app, the state of inner automaton is lost.

Another naive implementation of app:

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

will fail on the second law

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

Let's take a stateful incr as g

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

and helper method

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

Then we see that equation doesn't hold for a very simple input as well:

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

I have the runnable code as a gist

One wicked idea would be to make a version of Automaton by exploiting IORef or STRef

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

but that is probably the awkward way of using Kleisli (ST s) or Kleisli IO.