Оценка арифметического выражения в Haskell - PullRequest
Новая
       50

Оценка арифметического выражения в Haskell

0 голосов
/ 14 февраля 2019

Здесь я пытаюсь оценить выражение в Haskell, используя определенные значения типа данных Exp.Тип функции будет eval :: Exp -> Int, а тип данных будет таким: 

data Exp = Num Int
       | Exp :+: Exp
       | Exp :-: Exp
       | Exp :*: Exp
       | Exp :/: Exp
       deriving (Show)

, и значения, которые я пытаюсь оценить, таковы: 

 4 + 5 * 6 , respecting correct precedences of the operators
 4 + 5 + 6 , respecting, that + binds left-associative
 (4 + 3) * (5 - 2)
 4 + (4 / (2 - 2))

Пока эта логика работает нормальночто: 

eval :: Exp -> Int
eval (Num a) = a 
eval (a :+: b) = (eval a) + (eval b)
eval (a :-: b) = (eval a) - (eval b)
eval (a :*: b) = (eval a) * (eval b)
eval (a :/: b) = (eval a) `div` (eval b)

Когда я передаю это, я получаю 3 как вывод, который является правильным: 

eval (Num 2 :+: Num 2 :-: Num 1) 
output = 3

но я запутался, как он оценил вторую часть выражения, которая:-: что я понял, единственный шаблон, соответствующий первой итерации, был eval (a :+: b) = (eval a) + (eval b), который возвращал 4 как вывод, как он переносит 4 на следующую итерацию для выполнения операции :-:?

до этого япытался что-то вроде этого: 

eval :: Exp -> Int
eval (Num a) = a
eval (<b>Num</b> a :+: <b>Num</b> b) = eval (<b>Num</b> a) + eval (<b>Num</b> b)
eval (<b>Num</b> a :-: <b>Num</b> b) = eval (<b>Num</b> a) - eval (<b>Num</b> b)
eval (<b>Num</b> a :*: <b>Num</b> b) = eval (<b>Num</b> a) * eval (<b>Num</b> b)
eval (<b>Num</b> a :/: <b>Num</b> b) = eval (<b>Num</b> a) `div` eval (<b>Num</b> b)

он не дал желаемых результатов, а затем я просто изменил его на первую версию.это работало хорошо, но не получило надлежащей семантики этого.Любая помощь?Пожалуйста, не стесняйтесь вдаваться в детали.Заранее спасибо.

Ответы [ 3 ]

0 голосов
/ 14 февраля 2019

Я думаю, что самый простой способ следить за тем, что здесь происходит, - просто следить за оценкой по одному шагу за раз.Поскольку @WillNess объяснил, что порядок операций по умолчанию слева направо, ваш код оценивается следующим образом (каждый отдельный шаг идет непосредственно из одной из строк вашего определения eval): 

eval ((Num 2 :+: Num 2) :-: Num 1)
eval (Num 2 :+: Num 2) - eval(Num 1)
(eval (Num 2 :+: Num 2)) - 1
(eval (Num 2) + eval (Num 2)) - 1
(2 + 2) - 1
4 - 1
3

Надеюсь, это проясняет.

0 голосов
/ 14 февраля 2019

Как указывалось в других ответах, проблема в том, что все ваши конструкторы имеют одинаковый приоритет по умолчанию: они левоассоциативны с высоким (9) приоритетом.Вы можете изменить это, используя директиву infixl. 

data Exp = Num Int
       | Exp :+: Exp
       | Exp :-: Exp
       | Exp :*: Exp
       | Exp :/: Exp
       deriving (Show)

-- Using the same precedences as (+), (-), (*), and (/)
infixl 6 :+:, :-:
infixl 7 :*:, :/:

Теперь eval $ Num 4 :+: Num 2 :*: Num 3 будет корректно возвращать 10 вместо 18.

0 голосов
/ 14 февраля 2019

Исправление по умолчанию для операторов: infixl 9 (см. 4.4.2 Fixity Declarations).

Вы не объявили исправление для своих :+: и т. Д. Операторов.

Это означает, что ваше выражение анализируется как 

eval ((Num 2 :+: Num 2) :-: Num 1)  :: Exp

--     Num 2                        :: Exp 
--               Num 2              :: Exp 
--     Num 2 :+: Num 2              :: Exp 
--                          Num 1   :: Exp 
--    (Num 2 :+: Num 2) :-: Num 1   :: Exp

Таким образом, оценка выполняется как 

  eval ((Num 2 :+: Num 2) :-: Num 1)  -- match with:
  eval (a                 :-: b    ) = (eval a) - (eval b)
                                     =  ....
...