Is that really the right result, though? Do we really have that a variable can make one reduction step resulting in itself? Here the result (Var x) is an Expr, not a Maybe Expr, so it has the wrong type.
Lambda calculus interpreter haskell code#
The rest of the code has some issues: appNF_OneStep::Expr -> Maybe Expr Still, I'd recommend you start by examining all four cases, to understand what's going on. You might not need to consider all four cases if you discover some of them are similar and can be grouped. Can we reduce their application? How?Īnd so on. In case 2, e1 can not be reduced, but e2 can (to a').
In case 1, both e1 and e2 can not be reduced.
There are four possible cases: appNF_OneStep (App e1 e2) = This part of your code looks OK: appNF_OneStep (App e1 e2) = You need to perform the recursive calls, and check whether their result is Nothing or Just something. New expression expr', appNF_OneStep returns Just expr', otherwise it returns Nothing.Īs example inputs/outputs: Input: App (Lambda "x" (Lambda "y" (Var "x"))) (Lambda "x" (Var "x")) Correct Output: Just (Lambda "1_" (Lambda "x" (Var "x")))Īnother example: Input: Lambda "y" (Lambda "x" (Var "x")) Correct Output: NothingĪs can be seen, the entire expression with only the one reduction performed is wrapped inside of the Just. Pick the leftmost redex R if there are nested (inner) redexes within R, pick the leftmost one,Īnd so on, until we reach a redex without nested ones.) If a reduction was carried out, resulting in a (Note that in applicative order we are pursuing the leftmost, innermost strategyĪs follows. If there is a redex available in e, it picks the correct applicative Where the built-in Maybe type is defined as follows:ĪppNF_OneStep takes an expression e. Now write a function to do a single step of reduction:
Lambda calculus interpreter haskell how to#
I have written all of the other functions but this one is really giving me trouble because it needs to return either Just Expr or Nothing and I'm not sure how to propogate this through the recursion:Ī single step. I am implementing a lambda calculus interpreter and one of the functions I have to write is specified as follows.
0 kommentar(er)
