1. 16
  1. 3

    Fun fact: this is also the implementation that Erlang uses for the queues in the standard library.

    1. 2

      My understanding was that this is still not the ideal data structure as far as Okasaki is concerned. In particular, code may still retain reference to a queue before something was popped from it (sharing purely functional data structures is perfectly fine!); this code would once again pay the O(n) penalty if it decided to pop.

      The secret ingredient is laziness; there are some clever tricks that can be done to make sure that the “reverse” operation amounts to forcing some kind of thunk; this thunk, once forced, remains computed, and thus (I believe), the pre-pop version of the data structure can be popped from a second time in O(1).