haskell - 在 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-ed 结构的单遍中，例如：

data L a as = Empty | C a as

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

zygo似乎几乎是我想要的，除了我需要访问最终结果b（上例中的最终总和）。

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

Answer 1

您想通过调整值向上下降Fix f，同时像 mapAccumR 那样跟踪状态吗？那是cataM为了向上的顺序，用Statemonad来跟踪状态。在您的示例中：

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

全部未经测试。

还是您希望每个分支机构都本地化该州？