Lazy.hs

{-# LANGUAGE GADTs #-}
-- | Lazy weaves enable linear-time implementations of breadth-first unfolds.
module Weave.Lazy
  ( Weave(..)
  , weft
  , mesh
  ) where

-- | Lazy weaves.
--
-- The 'Applicative' operation @('liftA2')@ combines weaves level-wise.
data Weave m a where
  Pure :: a -> Weave m a
  Weft :: m (Weave m b) -> (b -> a) -> Weave m a

instance Functor (Weave m) where
  fmap f (Pure x) = Pure (f x)
  fmap f (Weft u g) = Weft u (f . g)

instance Applicative m => Applicative (Weave m) where
  pure = Pure
  liftA2 f (Pure x) u = fmap (f x) u
  liftA2 f (Weft u g) (Pure y) = Weft u (\x -> f (g x) y)
  liftA2 f (Weft u g) (Weft v h) = Weft (liftA2 (liftA2 (,)) u v) (\ ~(x, y) -> f (g x) (h y))

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

-- | Run all the wefts in a 'Weave' sequentially.
mesh :: Monad m => Weave m a -> m a
mesh (Pure x) = pure x
mesh (Weft u f) = f <$> (u >>= mesh)