CODEWITHSUNDEEP
haskelldependent-typehigher-kinded-typesdata-kindssingleton-type
Łukasz Lew
Łukasz Lew

Reputation: 50228

Does Haskell have kind unification?

I'm researching to what extent singleton types can simulate dependent types and I've arrived at a problem. The minimal code I replicate the error with:

{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeInType #-}

import Data.Kind(Type)

data SBool :: Bool -> Type where
  STrue :: SBool 'True
  SFalse :: SBool 'False

data SSBool :: SBool b -> Type where
  SSFalse :: SSBool 'SFalse
  SSTrue  :: SSBool 'STrue

The error message is:

Expected kind ‘SBool b’, but ‘'SFalse’ has kind ‘SBool 'False’

Upvotes: 3

Views: 178

Answers (1)

chi
chi

Reputation: 116139

You need to make the dependency explicit. The following compiles with GHC 8.0.1.

import Data.Kind(Type)

data SBool :: Bool -> Type where
  STrue :: SBool 'True
  SFalse :: SBool 'False

data SSBool :: forall (b :: Bool) . SBool b -> Type where
  SSFalse :: SSBool 'SFalse
  SSTrue  :: SSBool 'STrue

To be honest, I'm suprised by this. I was not aware that this sort of kind-dependency was allowed at all.

Note that this is not that different from Coq, where

Inductive SSBool (b: bool) : SBool b -> Type :=
  | SSFalse : SSBool SFalse
  | SSTrue  : SSBool STrue
.

fails to compile, while

Inductive SSBool : forall (b: bool), SBool b -> Type :=
  | SSFalse : SSBool false SFalse
  | SSTrue  : SSBool true STrue
.

compiles.

Upvotes: 6

Related Questions