Eliminating Amortization
Prev: Amortization and Persistence via Lazy Evaluation Next: Lazy Rebuilding
Prev: Amortization and Persistence via Lazy Evaluation Next: Lazy Rebuilding
7.2 Real-Time Queues
Exercises
Exercise 7.1
Show that replacing f ++ reverse r with rotate (f, r, $NIL) in the banker’s queues of Section 6.3.2 reduces the worst-case running times of snoc, head, and tail from to .
Hint: prove that the longest chain of dependencies between suspensions is . If it makes your analysis simpler, you may delay the pattern matching in rotate by writing fun lazy instead of fun.
Exercise 7.2
Compute the size of a queue from the sizes of s and r. How much faster might such a function run than one that measures the sizes of f and r?
7.3 Binomial Heaps
Exercises
Exercise 7.3
Show that it does no harm to the running time of insert to remove the lazy annotation from the definition of insTree.
Exercise 7.4
Write an efficient, specialized version of mrg, called mrgWithList, so that deleteMin can call:
mrgWithList (rev c, ds')instead of:
mrg (listToStream (map ONE (rev c)), ds')