Haskell: How to call a recursive function on a modified argument by said recursive function-CodePudding

I'd like to implement the lazy reduction of a lambda expression. It should only reduce that expression until it is in WHNF.

The type LExpr is defined like this:

data LExpr = Var String
            | App LExpr LExpr
            | Lam String LExpr

What i did so far:

lazy :: LExpr -> LExpr
lazy (Var v) = Var v 
lazy (Lam x e) = Lam x e
lazy (App e1 e2) = 
  case e1 of
    (Lam x e)   -> if (x `elem` bound e1) 
                     then lazy $ subst e2 x e 
                     else App e1 e2
    (App e3 e4) -> App (lazy $ App e3 e4) e2 
    _           -> App e1 e2

(bound is a List of all Strings that are bound in a expression; subst substitutes the string x in expression e with the expression e2 and is also doing alpha conversion if necessary)

But this is only reducing one argument. For example if I call lazy with (\x -> x) (\y -> f y) a b

It will be reduced to: (\y -> f y) a b

But I want to have: f a b

So basically in the second case-statement I want to call:

(App e2 e3) -> lazy $ App (lazy $ App e3 e4) e2

But this is not working. How can i call a function on an argument that is modified by said function? Maybe, i can force Haskell to reduce the inner call of lazy first?

I also tried to use fold:

lazy' :: LExpr -> LExpr
lazy' = lfold (\x -> Var x) 
              (\x y -> lazy $ (App x y)) 
              (\x y -> Lam x y)

It is working fine for the example above. However, not for this example: (\z x. (\x. x) z) x

which will be reduced to: (\x' -> x)

But the correct outcome would be: (\x' -> (\x -> x) x)

I don't know how to fix this. Maybe someone got an idea and would like to share it with me? Thank you very much in advance.

P.S.: All the functions that I used like "lfold" or "subst" etc. are from previous homeworks, so I know the implementation is correct. If you'd like to see the implementation, i can add them.

CodePudding user response：

In this case, the first thing that occurred to me was not to use case at all. I can't give it a try, but maybe this idea will help:

lazy :: LExpr -> LExpr
lazy (Var v) = Var v 
lazy (Lam x e) = Lam x e
lazy (App e1@(Lam x e) e2) = if (x `elem` bound e1) then lazy $ subst e2 x e else App e1 e2
lazy (App e1@(App _ _) e2) = App (lazy e1) e2 
lazy (App e1 e2@(Var _)) = App e1 e2
lazy (App e1 e2) = App e1 (lazy e2)

CodePudding user response：

Thanks everyone. I've found the problem.

If i call (App e3 e4) -> lazy $ App (lazy $ App e3 e4) e2 in the second case-statement, i only want to do that if lazy $ App e3 e4 results in a lambda expression. If it is an application of variables (or variable and an expression) it will be called over and over again. So before i call lazy on the modified expression, i just need to check whether it is of the form Lam x e or not.

Now lazy is working fine.