compdata- Compositional Data Types

Copyright(c) 2012 Patrick Bahr
MaintainerPatrick Bahr <>
Portabilitynon-portable (GHC Extensions)
Safe HaskellSafe-Inferred



This module provides functionality to number the components of a functorial value with consecutive integers.



newtype Numbered a Source

This type is used for numbering components of a functorial value.


Numbered (Int, a) 


Eq (Numbered a) 
Ord (Numbered a) 

number :: Traversable f => f a -> f (Numbered a) Source

This function numbers the components of the given functorial value with consecutive integers starting at 0.

class (Functor t, Foldable t) => Traversable t

Functors representing data structures that can be traversed from left to right.

Minimal complete definition: traverse or sequenceA.

A definition of traverse must satisfy the following laws:

t . traverse f = traverse (t . f) for every applicative transformation t
traverse Identity = Identity
traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

A definition of sequenceA must satisfy the following laws:

t . sequenceA = sequenceA . fmap t for every applicative transformation t
sequenceA . fmap Identity = Identity
sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA

where an applicative transformation is a function

t :: (Applicative f, Applicative g) => f a -> g a

preserving the Applicative operations, i.e.

and the identity functor Identity and composition of functors Compose are defined as

  newtype Identity a = Identity a

  instance Functor Identity where
    fmap f (Identity x) = Identity (f x)

  instance Applicative Indentity where
    pure x = Identity x
    Identity f <*> Identity x = Identity (f x)

  newtype Compose f g a = Compose (f (g a))

  instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = Compose (fmap (fmap f) x)

  instance (Applicative f, Applicative g) => Applicative (Compose f g) where
    pure x = Compose (pure (pure x))
    Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

(The naturality law is implied by parametricity.)

Instances are similar to Functor, e.g. given a data type

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

a suitable instance would be

instance Traversable Tree where
   traverse f Empty = pure Empty
   traverse f (Leaf x) = Leaf <$> f x
   traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

This is suitable even for abstract types, as the laws for <*> imply a form of associativity.

The superclass instances should satisfy the following:

Minimal complete definition

traverse | sequenceA


Traversable [] 
Traversable Maybe 
Traversable Identity 
Traversable XName 
Traversable XAttr 
Traversable WarningText 
Traversable Type 
Traversable TyVarBind 
Traversable Stmt 
Traversable Splice 
Traversable SpecialCon 
Traversable Safety 
Traversable RuleVar 
Traversable Rule 
Traversable Rhs 
Traversable RPatOp 
Traversable RPat 
Traversable QualStmt 
Traversable QualConDecl 
Traversable QOp 
Traversable QName 
Traversable Promoted 
Traversable PatField 
Traversable Pat 
Traversable PXAttr 
Traversable Op 
Traversable Name 
Traversable ModulePragma 
Traversable ModuleName 
Traversable ModuleHead 
Traversable Module 
Traversable Match 
Traversable Literal 
Traversable Kind 
Traversable InstHead 
Traversable InstDecl 
Traversable ImportSpecList 
Traversable ImportSpec 
Traversable ImportDecl 
Traversable IfAlt 
Traversable IPName 
Traversable IPBind 
Traversable GuardedRhs 
Traversable GuardedAlts 
Traversable GuardedAlt 
Traversable GadtDecl 
Traversable FunDep 
Traversable FieldUpdate 
Traversable FieldDecl 
Traversable ExportSpecList 
Traversable ExportSpec 
Traversable Exp 
Traversable Deriving 
Traversable DeclHead 
Traversable Decl 
Traversable DataOrNew 
Traversable Context 
Traversable ConDecl 
Traversable ClassDecl 
Traversable CallConv 
Traversable CName 
Traversable Bracket 
Traversable Binds 
Traversable BangType 
Traversable Asst 
Traversable Assoc 
Traversable Annotation 
Traversable Alt 
Traversable Activation 
Traversable (Either a) 
Traversable ((,) a) 
Ix i => Traversable (Array i) 
Traversable (Const m) 
Traversable (Proxy *) 
Traversable (Map k) 
Traversable f => Traversable (MaybeT f) 
Traversable f => Traversable (ListT f) 
Traversable f => Traversable (IdentityT f) 
Traversable (HashMap k) 
Traversable f => Traversable (WriterT w f) 
Traversable f => Traversable (WriterT w f) 
Traversable f => Traversable (ErrorT e f) 
(Traversable f, Traversable g) => Traversable (Compose f g) 
Traversable f => Traversable ((:&:) f a) 
(Traversable f, Traversable g) => Traversable ((:+:) f g) 
Traversable f => Traversable (Cxt h f)