| Copyright | (C) 2014-2015 Edward Kmett |
|---|---|
| License | BSD-style (see the file LICENSE) |
| Maintainer | Edward Kmett <ekmett@gmail.com> |
| Stability | provisional |
| Portability | portable |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Data.Functor.Contravariant.Divisible
Description
This module supplies contravariant analogues to the
Applicative
and
Alternative
classes.
Synopsis
Contravariant Applicative
class Contravariant f => Divisible f where Source #
A
Divisible
contravariant functor is the contravariant analogue of
Applicative
.
Continuing the intuition that
Contravariant
functors consume input, a
Divisible
contravariant functor also has the ability to be composed "beside" another contravariant
functor.
Serializers provide a good example of
Divisible
contravariant functors. To begin
let's start with the type of serializers for specific types:
newtype Serializer a = Serializer { runSerializer :: a -> ByteString }
This is a contravariant functor:
instance Contravariant Serializer where contramap f s = Serializer (runSerializer s . f)
That is, given a serializer for
a
(
s :: Serializer a
), and a way to turn
b
s into
a
s (a mapping
f :: b -> a
), we have a serializer for
b
:
contramap f s :: Serializer b
.
Divisible gives us a way to combine two serializers that focus on different
parts of a structure. If we postulate the existance of two primitive
serializers -
string :: Serializer String
and
int :: Serializer Int
, we
would like to be able to combine these into a serializer for pairs of
String
s and
Int
s. How can we do this? Simply run both serializers and
combine their output!
data StringAndInt = StringAndInt String Int
stringAndInt :: Serializer StringAndInt
stringAndInt = Serializer $ \(StringAndInt s i) ->
let sBytes = runSerializer string s
iBytes = runSerializer int i
in sBytes <> iBytes
divide
is a generalization by also taking a
contramap
like function to
split any
a
into a pair. This conveniently allows you to target fields of
a record, for instance, by extracting the values under two fields and
combining them into a tuple.
To complete the example, here is how to write
stringAndInt
using a
Divisible
instance:
instance Divisible Serializer where
conquer = Serializer (const mempty)
divide toBC bSerializer cSerializer = Serializer $ \a ->
case toBC a of
(b, c) ->
let bBytes = runSerializer bSerializer b
cBytes = runSerializer cSerializer c
in bBytes <> cBytes
stringAndInt :: Serializer StringAndInt
stringAndInt =
divide (\(StringAndInt s i) -> (s, i)) string int
Methods
divide :: (a -> (b, c)) -> f b -> f c -> f a Source #
Conquer acts as an identity for combining
Divisible
functors.
Instances
Contravariant Alternative
class Divisible f => Decidable f where Source #
A
Decidable
contravariant functor is the contravariant analogue of
Alternative
.
Noting the superclass constraint that
f
must also be
Divisible
, a
Decidable
functor has the ability to "fan out" input, under the intuition that contravariant
functors consume input.
In the discussion for
Divisible
, an example was demonstrated with
Serializer
s,
that turn
a
s into
ByteString
s.
Divisible
allowed us to serialize the
product
of multiple values by concatenation. By making our
Serializer
also
Decidable
-
we now have the ability to serialize the
sum
of multiple values - for example
different constructors in an ADT.
Consider serializing arbitrary identifiers that can be either
String
s or
Int
s:
data Identifier = StringId String | IntId Int
We know we have serializers for
String
s and
Int
s, but how do we combine them
into a
Serializer
for
Identifier
? Essentially, our
Serializer
needs to
scrutinise the incoming value and choose how to serialize it:
identifier :: Serializer Identifier
identifier = Serializer $ \identifier ->
case identifier of
StringId s -> runSerializer string s
IntId i -> runSerializer int i
It is exactly this notion of choice that
Decidable
encodes. Hence if we add
an instance of
Decidable
for
Serializer
...
instance Decidable Serializer where
lose f = Serializer $ \a -> absurd (f a)
choose split l r = Serializer $ \a ->
either (runSerializer l) (runSerializer r) (split a)
Then our
identifier
Serializer
is
identifier :: Serializer Identifier identifier = choose toEither string int where toEither (StringId s) = Left s toEither (IntId i) = Right i
Instances
Mathematical definitions
Divisible
In denser jargon, a
Divisible
contravariant functor is a monoid object in the category
of presheaves from Hask to Hask, equipped with Day convolution mapping the Cartesian
product of the source to the Cartesian product of the target.
By way of contrast, an
Applicative
functor can be viewed as a monoid object in the
category of copresheaves from Hask to Hask, equipped with Day convolution mapping the
Cartesian product of the source to the Cartesian product of the target.
Given the canonical diagonal morphism:
delta a = (a,a)
should be associative with
divide
delta
conquer
as a unit
dividedeltamconquer= mdividedeltaconquerm = mdividedelta(dividedeltam n) o =dividedeltam (dividedeltan o)
With more general arguments you'll need to reassociate and project using the monoidal structure of the source category. (Here fst and snd are used in lieu of the more restricted lambda and rho, but this construction works with just a monoidal category.)
dividef mconquer=contramap(fst. f) mdividefconquerm =contramap(snd. f) mdividef (divideg m n) o =dividef' m (divideidn o) where f' a = let (bc, d) = f a; (b, c) = g bc in (b, (c, d))
A note on
conquer
The underlying theory would suggest that this should be:
conquer :: (a -> ()) -> f a
However, as we are working over a Cartesian category (Hask) and the Cartesian product, such an input
morphism is uniquely determined to be
, so we elide it.
const
mempty
Decidable
A
Divisible
contravariant functor is a monoid object in the category of presheaves
from Hask to Hask, equipped with Day convolution mapping the cartesian product of the
source to the Cartesian product of the target.
chooseLeftm (losef) = mchooseRight(losef) m = mchoosef (chooseg m n) o =choosef' m (chooseidn o) where f' =either(eitheridLeft. g) (Right.Right) . f
In addition, we expect the same kind of distributive law as is satisfied by the usual
covariant
Alternative
, w.r.t
Applicative
, which should be fully formulated and
added here at some point!