使用 Uniplate 简化 GADT [英] Simplifying a GADT with Uniplate
问题描述
我正在尝试回答这个stackoverflow问题，使用uniplate 正如我所建议的，但是我来的唯一解决方案到目前为止很丑.
I'm trying to answer this stackoverflow question, using uniplate as I suggested, but the only solution I've come up with so far is pretty ugly.
这似乎是一个相当普遍的问题，所以我想知道是否有更优雅的解决方案.
This seems like a fairly common issue, so I wanted to know if there was a more elegant solution.
基本上，我们有一个 GADT，它解析为 Expression Int 或 Expression Bool(忽略 codataIf = If (B True) codataIf codataIf):
Basically, we've got a GADT which resolves to either Expression Int or Expression Bool (ignoring codataIf = If (B True) codataIf codataIf):
data Expression a where
I :: Int -> Expression Int
B :: Bool -> Expression Bool
Add :: Expression Int -> Expression Int -> Expression Int
Mul :: Expression Int -> Expression Int -> Expression Int
Eq :: Expression Int -> Expression Int -> Expression Bool
And :: Expression Bool -> Expression Bool -> Expression Bool
Or :: Expression Bool -> Expression Bool -> Expression Bool
If :: Expression Bool -> Expression a -> Expression a -> Expression a
并且(在我的问题版本中)我们希望能够使用一个简单的操作将叶子组合成一个新的叶子，从自下而上评估表达式树:
And (in my version of the problem) we want to be able to evaluate the expression tree from the bottom-up using a simple operation to combine leaves into a new leaf:
step :: Expression a -> Expression a
step = case
Add (I x) (I y) -> I $ x + y
Mul (I x) (I y) -> I $ x * y
Eq (I x) (I y) -> B $ x == y
And (B x) (B y) -> B $ x && y
Or (B x) (B y) -> B $ x || y
If (B b) x y -> if b then x else y
z -> z
我在使用 DataDeriving 来派生 Uniplate 和 Biplate 实例时遇到了一些困难(这可能应该是一个危险信号)，所以我为 Expression Int、Expression Bool 和 Biplate 实例为 (Expressiona) (Expression a)、(Expression Int) (Expression Bool) 和 (Expression Bool) (Expression Int).
I had some difficulty using DataDeriving to derive Uniplate and Biplate instances (which maybe should have been a red flag), so
I rolled my own Uniplate instances for Expression Int, Expression Bool, and Biplate instances for (Expression a) (Expression a), (Expression Int) (Expression Bool), and (Expression Bool) (Expression Int).
这让我想出了这些自下而上的遍历:
This let me come up with these bottom-up traversals:
evalInt :: Expression Int -> Expression Int
evalInt = transform step
evalIntBi :: Expression Bool -> Expression Bool
evalIntBi = transformBi (step :: Expression Int -> Expression Int)
evalBool :: Expression Bool -> Expression Bool
evalBool = transform step
evalBoolBi :: Expression Int -> Expression Int
evalBoolBi = transformBi (step :: Expression Bool -> Expression Bool)
但是由于这些中的每一个只能做一个转换(组合 Int 叶子或 Bool 叶子，但不能做任何一个)，他们不能做完全的简化，但是必须手动链接在一起:
But since each of these can only do one transformation (combine Int leaves or Bool leaves, but not either), they can't do the complete simplification, but must be chained together manually:
λ example1
If (Eq (I 0) (Add (I 0) (I 0))) (I 1) (I 2)
λ evalInt it
If (Eq (I 0) (I 0)) (I 1) (I 2)
λ evalBoolBi it
If (B True) (I 1) (I 2)
λ evalInt it
I 1
λ example2
If (Eq (I 0) (Add (I 0) (I 0))) (B True) (B False)
λ evalIntBi it
If (Eq (I 0) (I 0)) (B True) (B False)
λ evalBool it
B True
我的hackish解决方法是为Either (Expression Int) (Expression Bool)定义一个Uniplate实例:
My hackish workaround was to define a Uniplate instance for Either (Expression Int) (Expression Bool):
type WExp = Either (Expression Int) (Expression Bool)
instance Uniplate WExp where
uniplate = case
Left (Add x y) -> plate (i2 Left Add) |* Left x |* Left y
Left (Mul x y) -> plate (i2 Left Mul) |* Left x |* Left y
Left (If b x y) -> plate (bi2 Left If) |* Right b |* Left x |* Left y
Right (Eq x y) -> plate (i2 Right Eq) |* Left x |* Left y
Right (And x y) -> plate (b2 Right And) |* Right x |* Right y
Right (Or x y) -> plate (b2 Right Or) |* Right x |* Right y
Right (If b x y) -> plate (b3 Right If) |* Right b |* Right x |* Right y
e -> plate e
where i2 side op (Left x) (Left y) = side (op x y)
i2 _ _ _ _ = error "type mismatch"
b2 side op (Right x) (Right y) = side (op x y)
b2 _ _ _ _ = error "type mismatch"
bi2 side op (Right x) (Left y) (Left z) = side (op x y z)
bi2 _ _ _ _ _ = error "type mismatch"
b3 side op (Right x) (Right y) (Right z) = side (op x y z)
b3 _ _ _ _ _ = error "type mismatch"
evalWExp :: WExp -> WExp
evalWExp = transform (either (Left . step) (Right . step))
现在我可以做完全的简化:
Now I can do the complete simplification:
λ evalWExp . Left $ example1
Left (I 1)
λ evalWExp . Right $ example2
Right (B True)
但是为了完成这项工作，我必须做的error和包装/解包的数量只会让我觉得这不雅和错误.
But the amount of error and wrapping/unwrapping I had to do to make this work just makes this feel inelegant and wrong to me.
是否有正确的方法来使用uniplate解决这个问题?
Is there a right way to solve this problem with uniplate?
推荐答案
uniplate 没有正确的方法来解决这个问题，但是有一个正确的方法可以用相同的机制解决这个问题.uniplate 库不支持 uniplate 类型为 * -> 的数据类型.*，但我们可以创建另一个类来适应它.这是一个用于 * -> 类型的最小单板库.*.它基于 Uniplate 的当前 git 版本，该版本已更改为使用 Applicative 而不是 Str.
There isn't a right way to solve this problem with uniplate, but there is a right way to solve this problem with the same mechanism. The uniplate library doesn't support uniplating a data type with kind * -> *, but we can create another class to accommodate that. Here's a little minimal uniplate library for types of kind * -> *. It is based on the current git version of Uniplate that has been changed to use Applicative instead of Str.
{-# LANGUAGE RankNTypes #-}
import Control.Applicative
import Control.Monad.Identity
class Uniplate1 f where
uniplate1 :: Applicative m => f a -> (forall b. f b -> m (f b)) -> m (f a)
descend1 :: (forall b. f b -> f b) -> f a -> f a
descend1 f x = runIdentity $ descendM1 (pure . f) x
descendM1 :: Applicative m => (forall b. f b -> m (f b)) -> f a -> m (f a)
descendM1 = flip uniplate1
transform1 :: Uniplate1 f => (forall b. f b -> f b) -> f a -> f a
transform1 f = f . descend1 (transform1 f)
现在我们可以为Expression编写一个Uniplate1实例:
Now we can write a Uniplate1 instance for Expression:
instance Uniplate1 Expression where
uniplate1 e p = case e of
Add x y -> liftA2 Add (p x) (p y)
Mul x y -> liftA2 Mul (p x) (p y)
Eq x y -> liftA2 Eq (p x) (p y)
And x y -> liftA2 And (p x) (p y)
Or x y -> liftA2 Or (p x) (p y)
If b x y -> pure If <*> p b <*> p x <*> p y
e -> pure e
This instance is very similar to the emap function I wrote in my answer to the original question, except this instance places each item into an Applicative Functor. descend1 simply lifts its argument into Identity and runIdentity's the result, making desend1 identical to emap. Thus transform1 is identical to postmap from the previous answer.
现在，我们可以根据transform1来定义reduce.
Now, we can define reduce in terms of transform1.
reduce = transform1 step
这足以运行一个例子:
"reduce"
If (And (B True) (Or (B False) (B True))) (Add (I 1) (Mul (I 2) (I 3))) (I 0)
I 7
这篇关于使用 Uniplate 简化 GADT的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
