Блог

Главная - Вопросы по программированию - Оценка вложенного типа данных

Оценка вложенного типа данных

#haskell

#haskell

Вопрос:

Я пытаюсь написать функцию, которая оценивает вложенный логический тип данных. Моя проблема возникает из-за сравнения типа данных внутри типа данных. Первые два (Lit и Or) компилируются нормально, но я не понимаю, как включить первый тип в функцию SecondExpr. Когда я набираю его, я чувствую, что выбираю самый длинный возможный путь, когда работает что-то более короткое.

Вот два типа данных.

 data Expr = Val Int
          | Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          | If SecondExpr Expr Expr

data SecondExpr = Lit Bool
                | Or SecondExpr SecondExpr 
                | EqualTo Expr Expr
                | LessThan Expr Expr

(Еще одна проблема, с которой я сталкиваюсь, — это создание примеров SecondExpr для тестирования, потому что концептуально я рассматриваю каждое выражение как 6 различных типов выражения. Это означает, что для каждого выражения Expr будут сотни стражей.)

Ниже приведен код на данный момент:

 eval :: SecondExpr -> Bool
eval (Lit n)                   = n
eval (Or e1 e2)
  | True amp;amp; True               = True
  | True amp;amp; False              = True
  | False amp;amp; True              = True
  | otherwise                  = False
eval (EqualTo e1 e2)
  | (Add e1 e2) == (Add e1 e2) = True
  | (Sub e1 e2) == (Sub e1 e2) = True
  | (Mul e1 e2) == (Mul e1 e2) = True
  | (Div e1 e2) == (Div e1 e2) = True
  | otherwise                  = False
eval (LessThan e1 e2)
  | (Add e1 e2) == (Add e1 e2) = True
  | (Sub e1 e2) == (Sub e1 e2) = True
  | (Mul e1 e2) == (Mul e1 e2) = True
  | (Div e1 e2) == (Div e1 e2) = True
  | otherwise                  = False

Это ошибка, которую я получаю:

     * No instance for (Eq Expr) arising from a use of `=='
    * In the expression: (Add e1 e2) == (Add e1 e2)
      In a stmt of a pattern guard for
                     an equation for `eval':
        (Add e1 e2) == (Add e1 e2)
      In an equation for `eval':
          eval (EqualTo e1 e2)
            | (Add e1 e2) == (Add e1 e2) = True
            | (Sub e1 e2) == (Sub e1 e2) = True
            | (Mul e1 e2) == (Mul e1 e2) = True
            | (Div e1 e2) == (Div e1 e2) = True
            | otherwise = False
   |
24 |   | (Add e1 e2)       == (Add e1 e2) = True
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Итак, я знаю, что мой синтаксис неправильный, но как вы заменяете выражение в функции выражения?

Комментарии:

1. True amp;amp; True то же самое, что и просто True . Защитное выражение | True всегда выполняется успешно; это все равно, что вообще не иметь защиты: eval (Or e1 e2) = True .

2. Мне неясно, для чего SecondExpr это нужно. Вы, вероятно, хотите, например. eval (Or e1 e2) = eval e1 || eval e2 вместо того, что вы написали, что является постоянным True . Для EqualTo вам понадобится eval' on Expr для некоторого приравниваемого типа, затем просто eval (EqualTo e1 e2) = eval' e1 == eval' e2 (и вы можете увидеть, как легко адаптировать это для LessThan ). Это также решает проблему комбинаторного взрыва, которую вы наблюдали, хотя, как я уже сказал, общий дизайн кажется сомнительным, но трудно быть более полезным без большего контекста.

Ответ №1:

Вам понадобятся две функции оценки:

 evalNum :: Expr -> Int

и

 evalBool :: SecondExpr -> Bool

Ни один из них не должен использовать никаких предохранителей ( | ... ).

Например, evalBool будет выглядеть так:

 evalBool (Lit n) = n
evalBool (Or e1 e2) = evalBool e1 || evalBool e2
evalBool (EqualTo e1 e2) = evalNum e1 == evalNum e2
evalBool (LessThan e1 e2) = evalNum e1 < evalNum e2

Подвыражения вычисляются рекурсивно с помощью соответствующих eval функций, а результаты объединяются с использованием соответствующих операторов Haskell (таких как || , == , < ).

Реализация evalNum оставлена в качестве упражнения для читателя.