Difference between Haskell and Idris: Reflection of Runtime/Compiletime in the type universes

Question

So in Idris it's perfectly valid to write the following.

item : (b : Bool) -> if b then Nat else List Nat
item True  = 42
item False = [1,2,3] // cf. https://www.youtube.com/watch?v=AWeT_G04a0A

Without the type signature, this looks like a dynamically typed language. But, indeed, Idris is dependently-typed. The concrete type of item b can only be determined during run-time.

This is, of course, a Haskell-programmer talking: The type of item b in the Idris sense is given during compile-time, it is if b then Nat ....

Now my question: Am I right to conclude that in Haskell, the border between the runtime and the compiletime runs exactly between the world of values (False, "foo", 3) and the world of types (Bool, String, Integer) whereas in Idris, the border between the runtime and the compiletime goes across universes?

Also, am I right to assume that even with dependent types in Haskell (using DataKinds and TypeFamilies, cf. this article) the above example is impossible in Haskell, because Haskell contrary to Idris does not allow values to leak to the type-level?

Answer 1

Yes, you're right to observe that the types versus values distinction in Idris does not align with the compiletime-only versus runtime-and-compiletime distinction. That's a good thing. It is useful to have values which exist only at compiletime, just as in program logics we have "ghost variables" used only in specifications. It is useful also to have type representations at runtime, allowing datatype generic programming.

In Haskell, DataKinds (and PolyKinds) let us write

type family Cond (b :: Bool)(t :: k)(e :: k) :: k where
  Cond 'True  t e = t
  Cond 'False t e = e

and in the not too distant future, we shall be able to write

item :: pi (b :: Bool) -> Cond b Int [Int]
item True  = 42
item False = [1,2,3]

but until that technology is implemented, we have to make do with singleton forgeries of dependent function types, like this:

data Booly :: Bool -> * where
  Truey  :: Booly 'True
  Falsey :: Booly 'False

item :: forall b. Booly b -> Cond b Int [Int]
item Truey  = 42
item Falsey = [1,2,3]

You can get quite far with such fakery, but it would all get a lot easier if we just had the real thing.

Crucially, the plan for Haskell is to maintain and separate forall and pi, supporting parametric and ad hoc polymorphism, respectively. The lambdas and applications that go with forall can still be erased in runtime code generation, just as now, but those for pi are retained. It would also make sense to have runtime type abstractions pi x :: * -> ... and throw the rats' nest of complexity that is Data.Typeable into the dustbin.

Answer 2

Now my question: Am I right to conclude that in Haskell, the border between the runtime and the compiletime runs exactly between the world of values (False, "foo", 3) and the world of types (Bool, String, Integer) whereas in Idris, the border between the runtime and the compiletime goes across universes?

Idris compiles to Epic (UPDATE: no, it no longer compiles to Epis as Spearman says in the comment below):

No semantic checking, other than to see if names are in scope --- it is assumed that the higher level language will have performed typechecking, and in any case Epic should make no assumptions about the higher level type system or any transformations you've applied. Type annotations are required, but they only give hints to the compiler (I might change this).

So types do not matter denotationally, i.e. the meaning of a term doesn't depend on its type. Moreover some value level things can be erased, e.g. in Vect n A (where Vect is the type of lists with statically known length) n (the length) can be erased, because

There are methods described by Brady, McBride and McKinna in BMM04 to remove the indices from data structures, exploiting the fact that functions operating on them either already have a copy of the appropriate index or the index can be quickly reconstructed if needed.

The thing here is that pi in Idris acts for types in almost the same way as forall in Haskell: they are both parametric (though, these parametricities are different) in this case. A compiler can use types to optimize code, but in both languages control flow doesn't depend on types, i.e. you can't say if A == Int then ... else ... (though, if A is in canonical form, then you know statically whether it's Int or not and hence can write A == Int, but that still doesn't affect control flow, because all decisions are maken before runtime). The concrete type of item b just doesn't matter at runtime.

However as pigworker says it's not necessarily to be parametric in types. As well as it's not necessarily to be non-parametric in values. Type-level — value-level and parametric — non-parametric are completely orthogonal dichotomies. See this answer for details.

So Haskell and Idris are different in how they treat value level things wrt runtime/compile content (because in Idris you can mark an argument with . to make it erasable), but they treat types in roughly the same way.