4

我采用了 Okasaki 的可连接列表实现，并对其进行了一些重构以避免布尔盲问题。除此之外，数据结构本身保持不变：

functor CatList (Q : QUEUE) :> CAT_LIST =
struct
  (* private stuff, not exposed by CAT_LIST *)

  structure L = Lazy
  structure O = Option  (* from basis library *)

  datatype 'a cons = ::: of 'a * 'a cons L.lazy Q.queue

  infixr 5 :::

  (* Q.snoc : 'a Q.queue * 'a -> 'a Q.queue *)
  fun link (x ::: xs, ys) = x ::: Q.snoc (xs, ys)

  (* L.delay : ('a -> 'b) -> ('a -> 'b L.lazy)
   * L.force : 'a L.lazy -> 'a
   * Q.uncons : 'a Q.queue -> ('a * 'a Q.queue lazy) option *)
  fun linkAll (xs, ys) =
    let
      val xs = L.force xs
      val ys = L.force ys
    in
      case Q.uncons ys of
          NONE => xs
        | SOME ys => link (xs, L.delay linkAll ys)
    end

  (* public stuff, exposed by CAT_LIST *)

  type 'a list = 'a cons option

  val empty = NONE

  (* L.pure : 'a -> 'a L.lazy *)
  fun append (xs, NONE) = xs
    | append (NONE, xs) = xs
    | append (SOME xs, SOME ys) = SOME (link (xs, L.pure ys))

  (* Q.empty : 'a Q.queue *)
  fun cons (x, xs) = append (SOME (x ::: Q.empty), xs)
  fun snoc (xs, x) = append (xs, SOME (x ::: Q.empty))

  (* O.map : ('a -> 'b) -> ('a option -> 'b option) *)
  fun uncons NONE = NONE
    | uncons (SOME (x ::: xs)) = SOME (x, L.delay (O.map linkAll) (Q.uncons xs))
end

在他的书中，Okasaki 声称，给定具有O(1)操作的队列的实现（最坏情况或摊销），append并且uncons是摊销的O(1)。

为什么他的主张不能得到加强？给定实时队列的实现（所有操作都是最坏情况O(1)），append在我uncons看来是最坏情况O(1)。所有递归调用linkAll都由 保护L.delay，并且没有任何公共操作会强制暂停一次以上。我的推理（或我的代码）错了吗？

4

2 回答 2

1

不可变（纯函数式）队列只有分摊的 O(1) 构造函数和析构函数。

http://www.westpoint.edu/eecs/SiteAssets/SitePages/Faculty%20Publication%20Documents/Okasaki/jfp95queue.pdf

于 2015-02-01T23:44:22.507 回答
1

Regarding your question on catenable lists. You need to also take into account that forcing a suspension may result in a cascade of forces. Note that linkAll forces its input list, which could be a yet unevaluated suspension 's'. Forcing 's' may in turn force another suspension and so on. This would indeed happen if you do a sequence of uncons operations on the list. Eventually, at most after 'n' uncons operations, the data structure may degenerate to the naive Cons list (Cons(x, Cons(y, ...))), where 'n' is the size of the list. Any further uncons operations will have constant time. Therefore the data structure does have an amortized constant time bound, but it is not worst case.

于 2015-12-20T20:05:42.633 回答