Ocaml 队列删除前面，返回选项但不是每场比赛

Question

我遇到了为

创建出列操作的问题

type 'a t = 'a list * 'a list
exception Empty

队列表示为一对列表 (r,f)，其中 f 是队列的开头 [e1, e2, . . . , ei] r 是队列的末尾 [en; zh-1; . . . ; ei+1]

我被要求定义这个操作：

dequeue

返回队列上的一个选项等于参数中的队列减去第一个元素，或者在错误的情况下为无。

首先我不知道这是什么error.

所以，这就是我所做的：

let dequeue (r, f) = 
  match (r, f) with
  | ([], []) -> None
  | (r', _::f') -> Some (r', f')
  | (r'', []) -> Some ([], List.tl (List.rev r''))

但是作为解决方案提供的代码是这样的：

let dequeue (r,f) = 
  match (r,f) with
  | (r,_::q) -> Some (r,q)
  | ([],[]) -> None
  | _ -> ([], try List.tl_exn (List.rev r) with _ -> raise Empty)

我不明白为什么第三种情况没有

option

被返回，为什么在第三种情况下我们必须处理异常。

List.tl_exn

永远不会有空的'r'。对于(r, _::q)可以处理([], [1])和([1], [2]), ([], [])可以处理空队列, (r'', [ ]) 可以处理 ([1], []) 例如，第三种情况的最后一个例子，我们不必引发异常，因为

List.tl_exn [1]

将是 []。它是否正确？提供的代码解决方案是否有问题或不完整？

Answer 1

如你所说，第三个结果缺失

Some

。因此代码是错误的。编译器因此诊断出类型错误。

如果您将

Some

添加到第三个结果，所提供的解决方案看起来正确但编码很奇怪，正如您所说。

match

的第三种情况将在第二个列表（队列前面）为空但第一个列表（队列后面）非空时进行。在这种情况下

List.tl_exn

将始终返回列表的尾部并且永远不会引发异常。

将

List.tl_exn

替换为

List.tl

并去掉异常处理会更直接。结果函数将具有相同的行为。

（代码特别奇怪，因为标准库中没有函数

List.tl_exn

。可能代码是为其他库编写的。在那种情况下，

List.tl

也不是正确的函数。）