4

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.

duplode
  • 33,731
  • 7
  • 79
  • 150
jberryman
  • 16,334
  • 5
  • 42
  • 83
  • 1
    What sort of type signature are you hoping for? – dfeuer Dec 19 '16 at 16:43
  • 1
    Also, you should probably look at `para`. – dfeuer Dec 19 '16 at 16:48
  • 1
    But back to my first question, `mapAccumR` is a known concept for `Traversable` functors; it's much less clear what its supposed to mean for fixed points of arbitrary types. – dfeuer Dec 19 '16 at 16:54
  • 1
    Right so I think `para` is powerful enough to implement `f` but in quadratic time which I don't want. I think I could also do two `cata`, one to tag and accumulate sizes, and the next to strip those sizes from the subtrees again, but I also don't want to do that. You're right, probably if I thought hard about a signature I'd be most of the way to answering my own question, but I think I've decided this is all rather silly anyway – jberryman Dec 19 '16 at 17:17
  • It looks like what I'm after is `zygo`; see [this answer](http://stackoverflow.com/a/36911924/176841) – jberryman Dec 22 '16 at 19:23
  • Argh, except I need to capture that final `b` at the top level... hm, maybe that's hiding in `gzygo`; not sure. – jberryman Dec 23 '16 at 00:02
  • 2
    The documentation for `recursion-schemes` is really superb. Immediately obvious that `zygo` is the way to go. – scooter me fecit Dec 23 '16 at 06:48

1 Answers1

0

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?

Gurkenglas
  • 2,317
  • 9
  • 17
  • Thanks, my actual example is an AST where I'm type-checking and annotating the tree in one pass. So at each level we need access to child types and return a type for the parent. Here's some points though, I appreciate the answer – jberryman Dec 29 '16 at 16:01