Closed RyanGlScott closed 2 months ago
This is probably worth doing anyway, as we aren't really making essential use of the fact that
pr_scoped_vars
is anOSet
(i.e., we aren't really using that many set-like operations onpr_scoped_vars
).
I retract this claim, as there is one place where we rely on pr_scoped_vars
being an OSet
: when promoting pattern signatures. For example, consider foo8
from the T183
test case:
When promoting the Just (_ :: a)
pattern, should we bind a
as a scoped type variable? It depends! If a
is already in scope (i.e., due to an outermost forall
, like what foo8
's type signature uses), then we treat a
as a bound variable rather than binding it as a scoped type variable. Otherwise, we do bind a
. This means that we can't add to the scoped type variables unconditionally, as whether we do or not depends on whether pr_scoped_vars
already contains a
or not.
If pr_scoped_vars
is an OSet
, then checking this is easy: we just call OSet.insert a (pr_scoped_vars ...)
, and OSet.insert
will do the heavy lifting of checking if a
is already contained in the scoped type variables or not. If pr_scoped_vars
were a list, however, we'd need to explicitly check if a
is contained in the list beforehand, which is an O(n) operation. Not impossible, but a tad bit unsightly.
For this reason, I'm inclined to keep pr_scoped_vars
as an OSet
and instead change the Ord
instance for LocalVar
to only consider the Name
(and not the Maybe DKind
) for comparison purposes. We maintain the invariant that every LocalVar
Name
uniquely maps to a Maybe DKind
, so this should be an acceptable thing to do.
(Originally posted in https://github.com/goldfirere/singletons/pull/610#issuecomment-2190208845).
As of #610, we use
LocalVar
s to track the kinds of promoted term-level variables, but not the kinds of scoped type variables:https://github.com/goldfirere/singletons/blob/a3511058a6f0027edcfec891748e7433ffbb9188/singletons-th/src/Data/Singletons/TH/Promote/Monad.hs#L31-L35
Note that
pr_scoped_vars
uses a set ofName
s rather thanLocalVar
s. This means that if we were to promote something like this:Then we promote
y
, we would get something like this:This doesn't record the fact that
a :: k
, unfortunately. As such, the kind ofLetY
is more general than intended:This doesn't cause problems in any of the code in
singletons-base
, but I could easily foresee this being an issue in more sophisticated code. (See also #601.) If we usedLocalVar
s inpr_scoped_vars
, however, this would be possible.Note that if we did this, we might consider changing
pr_scoped_vars
to use a list ofLocalVar
s instead of anOSet
, as otherwise we would be sorting all of theLocalVar
s using theirDKind
'sOrd
instance, which seems wasteful. This is probably worth doing anyway, as we aren't really making essential use of the fact thatpr_scoped_vars
is anOSet
(i.e., we aren't really using that many set-like operations onpr_scoped_vars
).