1
$\begingroup$

In the world of mutable/ephemeral data structures and imperative programming languages, one of the classic ways to implement a stack or queue is to use array doubling: use mutation to fill up or empty an array, doubling or halving to expand/contract. Such stacks/queues have several nice properties:

  1. They use at most twice as much memory as strictly necessary.
  2. They involve minimal indirection.
  3. They use cache efficiently.
  4. They have amortized $O(1)$ insertion and deletion operations.

In a purely functional system, this approach falls down quite flat, because "mutate the array to fill/empty" becomes very expensive: the array has to be copied each time. I was wondering if there might be some reasonable compromise approach, making something more compact than classical approaches (a la Okasaki) but still with constant amortized time operations. Stacks are simpler, so I started thinking about those. My first attempt (in Haskell notation) was

data Stack a
  = Shallow !(Array a)
  | Deep !(Array a) (Stack a)

with the rule that the array at depth $n$ must have either $0$ or $2^n$ elements. Unfortunately, this doesn't look like it's nearly good enough. It appears that insertions impose an $O(\log n)$ amortized cost, since flipping from a 1 digit to a 0 digit gets more expensive the deeper it happens in the tree. My next attempt was the same, but using skew binary numbers instead of binary numbers (I didn't actually work this one out in full, so it might not even make sense). Same deal. Is there some trick I'm missing, or am I asking to have my cake and eat it too?

Improve this question
$\endgroup$
3
  • $\begingroup$ Amortized + Persistent are a bad combination in general. Since we can always replicate several times the critical action, making each update work with the complexity of the worst action. $\endgroup$
    – Marcelo Fornet
    Jun 22, 2020 at 17:31
  • $\begingroup$ That said, stacks can be represented like trees, and all operations will work in O(1), however you will not be able to get the kth element from the top on the ith stack in O(1) anymore, but you will be able to get the element at the top and pop in O(1). $\endgroup$
    – Marcelo Fornet
    Jun 22, 2020 at 17:33
  • $\begingroup$ @MarceloFornet, amortization can be resolved with persistence using lazy evaluation, which is what I'm trying to use here. Some problems are more susceptible to a generalization of lazy evaluation. Stacks can of course be represented very simply as linked lists, but each element then requires its own node, with the indirection and overhead that entails. $\endgroup$
    – dfeuer
    Jun 22, 2020 at 18:01

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.