Почему append и uncons для catenable списков просто амортизируются O (1)?

Question

Я взял реализацию Касабельных списков Окасаки и немного отредактировал его, чтобы избежать проблем с булевой слепотой. Кроме того, структура данных сам по себе остается неизменной:

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, и ни одна из публичных операций не заставляет больше одной подвески. Является ли мой аргумент (или мой код) неправильным?

Answer 1

Что касается Вашего вопроса о catenable списках. Вы также должны учитывать, что принудительное приостановление может привести к каскаду сил. Обратите внимание, что linkAll заставляет свой входной список, который может быть еще неоцененной подвеской 's'. Форсирование 'может в свою очередь заставлять другую приостановку и так далее. Это действительно произойдет, если вы выполните последовательность uncons операций в списке. В конце концов, самое большее после операций «n» uncons структура данных может выродиться до наивного Список минусов (Cons (x, Cons (y, ...))), где 'n' - размер списка. Любые дополнительные операции uncons будут иметь постоянное время. Следовательно, структура данных имеет амортизированную постоянную временную привязку, но это не худший случай.

Answer 2

Необязательные (чисто функциональные) очереди имеют только амортизируемые конструкторы и деструкторы O (1).

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