Type Families and Functional Dependencies

37.1 Type Families (Type-Level Functions)

{-# LANGUAGE TypeFamilies, DataKinds, UndecidableInstances #-}
import Data.Kind (Type)

-- Closed type family
type family Elem (c :: Type) :: Type where
  Elem [a] = a
  Elem (Maybe a) = a

firstElem :: [a] -> Elem [a]
firstElem = head

-- Associated type family (inside a class)
class Container f where
  type Item f :: Type
  empty :: f
  insert :: Item f -> f -> f
  toL :: f -> [Item f]

newtype IntBag = IntBag [Int]
instance Container IntBag where
  type Item IntBag = Int
  empty = IntBag []
  insert x (IntBag xs) = IntBag (x : xs)
  toL (IntBag xs) = xs

-- Data families: different representations per type
data family Array a
data instance Array Bool = BoolArray Integer      -- bit-packed
data instance Array Int = IntArray [Int]

37.2 Functional Dependencies

{-# LANGUAGE FunctionalDependencies #-}
-- "the collection type determines the element type"
class Collection c e | c -> e where
  cinsert :: e -> c -> c
  cempty :: c

instance Collection [a] a where
  cinsert = (:)
  cempty = []
-- mtl uses fundeps: class Monad m => MonadState s m | m -> s

37.3 Type-Level Computation

{-# LANGUAGE DataKinds, TypeFamilies, TypeOperators, UndecidableInstances #-}
import GHC.TypeLits

type family Length (xs :: [k]) :: Nat where
  Length '[] = 0
  Length (x ': xs) = 1 + Length xs

-- natVal (Proxy @(Length '[Int, Bool, Char])) == 3   (import Data.Proxy)