CODEWITHSUNDEEP
haskelldependent-typetype-level-computationtype-kinds
Wheat Wizard
Wheat Wizard

Reputation: 4219

Replacing self built Naturals with GHC type level literals

I wrote some code that takes a Heterogeneous List and indexes it.

{-# Language GADTs, FunctionalDependencies, MultiParamTypeClasses, KindSignatures, DataKinds, TypeOperators, FlexibleInstances, UndecidableInstances #-}

import Data.Kind

data Nat = Z | S Nat

data Natural a where
  Zero :: Natural 'Z
  Succ :: Natural a -> Natural ('S a)

data HList a where
  EmptyList :: HList '[]
  Cons :: a -> HList b -> HList (a ': b)

class IndexType (n :: Nat) (a :: [Type]) (b :: Type) | n a -> b where
  index :: (Natural n) -> (HList a) -> b

instance IndexType 'Z (a ': b) a where
  index _ (Cons a _) = a

instance IndexType a b c => IndexType ('S a) (d ': b) c where
  index (Succ a) (Cons _ b) = index a b

To do this I implemented my own Nat and Natural types. The Nat exists solely to elevate to the Kind level and Natural exists to fulfill the kind Nat -> Type.

Now I would prefer to use GHC.TypeLits' Nat kind rather than my own however when I try to translate my code over I start to hit a wall in terms of understanding.

I want to build my IndexType class and the declaration line doesn't change any

class IndexType (n :: Nat) (a :: [Type]) (b :: Type) | n a -> b where

Since GHC.TypeLits also has its own Nat kind. However GHC.TypeLits doesn't have a replacement for Natural that I see, namely I lack something of the kind Nat -> Type. Now I could build an equivalent 

data Natural a = Natural

But this is essentially equivalent the Proxy type so I could just use that instead.

{-# Language GADTs, FunctionalDependencies, MultiParamTypeClasses, KindSignatures, DataKinds, TypeOperators, FlexibleInstances, UndecidableInstances #-}

import Data.Kind
import GHC.TypeLits
import Data.Proxy

data HList a where
  EmptyList :: HList '[]
  Cons :: a -> HList b -> HList (a ': b)

class IndexType (n :: Nat) (a :: [Type]) (b :: Type) | n a -> b where
  index :: (Proxy n) -> (HList a) -> b

Now the first instance of the IndexType class is easy enough:

instance IndexType 0 (a ': b) a where
  index _ (Cons a _) = a

However the second one starts to puzzle me. The first line seems as if it would be

instance IndexType a b c => IndexType (1 + a) (d ': b) c where

However on the second line I don't know how to replace the Succ in the original code. The data constructor for Proxy is Proxy so I suppose it must use that constructor so I must write something like:

  index Proxy (Cons _ b) = index a b

But now I'm pulling the definition of a out of thin air. I suppose it has to be another Proxy since index takes a Proxy, but I don't know how to force it to be the correct type.

Upvotes: 4

Views: 181

Answers (1)

Lucy Maya Menon
Lucy Maya Menon

Reputation: 1590

How about this?

class IndexType (n :: Nat) (a :: [Type]) (c :: Type) | n a -> c where           
  index ::  (Proxy n) -> (HList a) -> c                                         
instance IndexType 0  (a ': b) a where                                          
  index _ (Cons a _) = a                                                        
instance {-# OVERLAPS #-} (IndexType (a-1) b c) => IndexType a (d ': b) c where 
  index _ (Cons _ b) = index (Proxy @(a-1)) b

This will use some extra extensions including ScopedTypeVariables and TypeApplications. PoC (tested on GHC 8.2.2):

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}

module Foo where
import Data.Kind
import GHC.TypeLits
import Data.Proxy

data HList a where
  EmptyList :: HList '[]
  Cons :: a -> HList b -> HList (a ': b)

class IndexType (n :: Nat) (a :: [Type]) (c :: Type) | n a -> c where
  index ::  (Proxy n) -> (HList a) -> c
instance IndexType 0  (a ': b) a where
  index _ (Cons a _) = a
instance {-# OVERLAPS #-} (IndexType (a-1) b c) => IndexType a (d ': b) c where
  index _ (Cons _ b) = index (Proxy @(a-1)) b

list :: HList '[Int, Bool]
list = Cons (5 :: Int) (Cons True EmptyList)
int :: Int
int = index (Proxy @0) list
bool :: Bool
bool = index (Proxy @1) list

Upvotes: 3

Related Questions