2

I'm currently studying for a final exam on ocaml and am having trouble with a problem and was wondering if anyone would take the time to help. I am working on a practice final that our professor posted here, specifically number 2. The problem is:

In this problem, we will represent Python-style namespaces using Ocaml data structures. Consider the following datatype declaration:

 type name_space = EmptyNameSpace
               | Info of (string * value) list * name_space
 and  value      = Int of int
               | Method of (name_space -> int -> int)

A name space is either the empty name space, or it contains some information. The information it contains is a list of string-to-value bindings, along with a pointer to the parent name space. A value is either an int, or it is a method. A method takes a name space as the first parameter (the self pointer), and an additional integer, and returns an integer. Suppose we had the following Python code:

class SimpleObj1: a=0
      def f(self, i): return i+1
class SimpleObj2 (SimpleObj1):
  def g(self, i): return i+2
SimpleObj2()

The object created by the call to SimpleObj2() would be represented in our OCaml data structures as follows:

let method_f self i = i+1
let SimpleObj1 = Info([("a", Int(0)); ("f", Method(method_f))], EmptyNameSpace)
let method_g self i = i+2
let SimpleObj2 = Info([("g", Method(method_g))], SimpleObj1)

write an ocaml function that will look up the value in the name space and return it. For example lookup SimpleObj2 "a" will return Int(0).

So that is the problem. I've tried a few things already but I get either plagued by syntax errors that don't make a whole lot of sense to me or I am just not doing something right. I'm feel like my logic is sound and I'm almost there but I could be far off, I'm not very good at ocaml. Try 1: I tried using fold

  let rec lookup ns str = 
    let foldfn acc (str', val) = 
      if str' = str then val else acc
    in
  let base = [] in 
  match ns with 
  | EmptyNameSpace -> raise NotFound
  | Info (l, parent) ->
    match List.fold_left foldfn base l with 
    | value val -> val
    | [] -> lookup parent str

For some reason this gives me a syntax error that the ( in let foldfn acc (str', val) is unmatched. I do not know what is giving me this as it is clearly matched. Would something else cause ocaml to throw this error?

Try 2: without fold and just recursion. I though maybe I'm bad at folding.

let rec lookup ns str = 
  let rec list_help l = 
    match l with 
    | [] -> []
    | (str',va)::t -> if str' = str then va else list_help t
  in 
  match ns with 
  | EmptyNameSpace -> []
  | Info (l, parent) -> 
    (match list_help l with 
    | [] -> lookup parent str
    | value v -> v)

This gives me a syntax error by underlining v. I don't understand why it would do this, I have a datatype value and I would think matching it like that would work fine. Is there some sort of nuance that I am not understanding in ocaml data type.

try 3: I tried to fix the weird syntax error above by coding around it(bad practice but I'm jsut trying to get it to work). In an effort to save space I'll only post the changes to the last match, everything else is the same.

  match ns with 
  | EmptyNameSpace -> []
  | Info (l, parent) ->
    let ans = list_help l in 
    if ans = [] then lookup ns str
    else ans

This is actually the closest I've been but gives the error error: This expression has type (string * value) list but an expression was expected of type (string * 'a list) list I can see why that is. iIt's because I'm returning an empty list in the base case of the list_help function. This actually will be a problem in the first two approaches above even if I fix the syntax errors. This leads me to a more concrete question then "hey why isn't this working". It's how would I return nothing? () doesn't work. I don't know enough about ocaml to understand how to do that. I appreciate anyone who will take the time to help me understand this. Also if you want to take a stab at the fold function for question 1c on the same test, I would also greatly appreciate it, but this one is bugging me the most, I could figure out that one given enough time.

Edit: just in case you need exception NotFound defined otherwise an entirely different error will throw. Also didn't there used to be a homework tag? This isn't homework but is pretty close to it.

Edit2: Figured it out. I was doing to much work.

let rec lookup ns str =
    match ns with
        | EmptyNameSpace -> raise NotFound
        | Info ([], parent) -> lookup parent str
        | Info ((k,v)::t, parent) -> if k = str then v else lookup (Info (t,parent)) str
Improve this question

1 Answer 1

Reset to default
4

The error in your first example is due to the fact that val is a keyword. But yes, there is a remaining error because

| value v -> ...
| [] -> ...

is not correct and I'm not sure what you mean. There is an underlying type error that you should fix.

You should consider using the List.assoc function that returns the value associated to a key in an associative list (list of pairs), or the exception Not_found.

PS: for the record, here is the code I had in mind (untested)

let rec lookup ns key = match ns with
  | EmptyNameSpace -> raise Not_found
  | Info (scope, parent) ->
      try List.assoc key scope
      with Not_found -> lookup parent key
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

The problem with raising not found is I want it to go to the parent namespace if it's not found. I can do a try catch block I suppose though. So I switched it to va instead of val but it still gives me syntax errors for value va in the last match(I'm using the fold one now). Would that be because it's not recognizing the value datatype or can I not use value and need to use Int or Method? INt seems to work but now what do I do with the base case? We can't use built in functions for the test so List.assoc wouldn't work...
Yes, use a try .. with block around List.assoc, or call List.mem_assoc : 'a -> ('a * 'b) list -> bool first to check whether the key really exists. I'm sorry I don't take the appropriate time to guide you through your misconception and type error; you did a good job explaining your problem, but your code still doesn't make sense and I cannot take the time to go into the details. You should look at your courses about pattern matching, because the syntax of patterns is not what you use in your faulty examples.
I've edited the question with the answer I've found. It works fine and ditches all of the folding and multiple matching and just manually folds over it. Thank you for trying to help.
You should probably still try to clear your misconceptions about pattern-matching and what went wrong with your code examples above.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.