Haskell readsPrec рациональные функции

У меня возникла проблема с реализацией readsPrec для анализа ввода для следующей структуры данных:

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

Я уже реализовал экземпляр 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), "")]

Сначала я был очень счастлив, пока не заметил, что этот код не работает ни для чего, кроме Монома. У кого-нибудь есть лучший подход?


instance input haskell rational-number
person RodrigoDela    schedule 22.10.2012    source источник
comment
Я предлагаю вам взглянуть на этот ответ и рассмотреть только deriving Read and Show для вашего типа данных. Конечно, вы по-прежнему можете анализировать ввод (и отображать вывод) в формате, более удобном, чем Addition (Monom 1 3) (Monom 2 3). Так ли это? Если это так, вы можете использовать генератор синтаксических анализаторов или библиотеку синтаксического анализа, например Parsec. Но не на 100% понятно, что вы хотите сделать.   -  person Rafael Caetano    schedule 22.10.2012

Ответы (1)


arrow_upward
2
arrow_downward

да. Это может показаться слишком мощным, но использование библиотеки комбинатора синтаксического анализатора, такой как 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 анализирует что-то вроде 2x^3 (без скобок), operations берет список кортежей и анализирует term, за которым следует один из символов операции, за которым следует еще один term, а затем использует соответствующий конструктор данных для создания правильного экземпляра ( строку fromJust $ lookup c ops).

Синтаксический анализатор term анализирует либо monom, либо одну из операций, заключенных в квадратные скобки. 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

но это может стать немного громоздким при внесении изменений.)

person huon    schedule 22.10.2012
comment
Вау, спасибо! Это решение работает очень хорошо. К сожалению, это не соответствует моему требованию реализовать решение с использованием readsPrec. Видите ли вы возможность реализовать это решение с помощью readsPrec? Я очень ценю вашу помощь! - person RodrigoDela; 22.10.2012
comment
Меня попросили реализовать это таким образом. Это имеет значение? Я также хочу улучшить свое понимание самого класса Read... - person RodrigoDela; 22.10.2012
comment
@RodrigoDela: написать свой собственный readsPrec, мягко говоря, довольно сложно! Посмотрите здесь чтобы увидеть, как анализировать более простой тип со значениями, такими как Leaf 3 :^: (Leaf 4 :^: Leaf 5), возможно, вы можете адаптировать это для нескольких операций? - person yatima2975; 22.10.2012
comment
Я только что посмотрел вашу ссылку. Не могли бы вы объяснить, что на самом деле делает эта строка: ("Leaf",s) <- lex r ? - person RodrigoDela; 23.10.2012