haskell - 将数据类型转换为映射

Question

我想将我的数据类型 Exp 转换为一个映射，其中函数名称(Add、Subtract 等)是键，值是它们在表达式中出现的次数。这是我的数据声明:

data Exp = Number     Int
         | Add        Exp Exp
         | Subtract   Exp Exp
         | Multiply   Exp Exp
         | Divide     Exp Exp
  deriving Show

我可以用 BST 来解决这个问题，但我似乎无法用不同的数据类型来完成这个任务。这是我的 BST 解决方案(如果有帮助的话):

import Data.Map 

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
leaf x = Node x Empty Empty

foldt :: (a -> b -> b) -> b -> Tree a -> b
foldt f a Empty = a
foldt f a (Node x xl xr) = f x ar 
                           where al = foldt f a xl
                                 ar = foldt f al xr

insert' :: Ord a => a -> Map a Int -> Map a Int 
insert' a = insertWith (+) a 1 

toMap :: Ord a => Tree a -> Map a Int
toMap = foldt insert' empty

完成上面的程序后，看起来应该很简单，但我什至不知道从哪里开始。注意:我想使用尽可能多的递归。提前致谢!

Answer 1

您的树函数使用包含 a 的树来生成 b 类型的值，但您的 Exp 数据类型不包含任何内容除了要组合(或计数)的表达式。让我们创建第二种可以计算出现次数的数据类型。最好是Ord，所以我们需要Eq，并且Show将有利于输出:

data Term = NumberTerm | AddTerm | SubtractTerm | MultiplyTerm | DivideTerm
  deriving (Eq, Ord, Show)

其中每一个都代表 Exp 类型的术语。

我已将您的 insert' 重命名为 inc:

inc :: Ord a => a -> Map a Int -> Map a Int 
inc a = insertWith (+) a 1 

---

不，我们已经准备好计算了:

countExp :: Exp -> Map Term Int

Number 只有一项(无子项)，因此我们将从 empty 开始，并增加 NumberTerm 的数量:

countExp (Number _) = inc NumberTerm empty

Add 术语更加复杂。每个表达式都有自己的计数，因此我们对每个子项递归地使用 countExp，然后使用 unionWith (+) 对计数求和。之后，我们inc AddTerm 将当前的Add 术语包含在总计中。

countExp (Add e1 e2) = inc AddTerm $ unionWith (+) (countExp e1) (countExp e2) 

我们可以对Subtract做几乎完全相同的事情:

countExp (Subtract e1 e2) = inc SubtractTerm $ unionWith (+) (countExp e1) (countExp e2) 

我希望你现在明白了，这样你就可以完成。