Как получить список переменных, которые появляются в логическом выражении?

Question

Здравствуйте. Мне нужна помощь в создании функции, которая возвращает переменные логического выражения. Я пытаюсь получить образец, но не могу найти общий подход, который работает со всеми тестовыми примерами.

Вот код

module BoolExpr (Variable, BoolExpr(..), evaluate) where
import Data.List
import System.IO

type Variable = Char
data BoolExpr = T
 |F
 |Var Variable
 |Not BoolExpr
 |And BoolExpr BoolExpr
 |Or BoolExpr BoolExpr
 deriving(Show)


--this is my attempt 
variables :: BoolExpr -> [Variable]
variables T = []
variables F = []
variables (Var e1)= [e1]
variables (And (Var e1) (Var e2))=variables (Var e1) ++variables (Var e2)
variables (Or (Var e1) (Var e2))=variables (Var e1) ++variables (Var e2)
variables ( And (Var e1) (Or (Var e2)(Var e3)) ) = variables (Var e1) ++ variables (Var e2) ++ variables (Var e3) 
variables (xy)=variables x ++ variables y
variables _ = []

Некоторые тестовые случаи и их желаемый вывод

> variables T
""

> variables (Or T F)
""

> variables (Var 'a')
"a"

> variables (And (Var 'a') (Or (Var 'c') (Var 'b')))
"abc"

> variables (And (Var 'a') (Or (Var 'a') (Var 'a')))
"a"

Но если используется более трех переменных или около того, функция завершится ошибкой. Я не могу сделать это в общем виде

Answer 1

Ваш шаблон соответствует слишком специфично. Например, вы пишете предложение:

variables (And (Var e1) (Var e2)) = …

и, таким образом, ограничиваетесь And, где операндами являются значения, заключенные в конструктор данных Var. Но это не обязательно. Мы можем просто написать это как:

variables (And <b>e1</b> <b>e2</b>) = &hellip;

, тогда e1 и e2 - это BoolExpr s, которые могут быть построены со всеми возможными конструкторами данных. Таким образом, мы можем определить функцию следующим образом:

variables :: BoolExpr -> [Variable]
variables T = []
variables F = []
variables (Var e1) = [e1]
variables (And e1 e2) = variables e1 ++ variables e2
variables (Or e1 e2) = variables e1 ++ variables e2
variables (Not e) = variables e

Обратите внимание, что переменная будет встречаться несколько раз раз, если она является частью выражения несколько раз. Таким образом, вы можете захотеть передать результат через фильтр уникальности , если вам нужен список уникальных переменных. Кроме того, вы также можете отсортировать результат.

Мы можем сделать это, определив функцию, которая работает поверх переменных, например:

uniqVariables :: BoolExpr -> [Variable]
uniqVariables e = _ (variables e)

, где _ - это нечтоВы должны заполнить. Я оставляю это как упражнение.