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

岡崎氏は著書の中で、O(1)操作を伴うキューの実装 (最悪の場合または償却されたもの) を考えるappendと、uncons償却されると主張していますO(1)。

なぜ彼の主張を強化できないのですか？リアルタイム キューの実装 (すべての操作が最悪の場合O(1))を考えるappendと、私にunconsは最悪の場合に見えO(1)ます。のすべての再帰呼び出しはlinkAllによって保護されており、どのL.delayパブリック操作も 1 つ以上の中断を強制することはありません。私の推論 (または私のコード) は間違っていますか?

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 に答える