Note that the lazy DFA and its lower level APIs exists now and threads this needle.

Maybe not in the general case for arbitrary abstracted datastructures, but I have done it in a basic test to see if it's viable for my use-case, which is why I made that claim at all.