Haskell как определить, простое выражение или нет?

Question

Я пишу функцию, чтобы определить, является ли выражение простым или нет. В моем случае простое выражение - это выражение, для которого нет доступной функции. У меня есть следующие типы Exp:

data Exp = IntExp Integer
         | VarExp String
         | LamExp String Exp
         | IfExp Exp Exp Exp
         | OpExp String Exp Exp
         | AppExp Exp Exp
         deriving (Eq)

Я считаю, что подпись типа для моей функции будет следующей:

isSimple :: Exp -> Bool

Вот несколько тестовых случаев:

Main Lib> isSimple (AppExp (VarExp "f") (IntExp 10))
False
*Main Lib> isSimple (OpExp "+" (IntExp 10) (VarExp "v"))
True
*Main Lib> isSimple (OpExp "+" (IntExp 10) (AppExp (VarExp "f") (VarExp "v")))
False

Как видите, первое и третье выражения имеют прикладные выражения для функций и, следовательно, не простые. Но я даже не знаю, как начать функционировать, чтобы решить. Любая помощь будет оценена. Спасибо. Изменить: извините, я должен был добавить свой текущий прогресс. У меня простой подход, который на самом деле казался слишком простым:

isSimple (AppExp e1 e2) = False
isSimple (IntExp e1) = True
isSimple (VarExp s1) = True

isSimple (IfExp e1 e2 e3) = (isSimple e1) && (isSimple e2) && (isSimple e3)
isSimple (OpExp s1 e1 e2) = (isSimple e1) && (isSimple e2)

Но также лямбда-выражения были бы немного сложнее.

Answer 1

TL; DR Лямбда-выражение является простым, если (и только если) его тело простое.

Лямбда-выражение в некотором смысле является просто частным случаем операторного выражения, за исключением того, что семантика операции закодирована в грамматике. Вы можете представить, например, разделение OpExp на несколько c случаев с указанием оператора:

data Exp = IntExp Integer
     | VarExp String
     | LamExp String Exp
     | IfExp Exp Exp Exp
<b>     | AddExp Exp Exp  -- x + y
     | MulExp Exp Exp  -- x * y
     | AndExpr Exp Exp -- x && y
     | ...</b>
     | AppExp Exp Exp

Но у нас нет отдельных правил для каждого оператора; у нас есть только один, который хранит рассматриваемый оператор как данные.

Вы можете развить эту идею дальше, рассматривая лямбда-выражение как просто еще один вид выражения оператора.

data Exp = IntExp Integer
     | VarExp String
     | IfExp Exp Exp Exp
     | OpExp Exp Exp
     | AppExp Exp Exp

где лямбда выражение типа λx . x + 3 становится

OpExp "λ" (VarExp "x") (OpExp "+" (VarExp "x") (IntExp 3))

(точно так же, как оба аргумента для + или * должны быть IntExp s или выражения, которые оцениваются как IntExp s, λ требует первым аргументом должно быть VarExp. Это ограничения semanti c, которые просто не захватываются самой грамматикой.)

В этом случае определение isSimple для OpExp по-прежнему сохраняется : выражение является простым, если связанная переменная (первый аргумент) и тело (второй аргумент) просты.

Таким образом, кажется вполне разумным определить

isSimple (LamExp _ e) = isSimple e