@a_cowley So to be clear, I haven’t benchmarked this, but I can’t imagine it’s great if you’re calling/replacing those higher-order functions a lot. Thunks aren’t free. But that’s going to be the case with anything where you’re traversing trees/replacing subtrees repeatedly, too.
@a_cowley And some things, like repeated substitutions (inlining!) of globals, can be performed by composing onto the function in O(1), deferring the actual *work* just like with difference lists.
@a_cowley I also haven’t yet done any sort of optimization passes or similar yet; doing that kind of graph traversal/transformation may be more difficult than e.g. unification has been. But I’m hopeful!
@a_cowley All in all I feel pretty happy with using it instead of a de Bruijn indexed representation, especially since I don’t need to think about capture avoidance in global substitution *at all* (since lambdas can’t bind globals).
@a_cowley I wonder (idly) if the repeated construction/elimination of the higher-order functions during unification could be asymptotically improved by the Reflection Without Remorse techniques, i.e. using a type-aligned queue instead of a function per se.
