Reconnecting trees in the Haskell AST template
I am updating a library where I translated Haskell into another language. I am currently using Meta.Parse to read in a Haskell module and return it to TemplateHaskell AST as described here .
The problem I'm running into is that when I run parsing, I get a bunch of infix operators parsed as UInfixE and UInfixP, which means they have unresolved associativity.
the description of associativity talks about how the Haskell compiler resolves them.
I am wondering if there is a function available that can make this override on the trees I get from parsing? I'm looking for something like this:
reassoc :: [Dec] -> [Dec]
I could write a massive AST traversal that does this, but it looks like it will be a massive amount of boilerplate, and obviously the function already exists in one form or another (hopefully in a form that goes well with TH).
Is there such a thing? Is there an easy way to get rid of the unresolved infix operators in the AST that I get from parsing declarations?
EDIT: Even a function that, given the name of the operator, could give advantage and associativity would be very helpful.
source to share
I don't know if such a function exists, but you can write it yourself using Scrap Your Boilerplate to get rid of all the template code. In particular, the writing of the function that is applied to each UInfixE
(when passing the declaration from top to bottom) is simple:
import Language.Haskell.TH
import Data.Data
import Data.Generics.Schemes
import Data.Generics.Aliases
fixity :: (Data a)
=> (Exp -> Exp -> Exp -> Exp) -- ^ a function that converts
-- UInfixE Exp Exp Exp to another Exp
-> a -> a
fixity f = everywhere' (mkT expf)
where
expf (UInfixE l o r) = f l o r
expf e = e
fixity
It can be applied to anything that is of the type Data
, including Dec
, Exp
and other types of data TH.
You probably don't care about the order UInfixE
, as the tree is still ambiguous and still needs to be re-linked. Going a little further in that direction, we can improve the function to dump every tree UInfixE
it finds:
-- | Converts all `UInfixU` subtrees using given right-folding functions.
--
-- For example if @fixityFold step right result@ finds
-- @1 + 2 * 3 / 4@ somewhere,
-- the corresponding subtree will be replaced by (abusing the notation)
-- @result (step '1 '+ (step '2 '* (step '3 '/ (right '4))))@.
fixityFold :: (Data a)
=> (Exp -> Exp -> a -> a)
-> (Exp -> a)
-> (a -> Exp)
-> a -> a
fixityFold step right result = everywhere' (mkT expf)
where
expf exp@(UInfixE _ _ _) = result (foldrUInfixE exp right)
expf e = e
foldrUInfixE (UInfixE l o r) rf = foldrUInfixE l
(\e -> step e o (foldrUInfixE r rf))
foldrUInfixE exp rf = rf exp
This should allow you to build whatever tree structure you need to reorder the expression using the appropriate precedence.
source to share