将数据类型转换为映射

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有一个学期（无subterms），所以我们将从empty开始并增加NumberTerm s的数字：

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) 

你的想法，现在我希望这样你就可以玩完。

Answer 2

下面是一个选项，这是AndrewC答案的一个细微变化。而不是创建一个单独的数据类型来表示您的Exp类型的构造函数为数字，您可以用简单的基本类型将表达式表示为自由单体。例如，如果基类型是

import Control.Monad.Free 
import Data.Map 

data ExpT a = Number a 
      | Add a a 
      | Subtract a a 
      | Multiply a a 
      | Divide a a 
      deriving (Eq,Ord,Show) 

那么你的表情可以作为根型

type Exp = Free ExpT Int 

现在你写inc在AndrewC的职位

被定义为在 ExpT免费的单子，用 Int

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

和countExp功能又非常相似

countExp :: Exp -> Map (ExpT()) Int 
countExp (Free (Number _)) = inc (Number()) empty 
countExp (Free (Add a b)) = inc (Add()()) $ unionWith (+) (countExp a) (countExp b) 

等等。你可能会想定义创建表达式

number :: Int -> Exp 

number n = Free (Number (Pure n)) 
add a b = Free (Add a b) 
sub a b = Free (Subtract a b) 
mul a b = Free (Multiply a b) 
divide a b = Free (Divide a b) 

和最终结果了一些方便的功能是

>>> countExp (add (number 1) (number 2)) 
fromList [(Number(),2),(Add()(),1)]