Haskell: преобразование любого Ast в строку

ProgramBox

Haskell: преобразование любого Ast в строку

Post author:admin
Запись опубликована:14 марта, 2023
Post category:Вопросы по программированию

#haskell

Вопрос:

У меня есть назначение, в котором я должен запрограммировать функцию оценки eval::Ast -> String, которая преобразует любой Ast в строку. например:

 >eval (parse "hel   lo") 
"hello"

> eval (parse "mi   2 * la")
"milala"

Я создал функцию синтаксического анализа, которая, например, принимает «hel lo» и возвращает плюс (слово «hel») (слово «lo»)

Но я очень не уверен в том, как должна выглядеть функция (и типы), поскольку в оценке AST задействовано несколько типов… Кто-нибудь, кто может направить меня в правильном направлении?

AST определяется как

 data Ast 
 = Word String
 | Num Int
 | Mult Ast Ast
 | Plus Ast Ast
 | Minus Ast Ast
 deriving (Eq, Show)

1. «Правила, приведенные во введении», неизвестны большинству людей. Выполняется ли 2 3 вычисление в "5" or "23" ? Как насчет "hello" - "world" (я могу представить оба "hello" , "hel" , и "he" ) ? "hello" * "world" ? (Нелегко придумать что-либо значимое для этого последнего.)

2. О, ха-ха, я думал, что эти правила не имеют отношения к задаче, с которой у меня возникли проблемы, поэтому я ими не делился. Но это в основном то, что * имеет наивысший приоритет, в то время - как и ассоциируется справа. "cabbage - aabcd" должно быть оценено "be" и "3 * yes" должно быть оценено "yesyesyes" и т.д. @molbdnilo

3. Я думаю, вам нужно иметь две функции оценки; одна для оценки числовых сумм и произведений, когда они встречаются в качестве аргументов рядом со строкой, и одна для оценки чисел как строк для конечного вывода. Рассмотрим mi (1 1) * la , к которому, как я предполагаю, выполняется синтаксический Plus (Word "mi") (Mul (Plus (Num 1) (Num 1)) (Word "la")) анализ.

4. Вы также можете подумать eval :: AST -> Either String String , поскольку неясно, что "foo" * "bar" может быть оценено, несмотря на то, что оно грамматически правильное.

5. Plus (Num 1) (Num 2) Вероятно, следует упростить что-то подобное Plus (Num 3) , прежде чем пытаться оценить его как строку. Я бы написал две функции, simplify :: AST -> AST и eval :: AST -> Either String String . eval x = eval' (simplify x) where ... , eval' являющуюся функцией, которая выполняет такие вещи, как eval' (Num x) = show x .

Ответ №1:

eval :: AST -> String это то, что определяет семантику ваших операций. Например, eval (Plus (Word x) (Word y)) == x y .

Однако, что должно eval (Plus x y) получиться, если оба аргумента являются числами? Должен ли он объединить их или добавить их численно? Что, если любой из них сам по себе является одним из значений Plus , Minus , или Mul ? Сначала вам нужно будет их оценить, но тогда вы не сможете определить, является ли результат like "2" действительно строкой или результатом числа.

Вам также нужно решить, AST можно ли оценить каждый: имеет ли Mul (Word "x") (Word "y") смысл? Если нет, что String бы вы вернули?

Я бы предложил две вещи:

Сначала определите simplify функцию, которая позаботится о сокращении AST до чего-то более простого. Он позаботится о выполнении таких вещей, как числовая арифметика в случае Plus (Num ...) (Num ...) , но оставит такие вещи, как Word x или Plus (Word x) (Num y) без изменений.

 simplify :: AST -> AST
simplify (Num x) = Num x  -- Easy case done for you; no simplification necessary
simplify (Word x) = ...
-- Hint: in each of the following, you need to recursively simplify the operands.
-- Once you do that, you can either simplify further, or return a new
-- node to be evaluated.
simplify (Plus x y) = ...
simplify (Minus x y) = ...
simplify (Mul x y) = ...

Во-вторых, define eval :: AST -> Either String String , сначала будет использовать simplify в своем аргументе, затем выполнять индивидуальные преобразования AST s Strings , где это возможно, и возвращать соответствующее сообщение об ошибке, где его нет.

 eval :: AST -> Either String String
eval x = eval' (simplify x)
   where eval' (Word x) = Right x  -- Easy case done for you
         eval' (Num x) = ...
         -- simplify will have reduced all the Num   Num, Num - Num, and
         -- Num * Num nodes to single Num nodes already.
         eval' (Plus (Word x) (Word y)) = x    y  -- Other easy case done above
         eval' (Plus x y) = ...
         eval' (Minus (Word x) (Word y)) = ...
         eval' (Minus x y) = ...
         eval' (Mul (Word x) (Word y)) = ...
         eval' (Mul x y) = ...

Обратите внимание, что вы могли бы предположительно определить некоторые комбинации в любом eval' или simplify , например

 simplify (Plus (Word x) (Word y)) == Word $ x    y

оставляя более сложные (и, возможно, невозможные) случаи eval .

1. Теперь все имеет гораздо больше смысла! Большое вам спасибо, вы великолепны

2. Я ввожу, например simplify (Mult x y) = "(" (show x) "*" (show y) ")" , и получаю сообщение «Не удалось сопоставить ожидаемый тип ‘Ast’ с фактическим типом‘[Char]’» — ошибка. Я пробовал разные способы упрощения операндов, но, думаю, я что-то неправильно понял : S @chepner

3. simplify не возвращает a String ; он возвращает an AST (возможно, то же самое, что вы передали в качестве аргумента). Например, simplify (Mult (Num 3) (Num 5)) == Num 15 . Если вы на самом деле не можете выполнить умножение, вы просто возвращаете узел как есть и позволяете eval попытаться что-то с ним сделать. Идея состоит в том, чтобы не преобразовывать преждевременно Num 5 в "5" , только чтобы узнать, что вам нужно умножить другую строку на 5 . Теперь вы не знаете, был ли исходный ввод 5 * "foo" или "5" * "foo" .

4. Ага, хорошо! Но что, если я хочу оценивать только строки, что я должен туда поместить? Я бы выдал 5 * 2 ошибку, но позволил 3*hi вычислить hihihi

5. simplify (Mul (Num 3) (Word "hi")) == (Mul (Num 3) (Word "hi")) ; вы можете передать это напрямую eval .