mealy

Online statistics

Monthly Downloads: 17

Programming language: Haskell

License: BSD 3-clause "New" or "Revised" License

Tags: Project     Folding    

README

mealy

{- | A 'Mealy' is a triple of functions

 * (a -> b) __inject__ Convert an input into the state type.
 * (b -> a -> b) __step__ Update state given prior state and (new) input.
 * (c -> b) __extract__ Convert state to the output type.

 By adopting this order, a Mealy sum looks like:

> M id (+) id

where the first id is the initial injection to a contravariant position, and the second id is the covriant extraction.

 __inject__ kicks off state on the initial element of the Foldable, but is otherwise be independent of __step__.

> scan (M e s i) (x : xs) = e <$> scanl' s (i x) xs

-}
newtype Mealy a b = Mealy {l1 :: L1 a b}
  deriving (Profunctor, Category) via L1
  deriving (Functor, Applicative) via L1 a

-- | Pattern for a 'Mealy'.
--
-- @M extract step [email protected]
pattern M :: (a -> c) -> (c -> a -> c) -> (c -> b) -> Mealy a b
pattern M i s e = Mealy (L1 e s i)

{-# COMPLETE M #-}

-- | Fold a list through a 'Mealy'.
--
-- > cosieve == fold
fold :: Mealy a b -> [a] -> b
fold _ [] = panic "on the streets of Birmingham."
fold (M i s e) (x : xs) = e $ foldl' s (i x) xs

-- | Run a list through a 'Mealy' and return a list of values for every step
--
-- > length (scan _ xs) == length xs
scan :: Mealy a b -> [a] -> [b]
scan _ [] = []
scan (M i s e) (x : xs) = fromList (e <$> scanl' s (i x) xs)