这个实例有什么问题: ArrowApply自动机？

Question

我希望自动机有实例ArrowApply，但是Control.Arrow.Transformer.Automaton没有。

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)

也许，未使用的论点的存在将是不好的。但是我不能对坏的例子有任何具体的想法，请告诉我其中的任何一个。

Answer 1

它不能满足ArrowApply定律，

实际上，第一条法律是行不通的：

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

让我们首先定义一个帮助函数：

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

在右边，我们得到：

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

但是在左手边(这里我必须给您的实现命名app')

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

我确信，如果ArrowApply for Automaton是可能的，那么它将在arrows包中。很难解释为什么不可能有。我试着解释我的直觉。ArrowApply相当于Monad，app是一种一元join。Automaton是一种有状态的计算，但是每个Automaton都有它自己的状态，而不是像State monad那样的全局状态。在纯设置中，在结果对中的每次迭代中，给出了自动机的下一个状态。然而，如果我们有app，内部自动机的状态就会消失。

app的另一个天真实现

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

第二条法律将失败

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

让我们以有状态incr作为g

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

辅助法

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

然后我们看到，对于一个非常简单的输入，这个方程也不成立：

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

我有作为要点的可运行代码

一个邪恶的想法是利用IORef或STRef制作一个自动机的版本。

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

但这可能是使用Kleisli (ST s)或Kleisli IO的尴尬方式。