I had this problem of creating a dequeue operation for
type 'a t = 'a list * 'a list
exception Empty
The queue is represented as a pair of lists (r,f), where f is the beginning of the queue [e1, e2, . . . , ei] and r is the end of the queue [en; en-1; . . . ; ei+1]
And I am asked to define this operation: dequeue returns an option on queue equal to the queue in parameter minus the first element, or None in case of error.
First of all I don't know what is this error.
So, this is what I did:
let dequeue (r, f) =
match (r, f) with
| ([], []) -> None
| (r', _::f') -> Some (r', f')
| (r'', []) -> Some ([], List.tl (List.rev r''))
But the code provided as solution is this:
let dequeue (r,f) =
match (r,f) with
| (r,_::q) -> Some (r,q)
| ([],[]) -> None
| _ -> ([], try List.tl_exn (List.rev r) with _ -> raise Empty)
And it doesn't make sense to me why for the third case there is no option being returned, and why in this third case we have to handle exception. List.tl_exn will never have empty 'r'. For (r, _::q) can handle ([], [1]) and ([1], [2]), ([], []) can handle the empty queue, and (r'', []) can handle ([1], []) for example, and this last example for the third case, we don't have to raise exception, because List.tl_exn [1] will be []. Is this correct? Is the code solution provided buggy or not complete?
As you say, the third result is missing Some. Hence the code is wrong. The compiler diagnoses a type error for this reason.
If you add Some to the third result, the provided solution looks correct but weirdly coded, as you also say. The third case of the match will be taken when the second list (front of queue) is empty but the first list (rear of queue) is nonempty. In this case List.tl_exn will always return the tail of the list and will never raise an exception.
It would be more straightforward to replace List.tl_exn with List.tl and take out the exception handling. The resulting function would have the same behavior.
Update
It appears that this code is written for the Jane Street Core library, which has a function named List.tl_exn. Furthermore the List.tl function returns 'a option for this library (so I'm told). That's why the code is so unnecessarily complicated. I apologize -- I don't have any experience using Core.
At any rate, the provided code doesn't look so strange if you realize that you can't just use List.tl to get the tail of a list. Testing for an exception whenever calling a function that ends with _exn might be required by the in-house style rules--even if the exception is impossible.
Here is the fixed code using the unnecessary Empty exception:
let dequeue (r,f) =
match (r,f) with
| (r,_::q) -> Some (r,q)
| ([],[]) -> None
| _ -> Some ([], try List.tl_exn (List.rev r) with _ -> raise Empty)
Here is fixed code that depends on the exception being impossible:
let dequeue (r,f) =
match (r,f) with
| (r,_::q) -> Some (r,q)
| ([], []) -> None
| _ -> Some ([], List.tl_exn (List.rev r)) (* r <> [] *)
Unfortunately I can't test these functions because (as I say) I don't use Core. But they should be pretty close to correct :-)