Lazily consuming a self-referential linked list

As promised here’s an application of recursion schemes to your problem. What you are in fact doing is what appears to be a hylomorphism. After looking through your type classes it appears you are trying to construct containers that have list-like semantics. That is they can be unfolded and folded over. In fact your call to Foldable.toList is actually a catamorphism and can be fused with the hylomorphism. Unfortunately I don’t have time to dive deeper into the theory here, but I believe your library is a wrapper around these concepts. I would take a deeper look into the ListF data type and learn about cata-, ana-, and hylomorphisms (and maybe futu-). But nonetheless here’s a small something I came up with:

import Data.Functor.Foldable (ListF (..), hylo, project)
import Control.Monad (join)
import Data.Foldable (toList)
import Control.Category ((>>>))

data GoF m a
  = Done
  | Rec (m a)
  deriving (Functor)

newtype WorkListT t q m a = WorkListT (t -> m (q t, a))

-- | Execute the provided monadic action until the task queue is exhausted.
--
-- Will diverge if the task queue is infinite, unless the base monad allows
-- for an early exit, like t'Control.Monad.Except.ExceptT'.
run :: (Foldable f, Monad m) => f t -> WorkListT t [] m () -> m ()
run fQueue (WorkListT f) = hylo runGoF (go' project f) . toList $ fQueue

runGoF :: (Monad m) => GoF m (m ()) -> m ()
runGoF = \case
  Done  -> pure ()
  Rec x -> join x

-- Maybe (e, a) ~ ListF e a
go' :: (Functor m, Semigroup (q a)) => (q a -> ListF a (q a)) -> (a -> m (q a, b)) -> q a -> GoF m (q a)
go' snoc f = snoc >>> \case
  Nil       -> Done
  Cons a as -> Rec $ ((as <>) . fst) <$> f a

Note that go' is a co-algebra “constructor” that is given a way to project from a list, and a WorkListT construct a co-algebra where your q a is the seed and GoF is the shape of your recursion.

Final thought, I believe you can fuse the hylo and toList together but I’ll leave this an exercise.