Невозможно получить полную полную бета-версию в Haskell - PullRequest
Новая
       76

Невозможно получить полную полную бета-версию в Haskell

0 голосов
/ 18 апреля 2019

В настоящее время я пытаюсь внедрить бета-версию в Haskell, и у меня небольшая проблема. Мне удалось выяснить большинство из них, однако сейчас, когда я тестирую, у меня возникает одна маленькая ошибка, и я не могу понять, как ее исправить.

В коде используется пользовательский тип данных, термин и функция подстановки, которые я определил ранее, оба они будут ниже. 

--Term datatype
data Term = Variable Var | Lambda Var Term | Apply Term Term

--Substitution function
substitute :: Var -> Term -> Term -> Term
substitute x n (Variable m)
    |(m == x) = n
    |otherwise = (Variable m)
substitute x n (Lambda m y)
    |(m == x) = (Lambda m y)
    |otherwise = (Lambda z (substitute x n (rename m z y)))
    where z = fresh (merge(merge(used y) (used n)) ([x]))
substitute x n (Apply m y) = Apply (substitute x n m) (substitute x n y)

--Beta reduction
beta :: Term -> [Term]
beta (Variable x) = []
beta (Lambda x y) =  map (Lambda x) (beta y)
beta (Apply (Lambda x m) n) = [(substitute x n m)] ++ [(Apply (Lambda x n) m) | m <- beta m] ++ [(Apply (Lambda x z) m) | z <- beta n]
beta (Apply x y) = [Apply x' y | x' <- beta x] ++ (map (Apply x) (beta y))

Ожидаемый результат выглядит следующим образом: 

*Main> Apply example (numeral 1)
(\a. \x. (\y. a) x b) (\f. \x. \f. x)
*Main> beta it
[\c. (\b. \f. \x. \f. x) c b,(\a. \x. a b) (\f. \x. f x)]

Однако это мой результат: 

*Main> Apply example (numeral 1)
(\a. \x. (\y. a) x b) (\f. \x. \f. x)
*Main> beta it
[\c. (\b. \f. \x. \f. x) c b,(\a. \f. \x. \f. x) (\x. a b)]

Любая помощь будет высоко ценится.

...