3

如何从 Ocaml 的队列中删除重复的值（即重复值）？

例如，假设这是一个队列（尽管它以列表的形式呈现）：

     [1; 1; 2; 3; 4; 7; 7; 8; 8; 8]

然后，将此函数应用于队列后，我们将得到：

     [1; 2; 3; 4; 7; 8]

列表情况下的实现：

     let rec deleteDuplicate l = 
        match l with 
         | []                -> [] 
         | x :: []          -> x :: [] 
         | x :: y :: rest -> 
               if x = y then deleteDuplicate (y :: rest) 
               else x :: deleteDuplicate (y :: rest)
4

1 回答 1

2

我认为首先要做的是决定你将如何代表你的队列。您可以使用标准 OCaml 库中的 Queue 模块。这使用队列的可变表示。或者你可以使用一个非常好的（简单但聪明的）不可变表示，它由两个列表组成，一个用于头部，一个反向用于尾部。在你决定你的代表之后，我怀疑很容易看出该怎么做。你可以毫无困难地做一个列表。

假设您想使用 OCaml 库中的 Queue 模块。由于这是一个可变队列，我假设您想以命令式风格进行编码。即，您想修改现有队列以便删除重复项。

一种非常直接的方法是先转换为列表，然后将您的函数应用于列表，然后将元素放回队列中。

let rec list_of_queue q =
    (* Change queue to list, emptying queue in the process.
     *)
    if Queue.is_empty q then [] else let h = Queue.take q in h :: list_of_queue q

let queue_add_list q l =
    List.iter (fun x -> Queue.add x q) l

let deleteQueueDuplicates q =
    let l = list_of_queue q in
    queue_add_list q (deleteDuplicate l)
于 2013-04-01T01:50:20.223 回答