compdata-0.7.0.2: Compositional Data Types

Copyright (c) 2012 Patrick Bahr BSD3 Patrick Bahr experimental non-portable (GHC Extensions) Safe-Inferred Haskell98

Data.Comp.Number

Description

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

Synopsis

# Documentation

newtype Numbered a Source

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

Constructors

 Numbered (Int, a)

Instances

 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:

naturality
`t . traverse f = traverse (t . f)` for every applicative transformation `t`
identity
`traverse Identity = Identity`
composition
`traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f`

A definition of `sequenceA` must satisfy the following laws:

naturality
`t . sequenceA = sequenceA . fmap t` for every applicative transformation `t`
identity
`sequenceA . fmap Identity = Identity`
composition
`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.

• `t (`pure` x) = `pure` x`
• `t (x `<*>` y) = t x `<*>` t y`

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:

• In the `Functor` instance, `fmap` should be equivalent to traversal with the identity applicative functor (`fmapDefault`).
• In the `Foldable` instance, `foldMap` should be equivalent to traversal with a constant applicative functor (`foldMapDefault`).

Minimal complete definition

Instances

 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)