將數據類型轉換爲映射

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)]