在 Fix 上实现类似于 mapAccumR 的递归方案？

Question

我正在使用来自recursion-schemes的函数，但我很难弄清它是否提供了一些类似于通用mapAccumR的东西。是否有足够强大的功能可以实现例如：

f :: [Int] -> (Int,[Int])
f [] = (0,[]) 
f (x:xs) = let (sz,xs') = f xs in (sz+x, x*sz : xs')

在处理像下面这样的Fix结构时，可以一次性完成：

data L a as = Empty | C a as

input :: Fix (L Int)
input = Fix (C 1 (Fix (C 2 (Fix Empty))))

zygo 看起来就是我需要的，但我需要访问最终的 b（如上例中的最终总和）。

我的实际用例是在注释AST时进行类型检查，并返回表达式的类型。

- jberryman

---

你希望得到什么类型的签名？ - dfeuer

另外，你可能应该看一下 para。 - dfeuer

但回到我的第一个问题，“mapAccumR”是“Traversable” functor的已知概念；对于任意类型的固定点，它的含义要清晰得多。 - dfeuer

所以我认为para足够强大，可以实现f，但是时间复杂度是二次的，这不是我想要的。我想我也可以使用两个cata，一个用来标记和累积大小，另一个用来从子树中去除这些大小，但我也不想这样做。你说得对，也许如果我仔细思考一下签名，我就能解答自己的问题，但我想我已经决定这一切都有些愚蠢了。 - jberryman

recursion-schemes 的文档非常出色。很明显 zygo 是最佳选择。 - scooter me fecit

Answer 1

你想要通过调整值下降到Fix f中，同时像mapAccumR一样保持状态吗？那就用cataM来进行向上遍历，使用State单子来跟踪状态。在你的例子中：

f :: Fix (L Int) -> (Fix (L Int), Int)
f = (`runState` 0) $ cataM $ ((.) . fmap) Fix $ \case
  Empty -> pure Empty
  C x xs -> do
    sz <- get
    put $ sz+x
    return $ C (x*sz) xs

使用lens：

makeClassyPrisms ''L

f = (`runState` 0) . transformMOf . _Fix . _C . _1 $ \x -> do
  sz <- id <<+= x
  return $ x*sz

全部未经测试。

或者你想让状态对于每个分支都是本地的吗？

- Gurkenglas

---

谢谢，我的实际例子是一个AST，在其中进行类型检查和注释树的一次遍历。因此，在每个级别，我们需要访问子类型并为父类型返回一个类型。以下是一些要点，感谢您的回答。 - jberryman