2

データ型 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

上記のプログラムを実行した後は簡単なはずですが、どこから始めればよいかさえわかりません。注: できるだけ多くの再帰を使用したいと考えています。前もって感謝します！

4

2 に答える 2

3

aツリー関数は、 type の値を作成するために含まれるツリーで機能しましbたが、Expデータ型には、結合 (またはカウント) する式以外は何も含まれていません。出現回数をカウントできる 2 番目のデータ型を作成しましょう。である方がよいので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には項が 1 つしかない (サブ項がない) ため、最初からsemptyの数を増やします。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)

あなたは今アイデアを得ることができると思います。

于 2013-07-18T23:57:33.927 に答える