Does Haskell have kind unification?

user_61342 0
Viewed 168

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’

singleton-type data-kinds dependent-type higher-kinded-types haskell
1 Answers

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.

user_32349590
Related