{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigb32m3ry6rmqhoawgfn6nlbv5btnut3bqsp7guaydmy2og5maicu",
    "uri": "at://did:plc:pi6woz4d47bkuws673w2il2r/app.bsky.feed.post/3mm6yoti3scm2"
  },
  "path": "/t/lazily-consuming-a-self-referential-linked-list/14131#post_1",
  "publishedAt": "2026-05-19T07:57:35.000Z",
  "site": "https://discourse.haskell.org",
  "textContent": "I grew tired of explicitly writing fixed-point/worklist algorithms so I tried to create a combinator for it, the signature looks like this:\n\n\n    run :: [q] -> s -> (q -> s -> [q] -> ([q], s)) -> s\n\n\nWhich is to say: Given any queue of workqueue jobs, an initial state and a function to perform a job by updating the state and enqueuing new jobs, compute the final state.\n\nI first used `Data.Sequence.Seq` for the queue for more efficient FIFO semantics, but I thought I could do better, hopefully without any concatenation, so I ended up doing this:\n\n\n    run :: [q] -> s -> (q -> s -> [q] -> ([q], s)) -> s\n    run initial state action\n      = let\n          (qs, state') = go (initial ++ qs) state action\n        in state'\n\n\nThis is awesome! The function can access their own generated queue elements and process them all, I implemented `go` like this:\n\n\n    go :: [q] -> s -> (q -> s -> [q] -> ([q], s)) -> ([q], s)\n    go qs s0 f = case qs of\n      [] -> ([], s0)\n      q:rest -> let\n          (qs1, s1) = f q s0 qs2\n          (qs2, s2) = go rest s1 f\n        in (qs1, s2)\n\n\nThis threads the state forwards and the list backwards, but hides one caveat.\n\nIn the case where the list is (finally) depleted or the run function is called with an empty queue, this happens:\n\n\n    run [] undefined undefined\n    -- expands to\n    let\n      (qs, state') = go ([] ++ qs) undefined undefined\n    in state'\n    -- also expand go, rename variables for clarity\n    let\n      (qsOuter, state') =\n      let\n        qsInner = [] ++ qsOuter\n        s0 = undefined\n        f = undefined\n      in case qsInner of\n        -- omitted\n    in\n\n\nWhich is just a very elaborated way to say:\n\n\n    let (qs, state') = case qs of\n      -- blah\n\n\nIs there a way to correctly detect the end of the list?\nMy only idea is a counter which keeps track of how many items were consumed/generated (it is possible to keep track of this.), list evaluation would immediately stop when the counter reaches zero. But this feels like cheating.",
  "title": "Lazily consuming a self-referential linked list"
}