Как реализовать свойство распределения в Haskell рекурсивных типах данных? - PullRequest
Новая
       4

Как реализовать свойство распределения в Haskell рекурсивных типах данных?

2 голосов
/ 06 февраля 2020

У меня есть задача исправить функцию expand. 

infixl 6 :+:
infixl 7 :*:
data Expr = Val Int | Expr :+: Expr | Expr :*: Expr
    deriving (Show, Eq)

expand :: Expr -> Expr
expand ((e1 :+: e2) :*: e) = expand e1 :*: expand e :+: expand e2 :*: expand e
expand (e :*: (e1 :+: e2)) = expand e :*: expand e1 :+: expand e :*: expand e2
expand (e1 :+: e2) = expand e1 :+: expand e2
expand (e1 :*: e2) = expand e1 :*: expand e2
expand e = e

-- expression example: (Val 1 :+: Val 2 :+: Val 3) :*: (Val 4 :+: Val 5)
-- which is equivalent to (1 + 2 + 3) * (4 + 5)

-- expression, that given fucntion evaluates our example to: 
--(Val 1 :+: Val 2) :*: (Val 4 :+: Val 5) :+: Val 3 :*: (Val 4 :+: Val 5)

-- expression that corrected function must evaluate our example to:
-- Val 1 :*: Val 4 :+: (Val 1 :*: Val 5 :+: (Val 2 :*: Val 4 :+: (Val 2 :*: Val 5 :+: (Val 3 :*: Val 4 :+: Val 3 :*: Val 5))))

-- answers like (Val 1 :*: Val 2) :+: (Val 3 :*: Val 4) 
-- and          (Val 4 :*: Val 3) :+: (Val 1 :*: Val 2)
-- are considered to be equal

Не работает, потому что скобки открываются только один раз. Итак, я изменил это следующим образом: 

infixl 6 :+:
infixl 7 :*:
data Expr = Val Int | Expr :+: Expr | Expr :*: Expr
    deriving (Show, Eq)

expand :: Expr -> Expr
expand ((e1 :+: e2) :*: e) = (expand $ e :*: e1) :+: (expand $ e :*: e2)
expand (e :*: (e1 :+: e2)) = (expand $ e :*: e1) :+: (expand $ e :*: e2)
expand (e1 :+: e2) = expand e1 :+: expand e2
expand expr@(e1 :*: e2) = if isMul expr
                          then expr
                          else expand $ expand e1 :*: expand e2
expand e = e

isMul :: Expr -> Bool
isMul (Val a :*: expr) = isMul expr 
isMul (expr :*: Val a) = isMul expr
isMul (Val a) = True
isMul  _      = False

Функция isMul добавлена, чтобы найти условие ребра: если наше выражение (e1 :*: e2) имеет форму Val 1 :*: Val 2 :*: Val 3 ..., то наша функция expand останавливается расширяет и вычисляет выражение для себя, в противном случае рекурсия продолжается.

На моих примерах он отлично работает ~ i sh 

exp0 = (Val 1 :+: Val 2 :+: Val 3) :*: (Val 4 :+: Val 5)
exp1 = (Val 1) :*: ((Val 2) :+: (Val 3)) :*: (Val 4)
exp2 =  Val 1 :*: (Val 2 :*: (Val 3 :+: Val 4)) 
exp3 = ((Val 1) :+: (Val 2)) :*: ((Val 3) :+: (Val 4))
exp4 =  Val 2 :*: (Val 3 :+: Val 4)
exp5 = (Val 3 :+: Val 4) :*: Val 2
exp6 =  Val 3 :+: Val 4  :*: Val 2
exp7 =  Val 3 :*: (Val 4 :*: Val 2)
exp8 = (Val 3 :*: Val 4) :*: Val 2
exp9 =  (Val 1 :+: Val 2 :+: Val 3) :*: (Val 4 :+: Val 5) :*: (Val 6) :*: ((Val 7) :+: (Val 8)) :*: (Val 9)

, но не проходит некоторый тест из-за превышения лимита времени. Я думаю, рекурсия не останавливается где-то, где она должна, но я не вижу, где.

1 Ответ

0 голосов
/ 07 февраля 2020

Ошибка была в функции isMul: результат выражения isMul ((Val 3 :*: (Val 4 :*: Val 2)) :*: ((Val 3 :*: Val 4) :*: Val 2)) был False. Это произошло потому, что data Expr по сути является деревом, поэтому выражения Val 1 :*: (Val 2 :*: (Val 3 :*: Val 4)) и (Val 1 :*: Val 2) :*: (Val 3 :*: Val 4) на самом деле разные. Итак, я написал более общую реализацию для isMul: 

isMul :: Expr -> Bool
isMul (e1 :*: e2) = isMul e1 && isMul e2
isMul (Val a) = True
isMul  _      = False

, которая заставила программу работать как задумано.

...