MIT licensed by Li-yao Xia
Maintained by [email protected]
This version can be pinned in stack with:first-class-families-,1597

First-class type families Hackage Build Status

First-class type families are type-level functions that can be composed using higher-order functions.

The core of the idea is an extensible kind of “type-level expressions” and an open type family for evaluating such expressions.

type Exp (k :: Type) :: Type
type family Eval (e :: Exp k) :: k

This library provides that core foundation, and also exports basic first-class type families.


For example, consider this simple type family:

type family   FromMaybe (a :: k) (m :: Maybe k) :: k
type instance FromMaybe a 'Nothing  = a
type instance FromMaybe a ('Just b) = b

With first-class-families (fcfs), it translates to a data declaration and instances for a single Eval family:

import Fcf

data FromMaybe :: k -> Maybe k -> Exp k
type instance Eval (FromMaybe a 'Nothing)  = a
type instance Eval (FromMaybe a ('Just b)) = b

That way, the FromMaybe constructor can be partially applied, and passed to higher-order fcfs such as Map:

Eval (Map (FromMaybe 0) '[ 'Just 1, 'Nothing ])  =  '[ 1, 0 ] :: [Nat]

Essential language extensions:

    UndecidableInstances #-}


  • Fcf.Core: definition of Exp and Eval.
  • Fcf.Combinators: general combinators to compose first-class families.
  • Fcf.Data.*: first-class families on common data types.
  • Fcf.Class.*: overloaded first-class families.
  • Fcf.Utils: miscellaneous.

The top-level module Fcf is a prelude to get acquainted with the library. For regular use, import what you need from the specialized modules above, preferably with explicit import lists.

import Fcf                       -- Simple but fragile

import Fcf.Class.Functor (FMap)  -- Explicit and robust


Overloaded type families

Value-level functions can be overloaded using type classes. Type families—type-level functions—are open by design, so overloading is as easy as just declaring them with more general types.

data Map :: (a -> Exp b) -> f a -> Exp (f b)

-- Instances for f = []
type instance Eval (Map f '[]) = '[]
type instance Eval (Map f (x ': xs)) = Eval (f x) ': Eval (Map f xs)

-- Instances for f = Maybe
type instance Eval (Map f 'Nothing) = 'Nothing
type instance Eval (Map f ('Just x)) = 'Just (Eval (f x))

See also

Contributions are welcome. Feel free to open an issue or make a PR on Github!


  • Add (Fcf.Combinators.>>=)
  • Resolve warnings about deprecated TypeInType

  • Bump upper bounds for GHC 9.0
  • Update doctests for cabal-docspec

  • Add modules

    • Fcf.Data.Symbol (currently just reexports Symbol) (thanks to gspia)
    • Fcf.Data.Function
    • “Overloaded type families” (“type-level type classes”)
      • Fcf.Class.Ord
      • Fcf.Class.Monoid
      • Fcf.Class.Monoid.Types (which exports just an Endo a to wrap a -> Exp a)
      • Fcf.Class.Functor
      • Fcf.Class.Bifunctor
      • Fcf.Class.Foldable
  • Add functions in Fcf.Data.List: Intersperse, Intercalate, Span, Break, Tails, IsPrefixOf, IsSuffixOf, IsInfixOf, Partition.

  • Generalize Foldr, Concat and ConcatMap to foldable types.

  • Remove deprecated Guarded, Guard((:=)), Otherwise.

  • Deprecate Fcf.Classes

  • Add Unfoldr, Concat, ConcatMap, Replicate, Take, Drop, TakeWhile, DropWhile, Reverse to Data.List. (thanks to gspia)
  • Change Elem, Lookup, Zip to be data instead of type synonyms.
  • Fix performance of Filter and Find.

  • Add Fcf.Utils.Case (thanks to TheMatten)
  • Deprecate Fcf.Bool.Guarded
  • GHC 8.8 compatibility

  • Modularized library

  • Fcf.Utils:

    • Add TError
    • Rename Collapse to Constraints
  • Fcf.Data.List: Added Cons, Last, Init, Elem

  • New functions (thanks to blmage)

    • LiftM, LiftM2, LiftM3
    • (<=), (>=), (<), (>)
    • Guarded, Guard((:=)), Otherwise

  • GHC 8.6 compatibility

  • More new functions, (thanks to isovector)

  • A whole bunch of basic functions (thanks to isovector)
  • Remove Traverse (now Map), BimapPair, BimapEither (now Bimap)

Initial version