Hi,It's probably not important for finishing SRFI-234, but for the interested: I have a stateless implementation of topological sorting based on (delimited) continuations:
https://notabug.org/maximed/cargoless-rust-experiments/src/master/topological-sort.scm I tried implementing it the simple way first, with explicit stacks,but I couldn't figure it out, so I thought: ‘If the simple approach is hard, perhaps a complicated approach will be easy!’ and somehow this troll logic worked out.
The idea behind this implementation, IIRC, is that:
* if the graph were a tree, you could find a topological ordering
by doing a depth-first traversal (*) of the graph starting at the
root and printing all the nodes.
* if it's a tree, that can be implemented with basic recursion.
* but it's a (directed, acyclic) graph, not a tree, so we must
skip some recursions
* recursion is ‘stuff‘ with the call stack and continuation does
shenanigans with the call stack.
(*) For trees depth-first/breadth-first/... doesn't matter, but IIRC it
does matter for DAGs.
(The continuation stuff can probably be avoided by passing around the current value 'visting' and 'visited', but that's what I tried before and couldn't figure out ...)
I find it interesting that while I don't understand standard algorithms on topological sorting, if I just look a the basic idea behind the algorithms (e.g.: ‘based on depth-first sorting’) and allow myself to use supposedly complicated stuff like continuations, then I can easily figure out an alternate implementation by myself.
Greetings, Maxime.
OpenPGP_0x49E3EE22191725EE.asc
Description: OpenPGP public key
OpenPGP_signature
Description: OpenPGP digital signature
