2

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

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

完成上述程序后似乎应该很简单，但我什至不知道从哪里开始。注意：我想尽可能多地使用递归。提前致谢！

4

2 回答 2

3

您的 tree 函数与包含a生成 type 值的树一起使用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

ANumber只有一个项（没有子项），所以我们将从 s 开始empty并增加NumberTerms 的数量：

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)

你现在明白了，我希望你能完成。

于 2013-07-18T23:57:33.927 回答
1

这是一个选项，与 AndrewC 的答案略有不同。与其创建一个单独的数据类型，将Exp类型的构造函数表示为数字，不如将表达式表示为更简单的基类型上的自由 monad。例如，如果基类型是

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)

那么你的表达式可以定义为自由单子 over ExpT，Int作为根类型

type Exp = Free ExpT Int

现在你inc像 AndrewC 的帖子那样写

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)]
于 2013-07-19T13:50:36.187 回答