Oblivious.hs

-- | Oblivious weaves forget the tree they are morally unfolding, saving energy.
-- Like "Weave.Lazy", oblivious weaves enable linear-time breadth-first unfolds,
-- but unlike "Weave.Lazy", they don't produce a tree.
module Weave.Oblivious where

-- | Oblivious weaves.
--
-- The 'Semigroup' operation @('<>')@ combines weaves level-wise.
data Weave m
  = End
  | Weft (m (Weave m))

instance Applicative m => Semigroup (Weave m) where
  End <> u = u
  u <> End = u
  Weft u <> Weft v = Weft (liftA2 (<>) u v)

instance Applicative m => Monoid (Weave m) where
  mempty = End

-- | A weft is one level of 'Weave'. It is a computation which returns the remaining levels.
weft :: m (Weave m) -> Weave m
weft = Weft

-- | Run all the wefts in a 'Weave' sequentially.
mesh_ :: Monad m => Weave m -> m ()
mesh_ End = pure ()
mesh_ (Weft u) = u >>= mesh_