# The snocBuilder

I recently came across the following implementation of a queue in an Haskell source

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 data SnocBuilder a = SnocBuilder !Word [a] [a] -- Smart constructor that rotates the builder when lp is one minus a power of 2 sb :: Word -> [a] -> [a] -> SnocBuilder a sb lp f r | lp < 255 || (lp .&. (lp + 1)) /= 0 = SnocBuilder lp f r | otherwise = SnocBuilder lp (f ++ reverse r) [] -- The empty builder emptySB :: SnocBuilder a emptySB = SnocBuilder 0 [] [] -- Add an element to the end of a queue. snocSB :: SnocBuilder a -> a -> SnocBuilder a snocSB (SnocBuilder lp f r) x = sb (lp + 1) f (x:r) 

What is the amortised running time of snocSB?

×