Fluctuation counting Monoid

Flux.hs

-- | 'Flux' is a monoid which counts the number of times an element changes
-- values (according to its Eq instance)
-- This is useful for gaining associativity (and its associated performance improvements)
-- for tasks where you'd otherwise use `group` or `groupBy`
data Flux a = Flux
  -- We keep track of the last value we saw on the left and right sides of the accumulated
  -- sequence; `Nothing` is used in the identity case meaning no elements have yet
  -- been encountered
  { sides :: Maybe (a, a)
  -- We have a counter which increments each time we mappend another Flux who's
  -- left doesn't match our right or vice versa depending on which side it is mappended onto.
  , getFlux :: Int
  } deriving (Show, Eq)


-- | Embed a single value into a Flux;
-- number of changes starts at 0.
flux :: a -> Flux a
flux a = Flux (Just (a, a)) 0

instance (Eq a) => Monoid (Flux a) where
  mempty = Flux Nothing 0
  Flux Nothing _ `mappend` f = f
  f `mappend` Flux Nothing _ = f
  Flux (Just (l, r)) n `mappend` Flux (Just (l', r')) n'
    | r == l' = Flux (Just (l, r')) (n + n')
    | otherwise = Flux (Just (l, r')) (n + n' + 1)

-- Now that it's set up, we can try it out!

-- > getFlux $ foldMap flux ["a", "b", "b", "a"]
-- 2
-- > getFlux $ foldMap flux ["a", "b", "b", "a", "c", "c", "c"]
-- 3

-- I'll be using this to implement a layer on top of the FingerTree used for
-- the Rope data-structure to allow efficient groupings of data by annotations
-- according to some predicate. FingerTrees require a monoidal measure to efficiently
-- segment and look up data, Flux provides this Monoid for the `group` operation.