5

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.

Cactus
  • 27,075
  • 9
  • 69
  • 149
phi16
  • 123
  • 5
  • The [laws for `ArrowApply`](http://hackage.haskell.org/package/base-4.7.0.1/docs/Control-Arrow.html#t:ArrowApply) relate it to `Arrow` and `Category`. It's not meaningful to consider if application is correct without an `Arrow` and `Category` instance. I assume you are using the `Arrow` and `Category` instances for `Automaton (->)` from [`Control.Arrow.Transformer.Automaton`](https://hackage.haskell.org/package/arrows-0.4.4.1/docs/Control-Arrow-Transformer-Automaton.html)? – Cirdec Dec 22 '14 at 15:13

1 Answers1

5

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.

phadej
  • 11,947
  • 41
  • 78
  • Thanks! In fact, I want to make an `Arrow` which is same as that `STAutomaton`. Can it be made a correct instance of `ArrowApply`? Or is it wrong way of implementing 'local state'? (Now I'm thinking `ArrowCircuit` can represent variable, so I'm attempting it. What do you think about it?) – phi16 Dec 23 '14 at 14:23
  • There are nice tricks presented in the recent ICFP paper. I didn't do the exercise, but you *should* be able to simulate local state using `ArrowChoice` and `delay` from `ArrowCircuit`: https://www.youtube.com/watch?v=zgNRM8tZguY – phadej Dec 24 '14 at 11:15