run-length.hs

import Data.Sequence (Seq (Empty, (:<|), (:|>)))
import qualified Data.Sequence as Seq

newtype RunLength a = RunLength (Seq.Seq (Int, a))
  deriving (Eq, Show)

singleton :: a -> RunLength a
singleton a = RunLength (Seq.singleton (1, a))

runLengthToList :: RunLength a -> [a]
runLengthToList (RunLength runs) = foldMap (uncurry replicate) runs

instance Eq a => Semigroup (RunLength a) where
  RunLength (as :|> (countA, a)) <> RunLength ((countB, b) :<| bs)
    | a == b = RunLength ((as :|> (countA + countB, a)) <> bs)
  RunLength as <> RunLength bs = RunLength (as <> bs)

instance Eq a => Monoid (RunLength a) where
  mempty = RunLength Empty

runLengthFromList :: Eq a => [a] -> RunLength a
runLengthFromList = foldMap singleton