Cool, Thanks :D also quickcheck says the two algorithms are equivalent :)
On Fri, Jan 29, 2010 at 4:33 AM, Nick Smallbone <[email protected]>wrote: > Job Vranish <[email protected]> writes: > > > Ideally we'd like the type of convert to be something like: > > convert :: LambdaExpr -> SKIExpr > > but this breaks in several places, such as the nested converts in the RHS > of the rule: > > convert (Lambda x (Lambda y e)) | occursFree x e = convert (Lambda x > (convert (Lambda y e))) > > > > A while ago I tried modifying the algorithm to be pure top-down so that > it wouldn't have this problem, but I > > didn't have much luck. > > > > Anybody know of a way to fix this? > > The way to do it is, when you see an expression Lambda x e, first > convert e to a combinatory expression (which will have x as a free > variable, and will obviously have no lambdas). Then you don't need > nested converts at all. > > Not-really-tested code follows. > > Nick > > data Lambda = Var String > | Apply Lambda Lambda > | Lambda String Lambda deriving Show > > data Combinatory = VarC String > | ApplyC Combinatory Combinatory > | S > | K > | I deriving Show > > compile :: Lambda -> Combinatory > compile (Var x) = VarC x > compile (Apply t u) = ApplyC (compile t) (compile u) > compile (Lambda x t) = lambda x (compile t) > > lambda :: String -> Combinatory -> Combinatory > lambda x t | x `notElem` vars t = ApplyC K t > lambda x (VarC y) | x == y = I > lambda x (ApplyC t u) = ApplyC (ApplyC S (lambda x t)) (lambda x u) > > vars :: Combinatory -> [String] > vars (VarC x) = [x] > vars (ApplyC t u) = vars t ++ vars u > vars _ = [] > > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
