这个实例有什么问题：ArrowApply Automaton？ [英] What is wrong with this instance : ArrowApply Automaton?

问题描述

我想让Automaton拥有实例ArrowApply，但是Control.Arrow.Transformer.Automaton没有。
我认为以下代码将表现良好：

 数据Automaton b c = Auto {runAuto :: b  - > （c，Automaton b c）} 
 
 app :: Automaton（Automaton b c，b）c 
 app = Auto $ \（f，x） - >让
（u，m）= runAuto f x 
 nextApp m = Auto $ \（_，x） - > （u'，nextApp n）
（u，nextApp m）
（u'，n）= runAuto mx 
让
  pre> 
 
 
也许，未使用的参数的存在会不好。 
然而，我不能对坏例子有任何具体的想法，请告诉我任何它。
解决方案
它将不符合 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 ax 
 in y：iterateAuto xs a'
  
在右侧，我们得到：
 
 
  *主> iterateAuto [（0,0），（1,0）]（id :: Auto（Int，Int）（Int，Int））
 [（0,0），（1,0）] 
  
但是在左侧（这里我必须为您的实现命名 app' $ b $ $ p $  iterateAuto [（0,0），（1,0）]（first（arr（\\ （x，y））））>>>>> app':: Auto（Int，Int）（Int，Int））
 [（0 ，0），（0,0）] 
  

我很确定如果<$ c $对于 Automaton ，c> ArrowApply 是可能的，它将位于 arrows 包中。很难解释为什么不能有一个。我试图解释我的直觉。 ArrowApply 相当于 Monad ，并且 app 是kind monadic 加入。 Automaton 是一种有状态计算，但每一个 Automaton 都有它自己的状态，而不是全局状态，如 State monad。在纯粹的设置中，自动机的下一个状态是在结果对的每次迭代中给予我们的。但是如果我们有 app ，内部自动机的状态就会丢失。

$ b

  app'':: Auto（Auto bc，b）c 
 app''=自动机$ \（f，x） - >让
（u，m）= runAuto fx 
 nextApp = app''
（u，nextApp）
  

在第二定律上将失败

  first（arr（g>> >））>>> app = second g>>> app 
  

让我们把有状态的 incr code> g

  incr :: Auto Int Int 
 incr = incr '0 
其中incr'n =自动机$ \ 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 的Automaton版本

  data STAutomaton sabc = STAutomaton（STRef s（Automaton abc））
  pre> 
 
 
但这可能是使用 Kleisli（ST s）或 Kleisli IO 。
 
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.
解决方案
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.

                        
这篇关于这个实例有什么问题：ArrowApply Automaton？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！