How to fuse multiple syb-style top-down rewriting functions?

Learn
#1

Hi fellow Haskellers,

I’m working on a compiler project, and currently, there are multiple rewriting passes which traverse the whole AST. The type signatures are all roughly somePass :: forall a . Data a => a -> m a, where m is a Monad instance. The Data constraint makes it convenient to work with mutually-recursive datatype definitions.

Does there exist some fusion technique so multiple passes can be fused into one to ensure the actual traversal is done only once, to reduce time/space overhead? Thanks.

#2

Fusion laws don’t apply, since you’re in a monadic setting. Fused and individual traversals don’t necessarily commute. That said, your “somepass” calls are probably all built out of calling some syb primitive over some “worker” function – so perhaps write your traversals in terms of the worker function itself, and then just chain those? What type signature do those worker functions have?

#3

I used to encode recursion directly by calling gmapM manually in each pass. Now that you mention it, it’s indeed possible to decompose a pass into a single worker which only transforms a single layer. Thanks!

Also, if we assume each pass lives in a separate state monad, and the “composition” of all rewriting passes lives in the state monad with a product state type, does that still violate fusion laws?

#4

I think it won’t violate fusion laws in that case, but I’d want to check carefully to be sure. In any case, just because it may admit some general case which violates laws doesn’t mean your specific case will run into problems.