FAQ for Homework 4: Queues

What should I read for help on this homework assignment?

Problem 3

Q1. I don’t know what’s wrong with my code, what should I do?

Draw a picture! Draw what the queue and nodes look like with all their pointers, and trace through your code. Write out what would happen to the queue if it was inputted into the current function. Does it do what you expected? This is a good way to make sure you are updating all the correct pointers and maintaining all the invariants.

Q2. What does it mean to modify the queue “in place”?

Instead of initializing new nodes you should change the queues by modifying the pointers of the already created nodes. Your TAs will be grading you based on your adherence to this constraint.

Q3. How many test cases should I write?

There is no exact number of tests to write. Queues and deques are complicated data structures, and there are many edge cases to consider when modifying them. Write an exhaustive set of tests that considers all interesting edge cases. Adding many similar tests is not as useful as a handful of tests that cover various and interesting inputs.

Q4. Why aren’t `Some x` and `Some y`aliases of each other?

‘Some’ is a constructor for the option type. So each use of the constructor Some creates a new heap location (equivalent to a new Some bubble in our representation of the heap). Therefore Some x will be pointing to a different Some bubble than Some y, meaning they are not reference equal.

Why does `None == None` but `Some n` does not always `== Some n`?

It turns out that OCaml optimizes constructors with no arguments (like None, but also Nil, and Empty, or any other user-defined type with no arguments) so that they aren’t stored in the heap. This means that every instance of None is == to every other instance.

Q6. Can I use the `to_list`/ `from_list` functions in my code for other problems?

This is a very inefficient way to do the problem and you will lose points for doing it in this way. You should be operating on queues and not lists in this assignment.

Q7. How do I define a `dequeue` of length 2 if I can’t reference a `qnode` before it’s defined?

Remember that dequeues have mutable fields that can be updated after they are defined. How do you change the value of a mutable field?

Q8. My function won’t compile and I’m getting weird errors, what should I do?

If a branch of an if/then statement has a sequence of commands you need to put parentheses around them. For example: if <cond> then (cmd1; cmd2; cmd3) else if <cond> then (cmd4; cmd5) else (cmd6; cmd7)

Q9. I’m getting an error that says this expression has type `'a qnode option` but an expression was expected of type `'a qnode`, what should I do?

Remember that ‘a qnode option and ‘a qnode are two different types. So something like n.next.next will not work because n.next is a ‘a qnode option which doesn’t have a next value (only ‘a qnodes do). In particular the type of head, tail, next, and prev are all ‘a qnode options. You can pattern match over an option to access the optionless data type. You can add the Some keyword in front of a datatype to turn it into an option.

Q10. I keep on getting an infinite loop/ out of memory error, what should I do?

Out of memory usually means you’re doing a structural equality check for dequeues or dqnodes somewhere in your code. This means you are using = to compare two values of that type. Since dequeues and dqnodes are cyclic this will result in an infinite loop. Make sure your code doesn’t contain this problem.

Q11. When I submit my code I get an error `*** No rule to make target graph.cmo', needed by ocamlbin'.`, what should I do?

You need to submit the graph.ml file even if you did not do the kudos program. Make sure you included that file. (This should happen automatically if you use the Zip menu option in Codio.)

Q12. I’m running into complilation issues when using semicolons in an if statement, what should I do?

This usually comes from not putting parenthesis around your statements. Semicolons will try to terminate the entire block prematurely, so parenthesizing the statement containing the semicolon should tell OCaml to resolve that first.