Zulip Chat Archive
Stream: lean4
Topic: Typeclass resolution with functions
Parth Shastri (Oct 22 2022 at 17:06):
In the following code, Lean fails to find an instance despite it being able to for a more complex type.
class Para (ϕ : Type u → Type u)
instance : Para λ α => α where
instance [Para ϕ] [Para ϕ'] : Para λ α => ϕ α → ϕ' α where
instance [Para ϕ] : Para λ α => List (ϕ α) where
#synth Para λ α => α -- instParaType
#synth Para λ α => α → α -- instParaTypeForAll
#synth Para λ α => List (α → α) -- instParaTypeList
#synth Para λ α => List α -- failed to synthesize Para fun α => List α
#check @instParaTypeList _ instParaType -- Para fun α => List α
Running with set_option trace.Meta.synthInstance.instances true
reveals that no candidate instances are found for the fourth resolution. From digging further, I was able to determine that the root of the issue lies in the DiscrTree
.
When converting the type to a key, the type is eta-reduced in whnfDT
, leading to the key path const Para, const List
for the last example while the first three examples result in const Para, other
. The three instances all have the key path const Para, other
, so the first three examples succeed, while the last one fails.
It turns out in this particular case, the problem can be remedied by writing
instance [Para ϕ] : Para no_index λ α => List (ϕ α) where
but there is no obvious indication for the cases in which this is necessary.
Is this a known limitation of the typeclass system? Is it possible to modify the system to correctly resolve this case?
Last updated: Dec 20 2023 at 11:08 UTC