1

Expr算術演算のクラスを作ります

class Expr a where
  mul :: a -> a -> a 
  add :: a -> a -> a
  lit :: Integer -> a

このようなものを「解析」したい: mul ( add (lit 3) (lit 2)) (lit 4) = (3+2)*4

そして私はデータ型を持っています:

data StackExp = PushI Integer
              | PushB Bool
              | Add
              | Mul
              | And
              | Or
                deriving Show

と

type Program = [StackExp] --i use this type for function of stack calculator later

私の仕事は次のとおりです。Exprfor タイプのインスタンスを作成する必要がありますProgram

より具体的に - この変換を行いたい: mul ( add (lit 3) (lit 2)) (lit 4)->>>[PushI 2, PushI 3, Add, PushI 4, Mul]

[[StackExp]]インスタンス宣言の出力で受け取るため、問題があります。

私の試み：

instance Expr Program where
  lit n = (PushI n):[]
  add exp1 exp2 = exp1:(exp2:[Add]) 
  mul exp1 exp2 = exp1:(exp2:[Mul])

すべての部分式をリストに連結する方法がわかりません

---------------- コンパイラ エラーは次のようになります------------------------

Couldn't match type `[StackExp]' with `StackExp'
    Expected type: StackExp
      Actual type: Program

..........

4

1 に答える 1

3

したがって、基本的にやりたいことは、式言語の抽象構文 (型 class Expr) から単純なスタック マシン ( type の要素のリスト) のコードにコンパイルすることですStackExpr。

そのときにすぐに遭遇する問題の 1 つは、Haskell 98 または Haskell 2010 だけ[StackExpr]では、クラスのインスタンスを宣言できないことです。たとえば、GHC は次のように文句を言います。

Illegal instance declaration for `Expr [StackExp]'
  (All instance types must be of the form (T a1 ... an)
   where a1 ... an are *distinct type variables*,
   and each type variable appears at most once in the instance head.
   Use -XFlexibleInstances if you want to disable this.)
In the instance declaration for `Expr [StackExp]'

これを回避するにはProgram、(現在のような単なる型シノニムではなく) 型同型として定義できます。

newtype Program = P [StackExp] deriving Show

次に、Program をクラス Expr のインスタンスにします。FlexibleInstances(または、上記のエラー メッセージで提案されているように有効にすることもできます。)

これで、必要なインスタンス宣言を記述できます。

instance Expr Program where
  mul (P x) (P y) = P (x ++ y ++ [Mul])
  add (P x) (P y) = P (x ++ y ++ [Add])
  lit n           = P [PushI n]

つまり、乗算と加算では、最初にオペランドをコンパイルしてから、それぞれMulorAdd命令を生成します。リテラルの場合、対応するプッシュ命令を生成します。

この宣言により、あなたの例では次のようになります。

> mul (add (lit 3) (lit 2)) (lit 4) :: Program
P [PushI 3,PushI 2,Add,PushI 4,Mul]

（あなたの例とは異なります。オペランドの順序を に交換しますAdd。加算は交換可能であるため、このバージョンも受け入れられると想定します。）

もちろん、スタックプログラム用の小さなエバリュエーターを書くのも楽しいです:

eval :: Program -> [Integer]
eval (P es) = go es []
  where
    go [] s                   = s
    go (PushI   n : es) s     = go es (n : s)
    go (Add : es) (m : n : s) = go es ((m + n) : s)
    go (Mul : es) (m : n : s) = go es ((m * n) : s)

（とにかく整数式しか扱っていないように見えるので、ここではブール値を扱う命令を無視していることに注意してください。）

あなたの例では、

> eval (mul (add (lit 3) (lit 2)) (lit 4))
[20]

これはほぼ正しいようです。

于 2013-05-04T20:23:35.630 に答える