折叠多项式解析树的最有效方法

Question

我正在研究符号代数系统。我目前正在研究如何从二进制解析树执行多项式 addition/multiplication 。稍后我会认为这是一个通用戒指。

解析与此处不相关——这是解析的输出。形成的解析树。如果这里有什么可以改进的地方，我当然也很乐意了解。

我 'feel' 这个树结构可能是 folded/crushed，但我不太清楚如何去做。我相信我可以一起破解一些东西，但由于我仍在学习 Haskell，我想了解更高级的用户会做什么。

相关代码背景如下

我的两个相关数据声明是：

data Op = Add | Mul
data Tree a = Leaf a | Node Op [Tree a] [Tree a]

这是我的测试示例之一：

-- 3*(x+2)*(x+(5*4))
test = Node Mul [
         Node Mul 
          [Leaf "3"] 
          [Node Add 
            [Leaf "x"] 
            [Leaf "2"]
          ]
         ] 
         [Node Add 
           [Leaf "x"] 
           [Node Mul 
             [Leaf "5"] 
             [Leaf "4"] 
           ]
         ]

这是一个典型的递归树类型，一个节点持有一个操作以及左右树的列表。计算通过以下操作进行。注意：目前都是字符串操作。我需要它们尽可能通用（但稍后会添加进一步的结构，如乘法交换性）。

prod :: [Tree [a]] -> [Tree [a]] -> [Tree [a]]
prod ls rs = [Leaf (l ++ r) | (Leaf l) <- ls, (Leaf r) <- rs]

add :: [Tree [a]] -> [Tree [a]] -> [Tree [a]]
add l r = l ++ r

opOnLeaf :: Op -> [Tree [a]] -> [Tree [a]] -> [Tree [a]]
opOnLeaf op l r  
  | op == Add = add l r
  | op == Mul = prod l r

operate :: Tree [a] -> [Tree [a]]
operate (Node op [Node op2 l2 r2] [Node op3 l3 r3]) = operate (Node op (operate (Node op2 l2 r2)) (operate (Node op3 l3 r3)))
operate (Node op [Node op2 l2 r2] r) = operate (Node op (operate (Node op2 l2 r2)) r)
operate (Node op l [Node op2 l2 r2]) = operate (Node op l (operate (Node op2 l2 r2)))
operate (Node op l r) = opOnLeaf op l r

我认为我在 operate 中的变量名很丑陋，但我想首先确保它起作用。使它变得丑陋也使它更加突出。简直是在叫我找更好的办法。

现在，我想使用 fold 或 foldMap，但我运行遇到的问题是我在每个操作中都有不同的幺半群（即 (*) 和 (+)。并且这只是开始——我将添加其他几个操作。所以我需要像 'variable monoid' 之类的东西，或者可能是其他一些操作是首先获取幺半群的地图。我不确定。

问题：给定这棵二叉树，每个节点都有多个操作，如何折叠这个结构？有没有更好的方法将其写为 Foldable 或其他结构的实例？我还打算添加其他几个二进制操作。理想情况下，我想要一个可以无限扩展的结构。我假设一旦解决了 2，我们就可以有效地解决 n。

Tree drawing corresponding to test example

Answer 1

“弃牌”在普通话中有两个相关但不同的含义。

Fold 在 Foldable. Viewing the datatype as a container, Foldable gives you access to the container's elements while throwing away any information about the shape of the container itself. (This is also the sense in which lens's Fold 中使用了该术语。）并非每个数据类型都是 Foldable — 只有那些可以被视为容器的数据类型。
“折叠”也可以表示“变形”，这是一种编写高阶函数的技术，可将结构简化为汇总值。每个数据类型都有对应的变质，但变质的签名取决于数据类型。

当您谈论的数据类型是 [] 时，“折叠”的两种含义恰好重合（这部分解释了两种含义的混淆），但通常情况下它们不会。您的 Tree 恰好是任何一种弃牌的合适人选，根据您的问题我无法完全判断您想要哪种弃牌，所以我将向您展示如何进行这两种弃牌。

编写Foldable实例的最简单方法是打开DeriveFoldable。

{-# LANGUAGE DeriveFoldable #-}
data Tree a = Leaf a | Node Op [Tree a] [Tree a]
  deriving (Foldable)

但为了便于理解，我将在此处写出实例：

instance Foldable Tree where
    -- foldr :: (a -> b -> b) -> b -> Tree a -> b
    foldr f z (Leaf x) = f x z
    foldr f z (Node _ ls rs) = foldr foldTree z (ls ++ rs)
        where foldTree t z' = foldr f z' t

想法是将树遍历到底部，将 f 应用于每个 Leaf 内的值。有关此代码的几点注意事项：

foldr 是一个重载函数（它是 Foldable 的一个方法），在第二个子句中我在两种不同的类型中使用它。 foldTree 中的 foldr 是对 Tree 的 foldr :: (a -> b -> b) -> b -> Tree a -> b 定义的递归调用。上面一行中的 foldr 是对常用列表 foldr :: (a -> b -> b) -> b -> [a] -> b.
foldr 丢弃信息！在 Node 的情况下，您可以从 _ 看到 Op 掉在地上。我们还将 ls 和 rs 一起粉碎成一个列表，忘记了它们曾经在两个列表中。

所以 Foldable 就是寻找容器内的物品，同时丢弃有关容器本身的任何信息。说白了，Foldable就是“toList-as-a-class”。

Foldable 非常适合容器类型和其他抽象数据类型，您希望在其中公开类似集合的接口，同时隐藏数据结构的内部表示。在你的例子中，你提到你想根据树内的 Op 应用操作 + 或 *，但是 Op 被丢弃通过 Foldable。所以看起来 Foldable 不是你想要做的事情的正确工具。

如果您想将数据类型缩减为汇总值而不丢弃有关结构的任何信息，您需要变形。

要推导出变质的签名，请遵循这个秘诀。

cata 采用您的数据类型的值和 returns 汇总值 b。
您的数据类型的每个构造函数对应于 cata 的一个参数。这些参数中的每一个都是一个 returns a b.
数据类型构造函数的每个字段对应于相应函数的参数之一。
数据类型本身的递归提及成为摘要值b。

让我们为您的 Tree 执行这些步骤。首先，cataTree 取一个 Tree 和 returns 一个汇总值 b.

cataTree :: ??? -> Tree a -> b

查看Tree的定义，我们看到两个构造函数。所以 cataTree 将有两个函数参数，一个用于 Leaf ，一个用于 Node.

cataTree :: ({- Leaf -} ??? -> b) -> ({- Node -} ??? -> b) -> Tree a -> b

查看 Leaf 构造函数，我们看到一个字段。所以 Leaf 函数只有一个参数。

cataTree :: (a -> b) -> ({- Node -} ??? -> b) -> Tree a -> b

现在让我们看看Node。 Node 有三个参数，但其中两个是 Tree 的列表。我们想用相应的汇总值替换每个 Tree。所以 cataTree 的最终签名是

cataTree :: (a -> b) -> (Op -> [b] -> [b] -> b) -> Tree a -> b

实现 cataTree 是遵循类型的问题。

cataTree leaf _ (Leaf x) = leaf x
cataTree leaf node (Node op ls rs) =
    node op (fmap (cataTree leaf node) ls) (fmap (cataTree leaf node) rs)

折叠多项式解析树的最有效方法

Most effective way to fold polynomial parse tree

parsing

haskell

fold

parse-tree