compdata-0.9: Compositional Data Types

Copyright (c) 2014 Patrick Bahr BSD3 Patrick Bahr experimental non-portable (GHC Extensions) None Haskell98

Data.Comp.Mapping

Description

This module provides functionality to construct mappings from positions in a functorial value.

Synopsis

# Documentation

data Numbered a Source

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

Constructors

 Numbered Int 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 IntMap Traversable Tree 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 (ErrorT e f) Traversable f => Traversable (WriterT w f) Traversable f => Traversable (WriterT w f) Traversable f => Traversable (ExceptT e f) Traversable f => Traversable (Cxt h f) Traversable f => Traversable ((:&:) * f a) (Traversable f, Traversable g) => Traversable ((:+:) * f g)

class Functor m => Mapping m k | m -> k where Source

Methods

(&) :: m v -> m v -> m v infixr 0 Source

left-biased union of two mappings.

(|->) :: k -> v -> m v infix 1 Source

This operator constructs a singleton mapping.

empty :: m v Source

This is the empty mapping.

prodMap :: v1 -> v2 -> m v1 -> m v2 -> m (v1, v2) Source

This function constructs the pointwise product of two maps each with a default value.

findWithDefault :: a -> k -> m a -> a Source

Returns the value at the given key or returns the given default when the key is not an element of the map.

lookupNumMap :: a -> Int -> NumMap t a -> a Source