In Type-Driven Development with Idris, ch 6, he says
- Type-level functions exist at compile time only ...
- Only functions that are total will be evaluated at the type level. A function that isn't total may not terminate, or may not cover all possible inputs. Therefore, to ensure that type-checking itself terminates, functions that are not total are treated as constants at the type level, and don't evaluate further.
I'm having difficulty understanding what the second bullet point means.
one: Nat
one = 1
is a constant? If so, how could that enable the type checker to complete its job?Partial type-level functions are treated as constants in the Skolem sense: invocations of a partial function f
remain f
with no further meaning.
Let's see an example. Here f
is a partial predecessor function:
f : Nat -> Nat
f (S x) = x
If we then try to use it in a type, it will not reduce, even though f 3
would reduce to 2
:
bad : f 3 = 2
bad = Refl
When checking right hand side of bad with expected type
f 3 = 2
Type mismatch between
2 = 2
(Type ofRefl
) andf 3 = 2
(Expected type)
So f
is an atomic constant here, standing only for itself. Of course, because it does stand for itself, the following still typechecks:
good : f 3 = f 3
good = Refl