connections-0.3.1: Orders, Galois connections, and lattices.

Safe HaskellSafe
LanguageHaskell2010
ExtensionsPatternSynonyms

Data.Connection

Contents

Description

This library provides connections between common types, combinators & accessors, including lawful versions of floor, ceiling, round, and truncate. There is also a separately exported Connection class, along with lawful versions of fromInteger and fromRational, suitable for use with -XRebindableSyntax. Lastly, there are Semilattice and Algebra classes based on the same construction.

connections is extensively tested, and it exports properties for use in testing your own connections. See Data.Connection.Property and Data.Lattice.Property. In addition to the property tests there are several doctests scattered around, these are runnable as a standalone executable. See the doctest stanza in the library's cabal file.

Synopsis

Documentation

What is a Galois connection?

A Galois connection is an adjunction in the category of preorders: a pair of monotone maps f :: p -> q and g :: q -> p between preorders p and q, such that

f x <= y if and only if x <= g y

We say that f is the left or lower adjoint, and g is the right or upper adjoint of the connection.

For illustration, here is a simple example from 7 Sketches:

Note that the two component functions are each monotonic:

 x1 <= x2 implies f x1 <= f x2

and furthermore they are are interlocked (i.e. adjoint) in the specific way outlined above:

 f x <= y if and only if x <= g y

See the README for a more extensive overview.

Types

data Conn (k :: Side) a b Source #

A chain of Galois connections of length 2 or 3.

Connections have many nice properties wrt numerical conversion:

>>> inner ratf32 (1 / 8)    -- eighths are exactly representable in a float
1 % 8
>>> outer ratf32 (1 % 8)
(0.125,0.125)
>>> inner ratf32 (1 / 7)    -- sevenths are not
9586981 % 67108864
>>> outer ratf32 (1 % 7)
(0.14285713,0.14285715)

Another example avoiding loss-of-precision:

>>> f x y = (x + y) - x
>>> maxOdd32 = 1.6777215e7
>>> f maxOdd32 2.0 :: Float
1.0
>>> round2 f64f32 f maxOdd32 2.0
2.0

See the README file for a slightly more in-depth introduction.

Instances
Category (Conn k :: Type -> Type -> Type) Source # 
Instance details

Defined in Data.Connection.Conn

Methods

id :: Conn k a a #

(.) :: Conn k b c -> Conn k a b -> Conn k a c #

data Side Source #

A data kind distinguishing links in a chain of Galois connections of length 2 or 3.

If a connection is existentialized over this value (i.e. has type forall k. Conn k a b) then it can provide either of two functions f, h :: a -> b.

This is useful because it enables rounding, truncation, medians, etc.

Constructors

L 
R 

Conn L

connL :: Conn R a b -> Conn L b a Source #

Witness to the mirror symmetry between ConnL and ConnR.

connL . connR = id
connR . connL = id

pattern ConnL :: (a -> b) -> (b -> a) -> Conn L a b Source #

A Galois connection between two monotone functions.

A Galois connection between f and g, written \(f \dashv g \) is an adjunction in the category of preorders.

Each side of the connection may be defined in terms of the other:

\( g(x) = \sup \{y \in E \mid f(y) \leq x \} \)

\( f(x) = \inf \{y \in E \mid g(y) \geq x \} \)

Caution: ConnL f g must obey \(f \dashv g \). This condition is not checked.

For further information see Property.

Conn R

connR :: Conn L a b -> Conn R b a Source #

Witness to the mirror symmetry between ConnL and ConnR.

connL . connR = id
connR . connL = id

pattern ConnR :: (b -> a) -> (a -> b) -> Conn R a b Source #

A Galois connection between two monotone functions.

ConnR is the mirror image of ConnL:

connR :: ConnL a b -> ConnR b a

If you only require one connection there is no particular reason to use one version over the other. However some use cases (e.g. rounding) require an adjoint triple of connections that can lower into a standard connection in either of two ways.

Caution: ConnR f g must obey \(f \dashv g \). This condition is not checked.

For further information see Property.

Conn k

pattern Conn :: (a -> b) -> (b -> a) -> (a -> b) -> Conn k a b Source #

An adjoint triple of Galois connections.

An adjoint triple is a chain of connections of length 3:

\(f \dashv g \dashv h \)

When applied to a ConnL or ConnR, the two functions of type a -> b returned will be identical.

Caution: Conn f g h must obey \(f \dashv g \dashv h\). This condition is not checked.

For detailed properties see Property.

Combinators

(>>>) :: Category cat => cat a b -> cat b c -> cat a c infixr 1 #

Left-to-right composition

(<<<) :: Category cat => cat b c -> cat a b -> cat a c infixr 1 #

Right-to-left composition

mapped :: Functor f => Conn k a b -> Conn k (f a) (f b) Source #

Lift a Conn into a functor.

Caution: This function will result in an invalid connection if the functor alters the internal preorder (e.g. Down).

choice :: Conn k a b -> Conn k c d -> Conn k (Either a c) (Either b d) Source #

Lift two connections into a connection on the coproduct order

(choice id) (ab >>> cd) = (choice id) ab >>> (choice id) cd
(flip choice id) (ab >>> cd) = (flip choice id) ab >>> (flip choice id) cd

select :: Conn k c a -> Conn k c b -> Conn k c (Either a b) infixr 3 Source #

Lift two connections into a connection on the coproduct order

strong :: Conn k a b -> Conn k c d -> Conn k (a, c) (b, d) Source #

Lift two connections into a connection on the product order

(strong id) (ab >>> cd) = (strong id) ab >>> (strong id) cd
(flip strong id) (ab >>> cd) = (flip strong id) ab >>> (flip strong id) cd

divide :: Total c => Conn k a c -> Conn k b c -> Conn k (a, b) c infixr 4 Source #

Lift two connections into a connection on the product order

Accessors

upper :: Conn L a b -> b -> a Source #

Extract the upper adjoint of a ConnL.

lower :: Conn R a b -> b -> a Source #

Extract the lower adjoint of a ConnR.

inner :: Conn k a b -> b -> a Source #

Extract the upper adjoint of a ConnL, or lower adjoint of a ConnR.

When the connection is an adjoint triple the inner function is returned:

>>> inner ratf32 (1 / 8)    -- eighths are exactly representable in a float
1 % 8
>>> inner ratf32 (1 / 7)    -- sevenths are not
9586981 % 67108864

outer :: Conn k a b -> a -> (b, b) Source #

Extract the left and/or right adjoints of a connection.

When the connection is an adjoint triple the outer functions are returned:

outer c = floor c &&& ceiling c
>>> outer ratf32 (1 % 8)    -- eighths are exactly representable in a float
(0.125,0.125)
>>> outer ratf32 (1 % 7)    -- sevenths are not
(0.14285713,0.14285715)

max/min

maximize :: Conn L (a, b) c -> a -> b -> c Source #

Generalized maximum.

minimize :: Conn R (a, b) c -> a -> b -> c Source #

Generalized minimum.

median :: (forall k. Conn k (a, a) a) -> a -> a -> a -> a Source #

Birkoff's median operator.

median x x y = x
median x y z = median z x y
median x y z = median x z y
median (median x w y) w z = median x w (median y w z)
>>> median f32f32 1.0 9.0 7.0
7.0
>>> median f32f32 1.0 9.0 (0.0 / 0.0)
9.0

ceiling

ceiling :: Conn L a b -> a -> b Source #

Extract the lower half of a ConnL.

ceiling identity = id
ceiling c (x \/ y) = ceiling c x \/ ceiling c y

The latter law is the adjoint functor theorem for preorders.

>>> Data.Connection.ceiling ratf32 (0 :% 0)
NaN
>>> Data.Connection.ceiling ratf32 (13 :% 10)
1.3000001
>>> Data.Connection.ceiling f64f32 pi
3.1415927

ceiling1 :: Conn L a b -> (a -> a) -> b -> b Source #

Map over a ConnL from the left.

ceiling1 identity = id

This is the counit of the resulting comonad:

x >~ ceiling1 c id x

ceiling2 :: Conn L a b -> (a -> a -> a) -> b -> b -> b Source #

Zip over a ConnL from the left.

floor

floor :: Conn R a b -> a -> b Source #

Extract the upper half of a ConnR

floor identity = id
floor c (x /\ y) = floor c x /\ floor c y

The latter law is the adjoint functor theorem for preorders.

>>> Data.Connection.floor ratf32 (0 :% 0)
NaN
>>> Data.Connection.floor ratf32 (13 :% 10)
1.3
>>> Data.Connection.floor f64f32 pi
3.1415925

floor1 :: Conn R a b -> (a -> a) -> b -> b Source #

Map over a ConnR from the right.

floor1 identity = id

This is the unit of the resulting monad:

x <~ floor1 c id x

floor2 :: Conn R a b -> (a -> a -> a) -> b -> b -> b Source #

Zip over a ConnR from the right.

round

round :: (Num a, Preorder a) => (forall k. Conn k a b) -> a -> b Source #

Return the nearest value to x.

round identity = id

If x lies halfway between two finite values, then return the value with the smaller absolute value (i.e. round towards from zero).

See https://en.wikipedia.org/wiki/Rounding.

round1 :: (Num a, Preorder a) => (forall k. Conn k a b) -> (a -> a) -> b -> b Source #

Lift a unary function over an adjoint triple.

round1 identity = id

Results are rounded to the nearest value with ties away from 0.

round2 :: (Num a, Preorder a) => (forall k. Conn k a b) -> (a -> a -> a) -> b -> b -> b Source #

Lift a binary function over an adjoint triple.

round2 identity = id

Results are rounded to the nearest value with ties away from 0.

Example avoiding loss-of-precision:

>>> f x y = (x + y) - x
>>> maxOdd32 = 1.6777215e7
>>> f maxOdd32 2.0 :: Float
1.0
>>> round2 ratf32 f maxOdd32 2.0
2.0

truncate

truncate :: (Num a, Preorder a) => (forall k. Conn k a b) -> a -> b Source #

Truncate towards zero.

truncate identity = id

truncate1 :: (Num a, Preorder a) => (forall k. Conn k a b) -> (a -> a) -> b -> b Source #

Lift a unary function over an adjoint triple.

truncate1 identity = id

Results are truncated towards zero.

truncate2 :: (Num a, Preorder a) => (forall k. Conn k a b) -> (a -> a -> a) -> b -> b -> b Source #

Lift a binary function over an adjoint triple.

truncate2 identity = id

Results are truncated towards zero.

Connections

bounded :: Bounded a => Conn k () a Source #

The defining connections of a bounded preorder.

ordered :: Total a => Conn k (a, a) a Source #

The defining connections of a total order.

>>> outer ordered (True, False)
(False,True)

identity :: Conn k a a Source #

The identity connection.

Unsigned ints

Word8

Word16

Word32

Word64

Word

w64wxx :: Conn k Word64 Word Source #

Caution: This assumes that Word on your system is 64 bits.

Natural

Signed ints

Int8

Int16

Int32

Int64

Int

i64ixx :: Conn k Int64 Int Source #

Caution: This assumes that Int on your system is 64 bits.

sysixx :: Conn k SystemTime Int Source #

The Int is valued in seconds

Integer

Rational

Floating point

Float

Double

Fixed point

ratfix :: forall e k. HasResolution e => Conn k Rational (Extended (Fixed e)) Source #

Uni

Deci

Centi

Milli

Micro

Nano

Time

SystemTime

f32sys :: Conn L Float (Extended SystemTime) Source #

The Float is valued in seconds.

>>> Data.Connection.ceiling f32sys (0/0)
PosInf
>>> Data.Connection.ceiling f32sys pi
Finite (MkSystemTime {systemSeconds = 3, systemNanoseconds = 141592742})

f64sys :: Conn L Double (Extended SystemTime) Source #

The Double is valued in seconds.

>>> Data.Connection.ceiling f64sys (0/0)
PosInf
>>> Data.Connection.ceiling f64sys pi
Finite (MkSystemTime {systemSeconds = 3, systemNanoseconds = 141592654})

f09sys :: Conn k (Extended Nano) (Extended SystemTime) Source #

The Nano is valued in seconds (to nanosecond precision).

ratsys :: Conn k Rational (Extended SystemTime) Source #

The Rational is valued in seconds.

Extended

extended :: b -> b -> (a -> b) -> Extended a -> b Source #

Eliminate an Extended.

data Extended r #

Extended r is an extension of r with positive/negative infinity (±∞).

Constructors

NegInf

negative infinity (-∞)

Finite !r

finite value

PosInf

positive infinity (+∞)

Instances
Functor Extended 
Instance details

Defined in Data.ExtendedReal

Methods

fmap :: (a -> b) -> Extended a -> Extended b #

(<$) :: a -> Extended b -> Extended a #

Connection k Double (Extended Int32) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Double (Extended Int16) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Double (Extended Int8) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Double (Extended Word32) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Double (Extended Word16) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Double (Extended Word8) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Float (Extended Int16) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Float (Extended Int8) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Float (Extended Word16) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Float (Extended Word8) Source # 
Instance details

Defined in Data.Connection.Class

HasResolution res => Connection k Rational (Extended (Fixed res)) Source # 
Instance details

Defined in Data.Connection.Class

Methods

conn :: Conn k Rational (Extended (Fixed res)) Source #

Connection k Rational (Extended SystemTime) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Integer) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Int) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Int64) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Int32) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Int16) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Int8) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Natural) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Word) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Word64) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Word32) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Word16) Source # 
Instance details

Defined in Data.Connection.Class

Connection k Rational (Extended Word8) Source # 
Instance details

Defined in Data.Connection.Class

HasResolution res => Connection L Double (Extended (Fixed res)) Source # 
Instance details

Defined in Data.Connection.Class

Methods

conn :: Conn L Double (Extended (Fixed res)) Source #

HasResolution res => Connection L Float (Extended (Fixed res)) Source # 
Instance details

Defined in Data.Connection.Class

Methods

conn :: Conn L Float (Extended (Fixed res)) Source #

Heyting a => Algebra R (Extended a) Source # 
Instance details

Defined in Data.Lattice

Methods

algebra :: Extended a -> Conn R (Extended a) (Extended a) Source #

Join a => Semilattice L (Extended a) Source # 
Instance details

Defined in Data.Lattice

Meet a => Semilattice R (Extended a) Source # 
Instance details

Defined in Data.Lattice

Bounded (Extended r) 
Instance details

Defined in Data.ExtendedReal

Eq r => Eq (Extended r) 
Instance details

Defined in Data.ExtendedReal

Methods

(==) :: Extended r -> Extended r -> Bool #

(/=) :: Extended r -> Extended r -> Bool #

(Fractional r, Ord r) => Fractional (Extended r)

Note that Extended r is not a field, nor a ring.

Instance details

Defined in Data.ExtendedReal

Data r => Data (Extended r) 
Instance details

Defined in Data.ExtendedReal

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Extended r -> c (Extended r) #

gunfold :: (forall b r0. Data b => c (b -> r0) -> c r0) -> (forall r1. r1 -> c r1) -> Constr -> c (Extended r) #

toConstr :: Extended r -> Constr #

dataTypeOf :: Extended r -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Extended r)) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Extended r)) #

gmapT :: (forall b. Data b => b -> b) -> Extended r -> Extended r #

gmapQl :: (r0 -> r' -> r0) -> r0 -> (forall d. Data d => d -> r') -> Extended r -> r0 #

gmapQr :: (r' -> r0 -> r0) -> r0 -> (forall d. Data d => d -> r') -> Extended r -> r0 #

gmapQ :: (forall d. Data d => d -> u) -> Extended r -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Extended r -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Extended r -> m (Extended r) #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Extended r -> m (Extended r) #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Extended r -> m (Extended r) #

(Num r, Ord r) => Num (Extended r)

Note that Extended r is not a field, nor a ring.

PosInf + NegInf is left undefined as usual, but we define 0 * PosInf = 0 * NegInf = 0 by following the convention of probability or measure theory.

Instance details

Defined in Data.ExtendedReal

Ord r => Ord (Extended r) 
Instance details

Defined in Data.ExtendedReal

Methods

compare :: Extended r -> Extended r -> Ordering #

(<) :: Extended r -> Extended r -> Bool #

(<=) :: Extended r -> Extended r -> Bool #

(>) :: Extended r -> Extended r -> Bool #

(>=) :: Extended r -> Extended r -> Bool #

max :: Extended r -> Extended r -> Extended r #

min :: Extended r -> Extended r -> Extended r #

Read r => Read (Extended r) 
Instance details

Defined in Data.ExtendedReal

Show r => Show (Extended r) 
Instance details

Defined in Data.ExtendedReal

Methods

showsPrec :: Int -> Extended r -> ShowS #

show :: Extended r -> String #

showList :: [Extended r] -> ShowS #

NFData r => NFData (Extended r) 
Instance details

Defined in Data.ExtendedReal

Methods

rnf :: Extended r -> () #

Hashable r => Hashable (Extended r) 
Instance details

Defined in Data.ExtendedReal

Methods

hashWithSalt :: Int -> Extended r -> Int #

hash :: Extended r -> Int #

Preorder a => Preorder (Extended a) Source # 
Instance details

Defined in Data.Order