I grew tired of explicitly writing fixed-point/worklist algorithms so I tried to create a combinator for it, the signature looks like this:
run :: [q] -> s -> (q -> s -> [q] -> ([q], s)) -> s
Which 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.
I 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:
run :: [q] -> s -> (q -> s -> [q] -> ([q], s)) -> s
run initial state action
= let
(qs, state') = go (initial ++ qs) state action
in state'
This is awesome! The function can access their own generated queue elements and process them all, I implemented go like this:
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 qs2
(qs2, s2) = go rest s1 f
in (qs1, s2)
This threads the state forwards and the list backwards, but hides one caveat.
In the case where the list is (finally) depleted or the run function is called with an empty queue, this happens:
run [] undefined undefined
-- expands to
let
(qs, state') = go ([] ++ qs) undefined undefined
in state'
-- also expand go, rename variables for clarity
let
(qsOuter, state') =
let
qsInner = [] ++ qsOuter
s0 = undefined
f = undefined
in case qsInner of
-- omitted
in
Which is just a very elaborated way to say:
let (qs, state') = case qs of
-- blah
Is there a way to correctly detect the end of the list?
My 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.
