Haskell中实现可结合操作表达式左结合函数的技术求助

要解决任意长度可结合操作的左结合转换问题，不能靠硬编码固定层数的模式匹配，得用递归+列表收集+折叠的方式处理任意嵌套的同操作表达式链。

完整实现步骤 #

首先补全缺失的Op类型定义（区分可结合/非结合操作）：

data Op = Add | Mul | Sub | Div deriving (Eq, Show)
data Expr = Val Int | App Op Expr Expr deriving (Eq, Show)

1. 标记可结合操作

先写一个辅助函数判断操作是否支持左结合：

isAssociative :: Op -> Bool
isAssociative Add = True  -- 加法可结合
isAssociative Mul = True  -- 乘法可结合
isAssociative _ = False   -- 减法、除法等非结合操作不处理

2. 收集同操作的所有子项

递归遍历表达式，把所有嵌套的同操作子表达式展开成一个列表，同时确保每个子项已经是左结合的：

collectAssoc :: Op -> Expr -> [Expr]
collectAssoc op expr = case expr of
  -- 如果当前节点是同类型的可结合操作，递归收集左右子项
  App op' e1 e2 | op == op' -> collectAssoc op e1 ++ collectAssoc op e2
  -- 非目标操作或常量，先处理自身的左结合再加入列表
  _ -> [leftAssociate expr]

3. 核心左结合转换函数

递归处理所有子表达式，对可结合操作使用foldl将收集到的子项从左到右折叠成左结合链：

leftAssociate :: Expr -> Expr
leftAssociate (Val n) = Val n  -- 常量直接返回
leftAssociate (App op e1 e2)
  -- 处理可结合操作：收集所有子项后左折叠
  | isAssociative op = case collectAssoc op (App op e1 e2) of
      [] -> error "无效的空表达式"
      [x] -> x
      xs -> foldl (\acc x -> App op acc x) (head xs) (tail xs)
  -- 非结合操作：递归处理子表达式后原样组合
  | otherwise = App op (leftAssociate e1) (leftAssociate e2)

测试示例 #

比如输入嵌套加法表达式：

testExpr :: Expr
testExpr = App Add (Val 1) (App Add (Val 2) (App Add (Val 3) (Val 4)))

调用leftAssociate testExpr会返回左结合形式：

App Add (App Add (App Add (Val 1) (Val 2)) (Val 3)) (Val 4)

方案优势 #

• 无需硬编码多层模式匹配，自动处理任意长度的同操作嵌套链
• 仅对可结合操作生效，非结合操作保持原有结构
• 递归处理子表达式，确保整个表达式树的所有可结合子链都被左结合转换

内容的提问来源于stack exchange，提问作者ali Mustapha