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

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

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

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不是尾递归的。如果您希望第一个元素保持在顶部并在末尾添加进一步添加的元素，那么您必须重建整个队列。添加基本List.append上是您将元素添加到队列末尾以重建整个队列的位置。因此，您的插入速度很慢，具有二次 O(x^2) 性能。

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

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

如果您已经有一个反向列表，则在另一端获取一个元素可能是 O(1)，否则可能是 O(N)。通常你可以说它是 Amortized 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为也返回剩余的队列（尾部）。因为大多数情况下，tail如果您使用head. 在这种情况下，列表的反转发生了两次。

只返回head一次。如果你不需要尾巴，那么你可以把尾巴扔掉。

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

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

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

问题描述

解决方案

推荐阅读