{-# LANGUAGE GADTs #-}
module PaperCode where


data Stepwise i a where
  Fail     :: String -> Stepwise i a
  Info     :: i -> Stepwise i a -> Stepwise i a
  Return   :: a -> Stepwise i a
  Pending  :: Stepwise i a -> Parents i a b -> Stepwise i b

data Parents i a b where
  None  :: Parents i a a
  Bind  :: (a -> Stepwise i b) -> Parents i b c -> Parents i a c


lazyEval :: Stepwise i a -> a
lazyEval  (Fail s)       = error s
lazyEval  (Info _ m)     = lazyEval m
lazyEval  (Return v)     = v
lazyEval  (Pending m p)  = evalPending p (lazyEval m)

evalPending :: Parents i a b -> a -> b
evalPending None        = id
evalPending (Bind f r)  = evalPending r . lazyEval . f


data Report i a where
  Failed  :: String -> Report i a
  Done    :: a -> Report i a
  Step    :: i -> Stepwise i a -> Report i a

next :: Stepwise i a -> Report i a
next (Fail s)       = Failed s
next (Info i m)     = Step i m
next (Return v)     = Done v
next (Pending m p)  = next' m p

next' :: Stepwise i a -> Parents i a b -> Report i b
next' (Fail s)    _          = Failed s
next' (Info i m)  r          = Step i (Pending m r)
next' m  None                = next m
next' (Return v) (Bind f r)  = next' (f v) r
next' (Pending m r') r       = next . Pending m $ push r' r

push :: Parents i a b -> Parents i b c -> Parents i a c
push None r = r
push (Bind f r') r = Bind f (push r' r)


instance Monad (Stepwise i) where
  return   = Return
  fail     = Fail
  m >>= f  = Pending m (Bind f None)