News for hackers. Stuff that matters.
Re:Dependently Typed Programming by tel on Tuesday July 01, 2014 @11:23PM (#7974986)
You can sort of do this sometimes. Consider Idris' decidable equality module:

https://github.com/idris-lang/Idris-dev/blob/master/libs/pre...

Idris has type classes and it produces a polymorphic total function `decEq` for any type which instantiates the class DecEq.

    decEq :: DecEq t => (x : t) -> y -> Dec (x = y)
where Dec denotes a decidable type, something like (but not actually)

    data Dec t where
      Yes : t     -> Dec t
      No  : Not t -> Dec t
So now we have a proposition in our type-level prolog called `DecEq` and some types, the ones with decidable equality, can instantiate it

    instance DecEq () where 
      decEq _ _ = Yes refl
   
    -- Equality is symmetric, so is the negation of equality
    total negEqSym : {a : t} -> {b : t} -> (a = b -> _|_) -> (b = a -> _|_)
    negEqSym p h = p (sym h)

    -- Proof that zero isn't equal to any number greater than zero
    total OnotS : Z = S n -> _|_
    OnotS refl impossible

    instance DecEq Nat where
      decEq Z     Z     = Yes refl
      decEq Z     (S _) = No OnotS
      decEq (S _) Z     = No (negEqSym OnotS)

      -- recurse on the arguments together and modify the eventual
      -- decided proof so as to match the arguments actually passed. 
      --
      -- I.e. we might find that Yes (n = m) but we need Yes (S n = S m)
      --
      decEq (S n) (S m) with (decEq n m)
        | Yes p = Yes $ cong p
        | No p = No $ \h : (S n = S m) => p $ succInjective n m h
Finally, at compile time Idris will try to infer the concrete types instantiating variables throughout the program. If any of the variables are bounded by `DecEq` then it must be able to solve the typeclass prolog to establish decidable equality for that type.

If it fails to fulfill that obligation then it'll fail at compile time.

    -- this fails since functions on naturals are 
    -- far, far, far from decidable... Idris cannot achieve the
    -- obligation to find `DecEq (Nat -> Nat)`.
    decEq : (x : Nat -> Nat) -> y -> Dec (x = y)

There are no comments on this comment yet.