箭头中的可观察递归(或绑定)

Question

我试图找到一种方法来转换正常的递归表示法,如| fib | 函数下面的箭头,保留尽可能多的递归表示法的结构.另外我想检查箭头.为此我创建了一个数据类型,其中包含每个Arrow {..}类的构造函数:

FIB:

fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

我的R数据类型,此数据类型的实例包含到相应构造函数的映射:

data R x y where
  -- Category
  Id       :: R a a
  Comp     :: R b c    -> R a b          -> R a c
  -- Arrow
  Arr      :: (a -> b) -> R a b
  Split    :: R b c    -> R b' c'        -> R (b,b') (c,c')
  Cache    :: (a -> a -> Bool) -> R a a
  -- ArrowChoice
  Choice   :: R b c -> R b' c' -> R (Either b b') (Either c c')
  -- ArrowLoop
  Loop     :: R (b, d) (c, d)  -> R b c
  -- ArrowApply
  Apply    :: R (R b c, b) c

翻译| fib | 上面的函数首先得出以下定义.但是由于| frz |声明的RHS上的处理,不允许这样做.我知道Arrow符号的语法可以防止这种情况,但这是什么原因？

fib' :: (ArrowChoice r, ArrowLoop r) => r Int Int
fib' = proc x -> do
  rec fibz <- proc n -> case n of
                          0  -> returnA -< 0
                          1  -> returnA -< 1
                          n' -> do l <- fibz -< (n'-2)
                                   r <- fibz -< (n'-1)
                                   returnA -< (l+r)
  fibz -<< x

重写上面的函数使用let语句编译.但是,这里出现了第二个问题.我希望能够检查它发生的递归.但是,在这种情况下,| fibz | 是一棵无限的树.我想捕获到fibz的递归,我希望rec能帮助我将它与| loop |结合使用 但也许我错了？

fib'' :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int
fib'' = proc x -> do
  let fibz = proc n -> case n of
                          0  -> returnA -< 0
                          1  -> returnA -< 1
                          n' -> do l <- fibz -< (n'-2)
                                   r <- fibz -< (n'-1)
                                   returnA -< (l+r)
  fibz -<< x

基本上,有可能观察到这种递归吗？(也许甚至在Arrow Notation的边界内)我也许可以添加另一个像fix这样的构造函数.也许我应该能够观察变量的绑定,以便引用它们成为可能.但这不属于箭头的范围.

有什么想法吗？

更新1: 我在箭头表示法之外提出了这个表格.这隐藏了内部的递归app,因此我最终得到了Arrow的有限表示.但是,我仍然希望能够将fib内部调用替换为app优化版本fib.

fib :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int
fib
  = (arr
       (\ n ->
          case n of
              0 -> Left ()
              1 -> Right (Left ())
              n' -> Right (Right n'))
       >>>
       (arr (\ () -> 0) |||
          (arr (\ () -> 1) |||
             (arr (\ n' -> (n', n')) >>>
                (first ( arr (\ n' -> app (fib, n' - 2))) >>>
                   arr (\ (l, n') -> (n', l)))
                  >>>
                  (first (arr (\ n' -> app (fib, n' - 1))) >>>
                     arr (\ (r, l) -> (l + r)))))))                                 

此代码对应于箭头表示法中的以下内容:

fib :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int
fib  = proc n ->
   case n of
     0  -> returnA -< 0
     1  -> returnA -< 1
     n' -> 
           do l <- fib -<< (n'-2)
              r <- fib -<< (n'-1)
              returnA -< (l+r)

Answer 1

您可以fib用循环的形式编写，例如：

\n\n

fib\'\' :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int\nfib\'\' = loop $\xc2\xa0proc (i, r) -> do\n    i\' <- r -<< i\n    returnA -< (i\', proc j -> case j of\n        0 -> returnA -< 0\n        1 -> returnA -< 1\n        _ -> do\n            a <- r -< j-2\n            b <- r -< j-1\n            returnA -< a + b)\n

\n\n

但这实际上只是向不需要它的问题引入了一个人工循环，并且在可观察性方面也并没有给你带来太多好处。您可以看出存在某种循环，但我认为不可能真正确定递归发生的位置。

\n\n

在具体化表示中，对其他箭头的任何调用本质上都是“内联的”，这包括对同一箭头的调用。您一开始就无法真正检测到这些调用站点，更不用说找出正在调用哪个箭头了。箭头具体化的另一个问题是，许多有关输入如何传递的有趣信息在Arr黑洞内丢失了。

\n\n

我当然不是箭头方面的专家，我希望有人证明我错了，但我倾向于认为你想要实现的目标是不可能可靠地做到的，或者至少是非常不切实际的。我能想到的一个可以帮助您转发的资源是Haskell 中的类型安全可观察共享论文和data-reify包。

\n