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

Question

我正在尝试找到一种方法来翻译正常的递归符号，例如作为 |fib|功能下方的箭头，保留尽可能多的递归表示法的结构尽可能。另外我会喜欢检查箭头。为此，我创建了一个数据类型，其中包含每个 Arrow{..} 类的构造函数:

斐波那契:

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|上面的函数首先导致以下定义。然而，由于 proc n on，这是不允许的|fibz| 声明的右侧。我知道的语法是箭头符号可以防止这种情况发生，但根本原因是什么这个？

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

基本上，是否可以观察到这种递归？ (也许即使在箭头表示法的范围内)我也许可以添加另一个构造函数，如修复。也许我应该能够观察变量的绑定(bind)，以便引用它们成为可能。但这超出了 Arrows 的范围。

对此有什么想法吗？

更新 1:我在箭头符号之外想出了这种形式。这隐藏了应用程序内的递归，因此我最终得到了箭头的有限表示。但是，我仍然希望能够例如将 app 内对 fib 的调用替换为 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，例如如下所示:

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

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

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

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