[Haskell] Queues / Lists with unbound tails

[Claus Reinke]

> Just to clarify, I want something with a *single* operation that takes one
> value, adding it to the front of the queue, and returns a tuple containing
> the value that was at the end of the queue and a new queue, with the new
> value at the front, and without the returned value at the end.  

ok, then you have to peekQ in the middle of pushQ, so to speak:-)

shiftQ front q = let q' = q . (front:)
                 in (head $ q' [],tail . q')

Prelude> :l Queue
Compiling Main             ( Queue.hs, interpreted )
Ok, modules loaded: Main.
*Main> shiftQ (Just 42) xxxx
(Just 2,[Nothing,Nothing,Just 42])
*Main> xxxx
[Just 2,Nothing,Nothing]

Cheers,
Claus

PS. It might be a good idea to test any hypotheses about complexity.