Повторное связывание деревьев в шаблоне Haskell AST's

Question

Я обновляю библиотеку, где я переводил Haskell на другой язык. Прямо сейчас я использую Meta.Parse для чтения в модуле Haskell и возвращаю его TemplateHaskell AST, как описано here.

Проблема, с которой я сталкиваюсь, заключается в том, что когда я запускаю синтаксический анализ, я получаю кучу инфиксных операторов, анализируемых как UInfixE и UInfixP, что означает, что они имеют неразрешенную ассоциативность.

description of the associativity рассказывает о том, как компилятор Haskell решает их.

Мне интересно, есть ли доступная функция, которая может выполнить эту переориентацию на деревьях, которые я получаю от разбора? Я ищу что-то вроде этого:

reassoc :: [Dec] -> [Dec] 

Я мог бы написать массивную AST обхода, который делает это, но похоже, что это будет огромное количество шаблонного, и ясно, что функция уже существует в той или иной форме (надеюсь, в форме, которая хорошо сочетается с TH).

Существует ли такая вещь? Есть ли простой способ избавиться от нерешенных инфиксных операторов в AST, которые я получаю от объявлений синтаксического анализа?

РЕДАКТИРОВАТЬ: Даже функция, которая, учитывая имя оператора, могла бы придавать ему приоритет и ассоциативность, была бы очень полезной.

Answer 1

Я не знаю, существует ли такая функция, но вы можете написать ее самостоятельно, используя Scrap Your Boilerplate, чтобы избавиться от всего кода шаблона. В частности, написание функции, которая будет применяться к каждому UInfixE (при прохождении декларации сверху вниз) легко:

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 могут быть применены ко всему, что имеет тип Data, в том числе Dec, Exp и других TH типы данных.

Возможно, вам все равно, что порядок UInfixE, так как дерево все равно неоднозначно, и в любом случае его необходимо повторно связать. Забегая дальше в этом направлении, мы можем улучшить функцию сложить над каждым деревом UInfixE с его находит:

-- | 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 

Это должно позволить вам создать то, что древовидная структура вам нужно переставить выражение используя соответствующие приоритеты.