Simulate an evaluator

Question

I'm simulating an evaluator with Haskell. It should be simple but I couldn't debug.

Here I define State as a look-up function (String -> Int), an initial state (empty, exception variable evaluates 0), and extend to add new key (and it's value) to a base environment:

type State = String -> Int

extend :: State -> String -> Int -> State
extend base key val = \x -> if key == x
                                 then val
                                 else base key

empty :: State
empty = \x -> 0

when I test the program:

aState = extend empty  "A" 5
bState = extend aState "B" 4
cState = extend bState "C" 3

I suppose that cState should be equivalent to a function:

\x -> if x == "C"
          then 3
          else if x == "B"
                   then 4
                   else if x == "A"
                            then 5
                            else 0

But instead, I get cState "B" == 0 and cState "A" == 0.

I can't see what is wrong with extend, could somebody explain to me?

Answer 1

In your else statement, you search key (rather than x) in every recursion: else base key. Fix it with:

extend :: State -> String -> Int -> State
extend base key val = \x -> if key == x
                                 then val
                                 else base x

---

BTW, you might write:

empty :: State
empty = \_ -> 0

since empty return 0 regardless of input.