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?

×

Problem Loading...

Note Loading...

Set Loading...