如何在Haskell递归数据类型中实现分配属性?

Question

我有一个任务来纠正功能expand。

infixl 6 :+:
infixl 7 :*:
data Expr = Val Int | Expr :+: Expr | Expr :*: Expr
deriving (Show, Eq)
expand :: Expr -> Expr
expand ((e1 :+: e2) :*: e) = expand e1 :*: expand e :+: expand e2 :*: expand e
expand (e :*: (e1 :+: e2)) = expand e :*: expand e1 :+: expand e :*: expand e2
expand (e1 :+: e2) = expand e1 :+: expand e2
expand (e1 :*: e2) = expand e1 :*: expand e2
expand e = e
-- expression example: (Val 1 :+: Val 2 :+: Val 3) :*: (Val 4 :+: Val 5)
-- which is equivalent to (1 + 2 + 3) * (4 + 5)
-- expression, that given fucntion evaluates our example to: 
--(Val 1 :+: Val 2) :*: (Val 4 :+: Val 5) :+: Val 3 :*: (Val 4 :+: Val 5)
-- expression that corrected function must evaluate our example to:
-- Val 1 :*: Val 4 :+: (Val 1 :*: Val 5 :+: (Val 2 :*: Val 4 :+: (Val 2 :*: Val 5 :+: (Val 3 :*: Val 4 :+: Val 3 :*: Val 5))))
-- answers like (Val 1 :*: Val 2) :+: (Val 3 :*: Val 4) 
-- and          (Val 4 :*: Val 3) :+: (Val 1 :*: Val 2)
-- are considered to be equal

它无法正常工作，因为它只打开一次括号。所以，我把它修改成这样：

infixl 6 :+:
infixl 7 :*:
data Expr = Val Int | Expr :+: Expr | Expr :*: Expr
deriving (Show, Eq)
expand :: Expr -> Expr
expand ((e1 :+: e2) :*: e) = (expand $ e :*: e1) :+: (expand $ e :*: e2)
expand (e :*: (e1 :+: e2)) = (expand $ e :*: e1) :+: (expand $ e :*: e2)
expand (e1 :+: e2) = expand e1 :+: expand e2
expand expr@(e1 :*: e2) = if isMul expr
then expr
else expand $ expand e1 :*: expand e2
expand e = e
isMul :: Expr -> Bool
isMul (Val a :*: expr) = isMul expr 
isMul (expr :*: Val a) = isMul expr
isMul (Val a) = True
isMul  _      = False

添加函数isMul以找到一个边条件：如果我们的表达式(e1 :*: e2)是Val 1 :*: Val 2 :*: Val 3 ...的形式，那么我们的函数expand停止扩展并计算自身的表达式，否则递归继续。

它在我的示例中工作正常~ish。

exp0 = (Val 1 :+: Val 2 :+: Val 3) :*: (Val 4 :+: Val 5)
exp1 = (Val 1) :*: ((Val 2) :+: (Val 3)) :*: (Val 4)
exp2 =  Val 1 :*: (Val 2 :*: (Val 3 :+: Val 4)) 
exp3 = ((Val 1) :+: (Val 2)) :*: ((Val 3) :+: (Val 4))
exp4 =  Val 2 :*: (Val 3 :+: Val 4)
exp5 = (Val 3 :+: Val 4) :*: Val 2
exp6 =  Val 3 :+: Val 4  :*: Val 2
exp7 =  Val 3 :*: (Val 4 :*: Val 2)
exp8 = (Val 3 :*: Val 4) :*: Val 2
exp9 =  (Val 1 :+: Val 2 :+: Val 3) :*: (Val 4 :+: Val 5) :*: (Val 6) :*: ((Val 7) :+: (Val 8)) :*: (Val 9)

但由于超过时间限制而未能通过一些测试。我想，递归不会在某个地方停止，在它必须停止的地方，但我看不到在哪里。

Answer 1

错误在于函数isMul：表达式的结果isMul ((Val 3 :*: (Val 4 :*: Val 2)) :*: ((Val 3 :*: Val 4) :*: Val 2))False。发生，因为data Expr本质上是一棵树，所以表达式Val 1 :*: (Val 2 :*: (Val 3 :*: Val 4))和(Val 1 :*: Val 2) :*: (Val 3 :*: Val 4)实际上是不同的。因此，我为isMul写了一个更普遍的实现：

isMul :: Expr -> Bool
isMul (e1 :*: e2) = isMul e1 && isMul e2
isMul (Val a) = True
isMul  _      = False

这使得程序按预期工作。