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