Lazily consuming a self-referential linked list

Applying your suggestions in the quote produces this code:

go :: [q] -> s -> (q -> s -> [q] -> ([q], s)) -> ([q], s)
go qs s0 f = case qs of
  [] -> ([], s0)
  q:rest -> let
      (qs1, s1) = f q s0 rest -- exchanged qs2 for rest
      (qs2, s2) = go qs1 s1 f -- exchanged rest for qs1
    in (qs2, s2) -- exchanged qs1 for qs2

I’m not quite sure what kind of behaviour this would be, I feel like the run would need to be adjusted as well. Maybe what you’re aiming for is this?

go :: [q] -> s -> (q -> s -> [q] -> ([q], s)) -> s
go qs s0 f = case qs of
  [] -> ([], s0)
  q:rest -> let
      (qs1, s1) = f q s0 rest
    in  go qs1 s1

Which would produce a LIFO queue, unless concatenation is used.

I’m afraid the condensed go function might perform poorly when a lot of tasks enqueue two more tasks, leading to catastrophic concatenation. I might just try it… premature optimization is the root of all evil, after all.