2

次のデータ構造の入力を解析するためのreadsPrecの実装で問題が発生しました。

data Term = Monom Int Int
          | Addition Term Term
          | Subtraction Term Term
          | Multiplication Term Term
          | Division Term Term

私はすでに、monomを次のように見せるshowのインスタンスを実装しました。

let k  = Monom 2 3
Main.show k

戻り値：

(2x^3)

と

let m = Addition k k
Main.show m

戻り値：

(2x^3)+(2x^3)

その間、私はその仕事を5時間ほど座っていて、どう対処すればいいのかまったくわかりません。私の最初のアプローチは次のようになりました。

instance Read Term where
  readsPrec _ inp = let[(a,b)] = lex inp in
   case a of
   "x" -> readsPrec 0 b
   "^" -> [(Monom 1 (read b::Int), "")]
   c  -> let[(d, "")] = readsPrec 0 b in
     [(Monom (read c::Int) ((\(Monom x y) -> y) d), "")]

最初は、このコードがMonom以外では機能しないことに気付くまで、とても幸せでした。誰かがより良いアプローチを得ましたか？

4

1 に答える 1

2

はい。これは少し圧倒されているように見えるかもしれませんが、Parsecのようなパーサーコンビネーターライブラリを使用すると、コードをきちんと書くことができます。例えば

import Text.ParserCombinators.Parsec
import Data.Maybe

monom, term :: Parser Term
operations :: [(Char,(Term -> Term -> Term))] -> Parser Term

int :: Parser Int
int = fmap read $ many1 digit

monom = do
         coef <- int
         string "x^"
         power <- int
         return $ Monom coef power


operations ops = do
                   a <- term
                   c <- choice . map (char . fst) $ ops
                   b <- term
                   return $ (fromJust $ lookup c ops) a b

term = do
        char '('
        x <- monom <|> (operations [('+', Addition), ('-', Subtraction), ('*', Multiplication), ('/', Division)])
        char ')'
        return x

term' = do 
         x <- term
         eof 
         return x

readTerm :: String -> Term
readTerm string = case parse term' "" string  of
                        Left err -> error . show $ err
                        Right term -> term

説明として、（角かっこなしで）のmonomようなものを解析し、タプルのリストを取得し、その後に操作文字の1つ、続いて別のを解析し、適切なデータコンストラクターを使用して適切なインスタンス（行）を作成します。2x^3operationstermtermfromJust $ lookup c ops

termパーサーは、角monomかっこで囲まれた操作の1つまたは1つを解析します。term'文字列全体を解析します（つまり、パーサーが文字列の最後まで実行されることを確認します）。readTermパーサーの単なる「よりクリーンな」バージョンです。

いくつかの例：

> readTerm "(2x^3)"
Monom 2 3
> readTerm "((2x^3)+(2x^3))"
Addition (Monom 2 3) (Monom 2 3)
> readTerm "(((2x^3)+(2x^3))*(2x^3))"
Multiplication (Addition (Monom 2 3) (Monom 2 3)) (Monom 2 3)

上記は非常に基本的なバージョンであり、簡単に拡張して、たとえば、coef用語をオプションにして、x^2として解析しMonom 1 2たり、power用語をオプションにして、として2x解析したりすることができMonom 2 1ます。（このoption関数は、この特定の変更に非常に役立ち、1行または2行だけ追加します。）

（注：これは、アプリケーションスタイルで記述された方が効率的でエレガントな場合があります。

import Control.Applicative

monom = Monom <$> int <* string "x^" <*> int

しかし、これは変更を加えるときに少し厄介になる可能性があります。）

于 2012-10-22T10:08:42.617 に答える