Copyright	(c) Edward Kmett 2017
License	BSD2
Maintainer	Edward Kmett <ekmett@gmail.com>
Stability	experimental
Portability	non-portable
Safe Haskell	None
Language	Haskell2010

Coda.Relative.Class

Contents

Data types with relative positions
Relative monoids
Relative orderings

Description

In order to work with fragments of syntax trees without having to pay an inordinate cost moving around errors and terms, we need a notion of Relative data types that permit relocation cheaply.

Note: There is structure to these classes: Consider the following problematic derivation that show some instances here are incompatible with others.

Delta 1 =                             -- by instance Monoid Delta
Delta 1 <> mempty =               -- by instance MonoidalDelta t
Delta 1 <> delta mempty =       -- by instance RelativeDelta t
delta (rel (Delta 1) mempty) =  -- by instance RelativeMonoid t
delta mempty =                      -- by instance MonoidalDelta t
mempty =                              -- by definition
Delta 0

Synopsis

Data types with relative positions

class Relative a where Source #

Applying a relative position change as a left monoid action

Laws:

rel mempty ≡ id
rel (m <> n) ≡ rel m . rel n

Preferably rel relocates in O(1) or logarithmic time at worst or the container probably isn't well suited for relative use.

Note: rel d = id is a perfectly legitimate definition by these laws.

Note: if you use some stashed delta to slow the descent into your data structure, then you probably need to have nominal roles for your arguments.

Methods

rel :: Delta -> a -> a Source #

rel :: (Generic a, GRelative (Rep a)) => Delta -> a -> a Source #

Instances

Relative () Source #
Methods rel :: Delta -> () -> () Source #
Relative Void Source #
Methods rel :: Delta -> Void -> Void Source #
Relative Delta Source #
Methods rel :: Delta -> Delta -> Delta Source #
Relative Change Source #
Methods rel :: Delta -> Change -> Change Source #
Relative Edit Source #
Methods rel :: Delta -> Edit -> Edit Source #
Relative Grade Source #
Methods rel :: Delta -> Grade -> Grade Source #
Relative Token Source #
Methods rel :: Delta -> Token -> Token Source #
Relative Dyck Source #
Methods rel :: Delta -> Dyck -> Dyck Source #
Relative Closing Source #
Methods rel :: Delta -> Closing -> Closing Source #
Relative Opening Source #
Methods rel :: Delta -> Opening -> Opening Source #
Relative MismatchError Source #
Methods rel :: Delta -> MismatchError -> MismatchError Source #
Relative a => Relative [a] Source #	O(n)
Methods rel :: Delta -> [a] -> [a] Source #
Relative a => Relative (Maybe a) Source #
Methods rel :: Delta -> Maybe a -> Maybe a Source #
Relative a => Relative (NonEmpty a) Source #	O(n)
Methods rel :: Delta -> NonEmpty a -> NonEmpty a Source #
Relative a => Relative (Identity a) Source #
Methods rel :: Delta -> Identity a -> Identity a Source #
Relative (Absolute a) Source #
Methods rel :: Delta -> Absolute a -> Absolute a Source #
Relative (List a) Source #
Methods rel :: Delta -> List a -> List a Source #
Relative (Located a) Source #
Methods rel :: Delta -> Located a -> Located a Source #
Relative (Queue a) Source #
Methods rel :: Delta -> Queue a -> Queue a Source #
Relative a => Relative (Cat a) Source #
Methods rel :: Delta -> Cat a -> Cat a Source #
(Relative a, Relative b) => Relative (Either a b) Source #
Methods rel :: Delta -> Either a b -> Either a b Source #
(Relative a, Relative b) => Relative (a, b) Source #
Methods rel :: Delta -> (a, b) -> (a, b) Source #
Relative (Proxy * a) Source #
Methods rel :: Delta -> Proxy * a -> Proxy * a Source #
Relative (Map k a) Source #
Methods rel :: Delta -> Map k a -> Map k a Source #
Relative (f a) => Relative (Rev f a) Source #
Methods rel :: Delta -> Rev f a -> Rev f a Source #

class GRelative f Source #

Minimal complete definition

grel'

Instances

GRelative (V1 *) Source #
Methods grel' :: Delta -> V1 * a -> V1 * a
GRelative (U1 *) Source #
Methods grel' :: Delta -> U1 * a -> U1 * a
Relative c => GRelative (K1 * i c) Source #
Methods grel' :: Delta -> K1 * i c a -> K1 * i c a
(GRelative f, GRelative g) => GRelative ((:+:) * f g) Source #
Methods grel' :: Delta -> (* :+: f) g a -> (* :+: f) g a
(GRelative f, GRelative g) => GRelative ((::) f g) Source #
Methods grel' :: Delta -> (* :: f) g a -> ( :*: f) g a
GRelative f => GRelative (M1 * i c f) Source #
Methods grel' :: Delta -> M1 * i c f a -> M1 * i c f a
(Functor f, GRelative g) => GRelative ((:.:) * * f g) Source #
Methods grel' :: Delta -> (* :.: ) f g a -> ( :.: *) f g a

grel :: (Generic a, GRelative (Rep a)) => Delta -> a -> a Source #

We can derive relativity generically.

frel :: (Functor f, Relative a) => Delta -> f a -> f a Source #

Every functor can be relative.

birel :: (Bifunctor f, Relative a, Relative b) => Delta -> f a b -> f a b Source #

Every bifunctor can be relative.

Relative monoids

class (Relative t, Monoid t) => RelativeMonoid t Source #

Laws: rel d is a monoid homomorphism.

rel d (m <> n)   = rel d m <> rel d n
rel d mempty   = mempty

TODO: Add RelativeSemigroup in ghc 8.4

instance RelativeSemigroup Void
instance Relative a => RelativeSemigroup (NonEmpty a)

Instances

RelativeMonoid () Source #

RelativeMonoid Delta Source #

RelativeMonoid Dyck Source #

Relative a => RelativeMonoid [a] Source #

Monoid a => RelativeMonoid (Absolute a) Source #

Relative a => RelativeMonoid (List a) Source #

(RelativeMonoid a, RelativeMonoid b) => RelativeMonoid (a, b) Source #

(StrictRelativeOrder k, Relative a) => RelativeMonoid (Map k a) Source #

RelativeMonoid (f a) => RelativeMonoid (Rev f a) Source #

Relative orderings

class (Relative t, Ord t) => RelativeOrder t Source #

A relative order

Laws:

rel d is monotone, that is to say

x <= y implies rel d x <= rel d y

Instances

RelativeOrder () Source #

RelativeOrder Delta Source #

RelativeOrder a => RelativeOrder [a] Source #

RelativeOrder a => RelativeOrder (NonEmpty a) Source #

Ord a => RelativeOrder (Absolute a) Source #

RelativeOrder a => RelativeOrder (List a) Source #

Ord a => RelativeOrder (Located a) Source #

(RelativeOrder a, RelativeOrder b) => RelativeOrder (Either a b) Source #

(RelativeOrder a, RelativeOrder b) => RelativeOrder (a, b) Source #

(StrictRelativeOrder k, RelativeOrder a) => RelativeOrder (Map k a) Source #

class RelativeOrder t => StrictRelativeOrder t Source #

A _strict_ relative order

Laws:

x < y implies rel d x < rel d y

This can be useful for keys in relative maps because shifting the map can't cause keys to collapse

Instances

StrictRelativeOrder () Source #

StrictRelativeOrder Delta Source #

StrictRelativeOrder a => StrictRelativeOrder [a] Source #

StrictRelativeOrder a => StrictRelativeOrder (NonEmpty a) Source #

Ord a => StrictRelativeOrder (Absolute a) Source #

StrictRelativeOrder a => StrictRelativeOrder (List a) Source #

Ord a => StrictRelativeOrder (Located a) Source #

(StrictRelativeOrder a, StrictRelativeOrder b) => StrictRelativeOrder (Either a b) Source #

(StrictRelativeOrder a, StrictRelativeOrder b) => StrictRelativeOrder (a, b) Source #

(StrictRelativeOrder k, StrictRelativeOrder a) => StrictRelativeOrder (Map k a) Source #