Lazily consuming a self-referential linked list

Leary:

Perhaps you just want this?

This was a great suggestion, I ended up trying this, it works perfectly well when you sprinkle in strictness annotations. My implementation, sadly, was still outperformed by Data.Sequence.Seq both in terms of space and time.

olf:

I’m missing the broader picture here, would you care to explain?

Sure, algorithms I had in mind were something like breadth-first-search, dijktra, A*, FIRST-Set of a Grammar Nonterminal. All of these problems have a recursive notion. E.g. to determine the First-Set of Nonterminal you must also determine the First Set of all Nonterminals that are reachable through the original. Or in my abstraction, any abstract “job” can issue any number of new work portions that arose from it’s processing. The function signature was very involved because I tried so hard to have a lazily generated work queue.

I want to thank everyone involved for the suggestions, I had a blast trying it all and benchmarking some stuff, though nothing held up against an implementation that used Seq.

I’m now doing this: j -> m (Seq j, a), it is always possible to read the current job, perform a monadic action and produce a Sequence of new jobs that should be run afterwards. This is very boring (no infinitely lazy lists) but very memory and space-efficient, apparently.

I think I might release a small library if this abstraction proves useful for me. What I’m doing currently looks like this:

breadthFirstSeach :: Graph Vertex -> Vertex -> Set Vertex
breadthFirstSearch graph start = WorkList.run (Set.singleton start) [start] $ do
  node <- WorkList.current
  visited <- State.get
  forM_ (neighbors graph node) $ \ neighbor -> do
    unless (neighbor `Set.member` visited) $ WorkList.queue neighbor
    State.modify (Set.insert neighbor)

the do-notation-block would have this type:

bfsDo :: WorkList Vertex (Set Vertex) ()

the first type argument is the job type, the second one is the state type and the third one is the monadic result type.

Using the WorkList.run function will run the monadic computation repeatedly until the job queue is empty and then yield the final state.

run :: Foldable f => s -> f q -> WorkList q s () -> s