mapAccumR -like recursion scheme over Fix?

Question

I'm playing with the functions from recursion-schemes, and struggling to figure out if it offers something that generalized mapAccumR. Something powerful enough to implement e.g.:

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

...in a single pass for a Fix-ed structure, like:

data L a as = Empty | C a as

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

zygo seems to be nearly what I want, except that I need access to the final b (the final sum in the example above).

My actual use case is type-checking an AST while annotating, and returning the type of the expression.

Answer 1

You want to descend upwards through Fix f tweaking values, while keeping track of a state as mapAccumR does? That's cataM for the upward order, with the State monad for the state to be kept track of. In your example:

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

Using lens:

makeClassyPrisms ''L

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

All untested.

Or do you want the state to be local to each branch?