3 
{-# LANGUAGE FlexibleContexts, DeriveFoldable, TemplateHaskell,
    TypeFamilies, DeriveFunctor, DeriveTraversable #-}
import Control.Applicative
import Data.Functor.Foldable
import Data.Functor.Foldable.TH
import Data.Maybe

我想使用“本地”重写器重写树：

data SKI = S | K | I | App SKI SKI deriving (Show)

makeBaseFunctor ''SKI

type Rewrite a = a -> Maybe a

match :: Rewrite SKI
match x = case x of
    App I x -> Just x
    _ -> Nothing

所以我编写了在树的不同点rewriteGlobal应用相同的函数。match它需要一个“本地”Rewrite t并返回一个全局的。我只遍历树一次，没有尝试对每个树节点多次应用重写，直到不再可能进行重写。

但是有两种方法可以重写树。每次重写都对已重写的子树（WithChildren模式）或“原始”子树（WithoutChildren模式）进行操作。在后一种情况下，更高的重写“获胜”。

忽略 上的约束t， 的类型rewriteGlobal为：

data ChildRewrites = WithChildren | WithoutChildren

rewriteGlobal :: ChildRewrites -> Rewrite t -> Rewrite t

这是一个实现：

rewriteGlobal flag rewriteFn = para $ liftA2 (<|>)
    (rewriteFn . handleChildren flag)
    liftChildRewrites

handleChildren WithChildren = embed . fmap (uncurry fromMaybe)
handleChildren WithoutChildren = embed . fmap fst

liftChildRewrites cons | any (isJust . snd) cons = Just $ handleChildren WithChildren cons
liftChildRewrites _ = Nothing

liftChildRewrites而且liftA2 (<|>)看起来特别难看。

问题是：我不能做得更好吗？代码已经很短了，所以不是要让它更短。但是我是否朝着正确的方向前进，或者有比异态更好的局部匹配分布方法，例如更好的数据结构、单子方法或递归方案？

我没有避免替换的活页夹/名称/捕获，因此（P）HOAS 和类似方法可能不会更好。而且我没有实施 SKI 演算，这只是一个激励性的例子。

以下代码可用于测试：

test = App I $ App S $ App I $ K

bar = [rewrite WithChildren match test, rewrite WithoutChildren match test]

问题是：是否有为本地重写设计的特定结构/方法？如果这种专门的方法不存在并且通用方法是我能做的最好的，它只是基于意见的。

4

0 回答 0