types - 在 F# 中实现包含元素的队列类型

Question

我在 F# 中实现了一个队列，插入元素效果很好。

// Defines the Queue type as an algebraic data type.
type 'a Queue = QueueList of 'a list * 'a list

let empty = QueueList([], [])

let add elem = function
  | QueueList(top, rest) -> QueueList(top, elem :: rest) 

我一直在尝试验证队列列表是否有该元素，是否返回 true。如果没有返回 false。

// Returns true if the queue contains the given element.
val contains: 'a -> 'a Queue -> bool when 'a : equality

// Returns true if the queue contains the given element.
// let rec contains elem = function
       | QueueList([], []) -> false
       | QueueList(hd::tl, tl2) -> if hd = elem 
                                       then true 
                                         else contains elem (QueueList (tl, tl2))

感谢您的帮助。

Answer 1

您可以使用列表的思想来实现不可变队列。所以你有一个顶部元素和队列的其余部分。

type QueueA<'a> =
    | Empty
    | Top   of 'a * QueueA<'a>

这是可能的；但插入性能较差。无论如何，这就是如何实现这种队列。

module QueueA =
    let empty = Empty

    let rec add x q =
        match q with
        | Empty        -> Top (x,Empty)
        | Top(y,rest ) -> Top (y, add x rest)

    let head q =
        match q with
        | Empty       -> None
        | Top(x,rest) -> Some x

    let tail q =
        match q with
        | Empty       -> None
        | Top(x,rest) -> Some rest

    let rec iter f q =
        match head q with
        | None   -> ()
        | Some x ->
            f x
            Option.iter (iter f) (tail q)

add 不是尾递归。如果您希望第一个元素保留在顶部，并将进一步添加的元素添加到末尾，那么您必须重建整个队列。 Add 基本上是一个 List.append ，您可以在其中将一个元素添加到队列末尾，从而重建整个队列。因此，插入速度较慢，且性能为二次 O(x^2)。

但是 tail 是一个 O(1) 的快速操作。

您可以使用两个列表作为不可变队列，而不是这样做。这个想法是:添加的元素构建一个列表，然后你留下它们 只要不获取元素，就按相反的顺序。仅当您想要获取元素并且没有可用的反转列表时，您才反转列表一次，然后保存反转列表。所以添加 一个元素的性能为 O(1)。

如果已经有反向列表，则获取另一侧的元素可能是 O(1) 时间复杂度，否则可能是 O(N) 时间复杂度。通常你可以说它是摊销 O(1)。

实现看起来像

type QueueB<'a> = Queue of queue:list<'a> * added:list<'a>

module QueueB =
    let empty     = Queue ([], [])
    let queue q a = Queue (q,a)

    let add x (Queue (q,r)) =
        queue q (x::r)

    let head q =
        match q with
        | Queue([],[]) -> None
        | Queue([],r)  -> Some (List.head (List.rev r))
        | Queue(q,_)   -> Some (List.head q)

    let tail q =
        match q with
        | Queue([],[]) -> None
        | Queue([],r)  ->
            let q = (List.tail (List.rev r))
            Some (queue q [])
        | Queue(h::t,r) ->
            Some (queue t r)

    let rec iter f q =
        match head q with
        | None   -> ()
        | Some x ->
            f x
            Option.iter (iter f) (tail q)

例如，当您将 1,2,3 添加到 QueueA 时，它将构建结构

Top(1, Top(2, Top(3, Empty)))

当您将 1,2,3 添加到 QueueB 时，它将构建结构

Queue([], [3;2;1])

当你对此调用 tail 时，你会得到

Queue([2;3], [])

相加 4,5,6 的结果

Queue([2;3], [6;5;4])

示例

(* Top(1, Top(2, Top(3, Empty))) *)
let qs =
    QueueA.empty
    |> QueueA.add 1
    |> QueueA.add 2
    |> QueueA.add 3

(* Queue([], [3;2;1]) *)
let qs =
    QueueB.empty
    |> QueueB.add 1
    |> QueueB.add 2
    |> QueueB.add 3

(* Queue([2;3], [6;5;4]) *)
let qs2 =
    QueueB.tail qs
    |> Option.defaultValue QueueB.empty
    |> QueueB.add 4
    |> QueueB.add 5
    |> QueueB.add 6

(* Prints numbers from 2 to 6 *)
QueueB.iter (printfn "%d") qs2

也许在真正的实现中，我会更改 head 以返回剩余的队列(尾部)。因为大多数时候，如果您使用 head，您可能还会调用 tail。在这种情况下，列表的反转发生了两次。

使用 head 返回两者只会执行一次。如果你不需要尾部，那么你可以把尾部扔掉。

---

现在，如果您想要其他功能，您应该首先添加 fold 和 foldBack 函数。例如，在 QueueB 上，折叠 将是

let rec fold f (state:'State) q =
    let rec loop state q =
        match head q with
        | None      -> state
        | Some head ->
            match tail q with
            | None      -> state
            | Some rest -> loop (f state head) (rest)
    loop state q

然后你可以用它实现contains。

let contains x q =
    let folder state e =
        if e = x then true else state
    fold folder false q

还有上面的qs2

QueueB.contains 1 qs2 (* false *)
QueueB.contains 6 qs2 (* true  *)