How to evaluate a function with curried argument in haskell?

Question

I'm writing an expression evaluator defined as such:

eval :: LState -> Env -> Lexp -> (LState, Value)

Where LState is the memory. Env: a map of Variable & Value.Lexp are defined as such:

data Lexp = Lid Var | Lfuncall Lexp [Lexp]

(there is more to Lexp, but the rest is not useful to solving my problem.

Value is defined as such:

data Value = Vnum Int
           | Vbool Bool
           | Vref Int
           | Vfun ((LState, Value) -> (LState, Value))

Using pattern matching, I've written the first part of my function: eval s env (Lfuncall func (arg:args)) =

Now, I tried using foldl and lambda functions, but nothing works.

eval s env (Lfuncall func (arg:args)) =   let arg' = eval s env arg
        args' = map (eval s env) args
    in
        case eval s env func of
            (_, Vfun func') -> foldl func' arg' args'
            _ -> error "error"

This doesn't work however, because func' needs to be (LState, Value) -> (LState, Value) -> (LState, Value) but it's only (LState, Value) -> (LState, Value). Lambdas took me nowhere in solving this.

Any hints or idea on what I should try to explore?

Answer 1

You're on the right track with a left fold. Let's think carefully about what function we will be folding. It takes a Value which ought (but is not guaranteed) to be a function, and a Lexp argument which will be evaluated, and should give back a Value (which will play the role of the next function, if there are more arguments). So, at first blush, is type is just:

folder :: Value -> Lexp -> Value
--        ^ accumulator (function)
--                 ^ argument
--                         ^ result (used as next accumulator)

And if we apply foldl to this:

foldl folder :: Value -> [Lexp] -> Value

Which takes the initial function and the list of arguments.

But this doesn't handle the state part. We need the current state as part of our accumulator, not just the current function, and the final state needs to be returned. The arguments don't come with their own state. So that brings our type to:

folder :: (LState, Value) -> Lexp -> (LState, Value)

And the resulting fold will be:

foldl folder :: (LState, Value) -> [Lexp] -> (LState, Value)

Taking an initial state, initial function, a list of arguments, and giving us a final state and final result. This adds up. So now all we need to do is write folder with that signature, which I will leave as an exercise.

Some things to keep in mind. Never throw away a state or use it twice -- this is called linearity and it's very important for the idea of a "stateful computation". State computations usually have this pattern

 let (s1, x) = something s0
     (s2, y) = something s1
     (s3, z) = something s2
 in  (s3, something)

So we take the result state from the previous step and pass it to the next one, returning the final one.

In order to call eval, folder will have to have access to env. You can do this by defining folder in a where clause:

eval s env (Lfuncall func args) = ...
    where
    folder :: (LState, Value) -> Lexp -> (LState, Value)
    folder (s0, Vfun f) argExp = -- use env freely here

I hope this helps. I was intentionally a bit vague about some of the details because you really just kind of have to bang your head against it to get the patterns, let me know if there's anything you need further clarification on.