在 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)

我一直在尝试验证队列列表是否包含元素，return 为真。如果不是return 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

您可以使用列表的思想来实现不可变的 queue。所以你有一个顶级元素和你的 Queue.

的其余部分

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

这是可能的；但插入性能不佳。无论如何，这是实现这种 Queue.

的方法

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 不是 tail-recursive。如果您希望第一个元素保留在顶部，而进一步添加的元素添加到末尾，那么您必须重建整个 Queue。添加基本上是一个 List.append，您可以在其中添加一个元素到 queue 的末尾重建整个 Queue。所以你的插入速度很慢，二次 O(x^2) 性能。

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

您可以使用两个列表作为不可变 queue 而不是这样做。这个想法是：添加元素构建一个列表，你离开它们只要您不获取元素，就以相反的顺序进行。只有当你想获取一个元素，并且没有可用的反向列表时，你才反向列表一次，并保存反向列表。所以加入一个元素是 O(1) 性能。

如果您已经有一个反向列表，则在 other-side 上获取一个元素可以是 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 也更改为 return 剩余的 Queue（尾部）。因为在大多数情况下，如果您使用 head，您可能还会调用 tail。在这种情况下，列表的反转发生了两次。

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

现在，如果你想要额外的功能，你应该先添加一个fold和foldBack功能。例如在 QueueB 上 fold 将是

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  *)

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

Implement a queue type in F# contains elements

queue

f#

types