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

Question

[Дмитрий Щербаков]

Создал пользовательский тип логического выражения:

-- Тип логического выражения
data Prop =   Var String 
			| Not Prop
			| And Prop Prop
			| Or Prop Prop 
				deriving (Eq, Show)

Вот пример такого выражения:
expr = Or (Var"y") (Or (Var "x") (Not (Var "x")))
Думаю понятно, у меня все максимально упрощенно, без констан, только переменные, и операции, не или и.
Мне необходимо написать функцию для него, чтобы его упростить.
А конкретно учесть двойное отрицание. не (не А) = А
Повторения. А && А = А. А || А = А
И Поглощения. А + А*B = A. A*(A+B) = B
Помогите пожалуйста с такой функцией. На вход выражение и на выходе тоже выражение.
simplifyExpr :: Prop -> Prop

Answer 1

[Александр Скуснов]

можно так:

simplifyExpr (Not (Not p)) = simplifyExpr p -- рекурсивный вызов
-- другие шаблоны

-- конец рекурсии
simplifyExpr p = p

-- проверка
>simplifyExpr (Not (Not (Var "abc")))
Var "abc"

Comments

[Дмитрий Щербаков]

Спасибо, но ведь если Not (Not p) будет спрятан внутри, то этого сокращения не произойдет(
например
And (Var "a") (Not(Not "k"))

[YURIY KOZLOV]

Дмитрий Щербаков, Александр Вам правильно написал. И сокращение произойдет. Если Вы для каждой логической функции определение напишете рекурсивно, и для каждого логического закона определите шаблон.
Заканчиваться рекурсия будет на эквивалентной функции
simplifyExpr p = p