O(1) sliding window with just a Monoid, not a Group. Via Edward Kmett, copied from http://lpaste.net/88182 for posterity.

Window.hs

module Window where

import Data.Monoid

data Window a = Window [a] a [a] deriving (Show,Read)

null :: Window a -> Bool
null (Window [] _ []) = True
null _ = False

queue :: Monoid a => a -> Window a -> Window a
queue r (Window fs s rs) = Window fs (s `mappend` r) (r:rs)

dequeueSum :: Monoid a => Window a -> Maybe (a, Window a)
dequeueSum (Window (b:bs) a rs) = Just (mappend b a, Window bs a rs)
dequeueSum (Window [] _ []) = Nothing
dequeueSum (Window [] a rs) = Just (a, Window ss mempty []) where
  ss = tail $ scanr1 mappend $ reverse rs

empty :: Monoid a => Window a
empty = Window [] mempty []