Skip to content

WIP: Try generalizing free variable traversals

Ben Gamari requested to merge wip/fvs into master

This is an experiment to common-up the free variable traversal logic.

This was motivated by the new story for zapped coercions laid forth in !1466 (closed) which will require yet another set of free variable traversals. Given that we already have several variants of such traversals open-coded in various places throughout the free, I thought it might be worthwhile to try consolidating things.

The implementation here essentially introduces a final-tagless encoding for free variable traversals. We then introduce three interpretations:

  • An non-deterministic interpretation (providing tyCoVarsOfType, et al.)
  • A deterministic interpretation (providing tyCoFVsOfType, et al.)
  • A simple non-zero-cardinality traversal (providing noFreeVarsOfType, et al.)

We then explicitly SPECIALISE for each of these interpretations. The real question is whether the simplifier can be coerced into generating the same efficient code from the abstracted approach implemented here that it does currently. This remains an open question.

To do:

  • Verify that performance has not regressed
  • Sort out better story for import cycles?
  • Less obscure name for FSM
  • Introduce unionFV and emptyFV synonyms for <> and mempty?
  • Documentation

Depends upon !1487 (closed).

Edited by Ben Gamari

Merge request reports