transducers.idr

module Transducers

import Control.Category
import Control.Arrow

data Transducer : Type -> Type -> Type where
  T : ({r : Type} -> (b -> r -> r) -> (a -> r -> r)) -> Transducer a b

instance Category Transducer where
  id = T (\cons => cons)
  (T t1) . (T t2) = T (\cons => t2 . t1 $ cons)

instance Arrow Transducer where
  arrow f = T $ \cons => (\a, r => cons (f a) r)
  first (T t) = T $ \cons => \(b,d), r => let cons' = t $ \c, r => cons (c, d) r
                                          in cons' b r
                                          
mapping : (a -> b) -> Transducer a b
mapping = arrow

filtering : (a -> Bool) -> Transducer a a
filtering p = T (\cons => \a, r => if p a then cons a r else r)

flattening : Foldable t => Transducer (t a) a
flattening = T (\cons => \as, r => foldr cons r as)

flatMapping : Foldable t => (a -> t b) -> Transducer a b
flatMapping f = mapping f >>> flattening

-- equivalent to `filtering (const False)`
dropping : Transducer a a
dropping = T (\cons => \_, r => r)


looping : Transducer (a, l) (b, l) -> Transducer a b
looping (T t) = T (\cons => \a, r => ?loop)