-- | 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
  Weave m
End <> :: Weave m -> Weave m -> Weave m
<> Weave m
u = Weave m
u
  Weave m
u <> Weave m
End = Weave m
u
  Weft m (Weave m)
u <> Weft m (Weave m)
v = m (Weave m) -> Weave m
forall (m :: * -> *). m (Weave m) -> Weave m
Weft ((Weave m -> Weave m -> Weave m)
-> m (Weave m) -> m (Weave m) -> m (Weave m)
forall a b c. (a -> b -> c) -> m a -> m b -> m c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Weave m -> Weave m -> Weave m
forall a. Semigroup a => a -> a -> a
(<>) m (Weave m)
u m (Weave m)
v)

instance Applicative m => Monoid (Weave m) where
  mempty :: Weave m
mempty = Weave m
forall (m :: * -> *). Weave m
End

-- | A weft is one level of 'Weave'. It is a computation which returns the remaining levels.

weft :: m (Weave m) -> Weave m
weft :: forall (m :: * -> *). m (Weave m) -> Weave m
weft = m (Weave m) -> Weave m
forall (m :: * -> *). m (Weave m) -> Weave m
Weft

-- | Run all the wefts in a 'Weave' sequentially.

mesh_ :: Monad m => Weave m -> m ()
mesh_ :: forall (m :: * -> *). Monad m => Weave m -> m ()
mesh_ Weave m
End = () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
mesh_ (Weft m (Weave m)
u) = m (Weave m)
u m (Weave m) -> (Weave m -> m ()) -> m ()
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Weave m -> m ()
forall (m :: * -> *). Monad m => Weave m -> m ()
mesh_