Creating a Function Representation for Environments in SML

Question

Okay, So I am working on creating a function representation for environments in SML:

type name = string
type 'a fenv = name -> 'a

I'm a little stuck on how to proceed with this. The first thing I need to do is define a value fenvEmpty of type 'a fenv, which represents the empty environment (the environment that does not bind any names). So far, I have this:

val fenvEmpty = 
    let
        fun empty (name) = ???
    in
        empty
    end

I'm not sure if I'm on the right track or anything. What am I supposed to return from the function empty? Putting in 0, null, or NONE won't work.

Later, I also have to write functions that returns data associated with a particular name in the environment (a find function), and a function that binds data to a particular name in the environment ( a bind function), but I'm already stuck on the fenvEmpty part.

Answer 1

I presume the teacher wants you to raise an exception when attempting to look up an unbound value:

type name = string
type 'a fenv = name -> 'a

exception UnboundName of name

fun fenvEmpty name = raise UnboundName name

But I think it will help you more if you first try to use a version of fenv that returns NONE for unbound variables. I believe this because, as opposed to exceptions, there's more type structure to the program that will guide you while writing the implementation (see also below). So, first try to write this implementation where fenv is:

type 'a fenv = name -> 'a option

Now, for the later part of the question, you'll have to define a function for associating a name with a value to an existing environment. This would be that function's type:

val fenvAssoc : 'a fenv -> name -> 'a -> 'a fenv

Notice that the above returns a result of type 'a fenv. But remember what fenv actually is. It's "just" a function:

type 'a fenv = name -> 'a

So, this returned value, a function, needs to somehow "remember" the name and value that have been associated with it. How do functions normally "remember" things they've "seen" in the context where they've been defined?

To look up a name's value, you need a third function, which takes an existing environment and a name and returns the value for that name, if any:

val fenvLookup : 'a fenv -> name -> 'a

Again, remember what the type of 'a fenv is:

type 'a fenv = name -> 'a

I'm emphasizing this because the type of 'a fenv restricts you in the operations you can apply to it. You can basically either: a) create a function or b) apply one.