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).
Fun fact: this is also the implementation that Erlang uses for the queues in the standard library.
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).