Monadic profunctors for bidirectional programming
Preface
(Updated May 2018)
This is an unfinished post consolidating ideas on monadic profunctors, that I’ve also written about in previous posts.. In particular, this post walks step by step from simple parsers and printers, to this “bidirectional” representation. Since it kept getting longer with no end in sight, I put this out there in this unfinished state. For more examples and a more up-to-date preview of this work, I am working on a few libraries.
Introduction
Programmers deal with data in various forms, and often need ways to convert back and forth between different representations. Such conversions are usually expected to follow some inverse relationship, leading to partially overlapping and redundant specifications. Multiple techniques have been investigated to exploit that redundancy in order to define mappings between two representations as a single bidirectional transformation. These programs avoid code duplication; they are more concise and more maintainable. Certain properties relating the unidirectional mappings that are extracted from these artifacts can be established by construction, lessening burden of correctness on the programmer.
Diverse languages have been created to program bidirectional transformations. A popular approach in functional programming is the design of combinator libraries, or ways to compose complex programs which inherit the good behavior of their components. Such libraries form an embedded domain specific language, and are generally simpler to implement and use than a wholly separate language.
TODO: Blabla
Unifying parsers and printers
This document is written in Literate Haskell. Familiarity with syntax in the ML family of functional languages is assumed (e.g., type annotations, pattern matching, function application), and we shall try to explain constructs which are specific to Haskell when necessary.
{-# LANGUAGE InstanceSigs #-}
module Monadic.Profunctors where
import Data.Char
import Data.Monoid
Let us first consider the problem of parsing and printing with a straightforward approach.
Types
Here are simple parser and printer types. A parser consumes a prefix of an
input string, converts it to a value of some type a
, returned alongside
the unconsumed suffix of the string. A printer simply converts a value into
a string.
data Parser a = Parser (String -> (a, String))
data Printer0 a = Printer0 (a -> String)
runParser :: Parser a -> String -> (a, String)
runParser (Parser p_) = p_
runPrinter0 :: Printer0 a -> a -> String
runPrinter0 (Printer0 q_) = q_
We would like to be able to write both a parser and a printer as a single enitity. So let us put them together in a pair, and call it an invertible parser.
data IParser0 a = IParser0 (Parser a) (Printer0 a)
asParser0 :: IParser0 a -> Parser a
asParser0 (IParser0 p _) = p
asPrinter0 :: IParser0 a -> Printer0 a
asPrinter0 (IParser0 _ q) = q
Elementary parsers
Let us define some elementary invertible parsers, to parse/print a word made of digits and to consume/print whitespace.
digits0 :: IParser0 String
digits0 = IParser0 p q
where
p = Parser $ \s -> span isDigit s
q = Printer0 $ \digits -> digits
whitespace0 :: IParser0 ()
whitespace0 = IParser0 p q
where
p = Parser $ \s -> ((), dropWhile isSpace s)
q = Printer0 $ \() -> " "
Parsers, like various other kinds of “computations”, can generally be modelled
as applicative functors or monads, concretely represented in Haskell by the
type classes Applicative
and Monad
. These abstractions provide a familiar
interface for functional programmers to compose computations.
Unfortunately, we will see that we cannot implement instances of Applicative
or Monad
for IParser0
.
However, it is still tempting to imitate these abstractions for invertible
parsers.
Functors
Parsers are functors.
The mapParser
higher-order function takes a function and applies it to the
result of a parser, producing a parser with a different output type.
mapParser :: (a -> b) -> Parser a -> Parser b
mapParser f p = Parser $ \s ->
let (a, s') = runParser p s
in (f a, s')
Functors are represented in Haskell by the Functor
type class in the standard
library base
.
class Functor m where
fmap :: (a -> b) -> m a -> m b
instance Functor Parser where
fmap = mapParser
More precisely, the Functor
type class represents covariant functors:
the input type a
(resp. result type b
) of f :: a -> b
corresponds to the
input type Parser a
(resp. result type Parser b
)
of mapParser f :: Parser a -> Parser b
.
In contrast, Printer0
is a contravariant functor.
A contravariant functor reverses the direction of the lifted arrow:
the input type a
(resp. result type b
) of f :: a -> b
corresponds to
the result type Printer0 a
(resp. input type Printer0 b
) of
mapPrinter0 f :: Printer0 b -> Printer0 a
.
mapPrinter0 :: (a -> b) -> Printer0 b -> Printer0 a
mapPrinter0 f q = Printer0 $ \a -> runPrinter0 q (f a)
Invertible parsers
To transform an IParser0
, which contains both a parser and a printer, we
thus need to map both ways.
We say that IParser0
is an invariant functor.
class Invariant m where
imap :: (a -> b) -> (b -> a) -> m a -> m b
instance Invariant IParser0 where
imap :: (a -> b) -> (b -> a) -> IParser0 a -> IParser0 b
imap f f' (IParser0 p q) = IParser0 (mapParser f p) (mapPrinter0 f' q)
Parser
and Printer0
independently turn out to also be instances,
simply ignoring one component or the other.
instance Invariant Parser where
imap f _ p = fmap f p
instance Invariant Printer0 where
imap _ f' q = mapPrinter0 f' q
Demonstration: parsing an integer
We need to wrap digit0
, which only returns a string of digits.
We may map between that string and the corresponding number using
read :: String -> Int
and show :: Int -> String
.
int0 :: IParser0 Int
int0 = imap read show digits0
Using the invertible parser:
> runParser (asParser0 int0) "42sixtimesnine"
42, "sixtimesnine")
(> runPrinter0 (asPrinter0 int0) 42
"42"
Applicative functors
Applicative functors make it possible to sequence computations and combine
their results.
Functor
is a superclass of Applicative
: every applicative functor is
a (covariant) functor.
class Functor m => Applicative m where
pure :: a -> m a
<*>) :: m (a -> b) -> m a -> m b (
Our Parser
is an instance of Applicative
.
pure
creates a parser that does nothing beyond producing a constant value.
The binary operator (<*>)
(“ap”) runs a parser producing a function f
,
followed by another producing a value a
, and returns the application
f a
.
instance Applicative Parser where
pure a = Parser $ \s -> (a, s)
-- "ap"
pf <*> pa = Parser $ \s ->
let (f, s') = runParser pf s
a, s'') = runParser pa s'
(in (f a, s'')
However, Printer0
is not an applicative functor, since it is not even a
covariant functor, but a contravariant one.
Furthermore, even if we ignore the superclass constraint, a printer
qf <*> qa :: Printer0 b
would need to print a value (of type) b
using
printers qf :: Printer0 (a -> b)
and qa :: Printer0 a
, but there is no
general way to extract a function a -> b
and a value a
out of a value
b
.
Monoidal functors
We can still apply the idea of sequencing operations to printers with a different type class:
class Invariant m => Monoidal m where
pure' :: a -> m a
-- "pair"
<.>) :: m a -> m b -> m (a, b) (
A pure printer just prints the empty string (essentially doing nothing).
Given two printers qa :: Printer0 a
and qb :: Printer0 b
, we can construct
a printer for pairs of values qa <.> qb :: Printer0 (a, b)
, by
concatenating their printing results.
Thus Printer0
is a monoidal functor.
instance Monoidal Printer0 where
pure' :: a -> Printer0 a
pure' _ = Printer0 $ \_ -> ""
<.>) :: Printer0 a -> Printer0 b -> Printer0 (a, b)
(qa <.> qb = Printer0 $ \(a, b) ->
runPrinter0 qa a ++
runPrinter0 qb b
Assuming that a type is a covariant Functor
(e.g., Parser
), then (<*>)
and (<.>)
(“pair”) are equivalent, in the sense that we can implement one
with the other.
Below, (<$>)
is an infix synonym for Functor
’s
fmap
, quite frequent when programming in applicative style.
(,)
is the constructor of pairs used as a regular identifier.
<.>*) :: Applicative m => m a -> m b -> m (a, b)
(ma <.>* mb = (,) <$> ma <*> mb
<*>.) :: (Functor m, Monoidal m) => m (a -> b) -> m a -> m b
(ma <*>. mb = (\(f, a) -> f a) <$> (ma <.> mb)
-- f <$> a = fmap f a
-- f <$> a <*> b = (f <$> a) <*> b -- Associates like that
-- (,) a b = (a, b)
Given two parsers pa :: Parser a
and pb :: Parser b
, we can construct
a parser pa <.>* pb :: Parser (a, b)
which runs both parsers successively
and collects their results in a pair.
Thus Parser
is a Monoidal
functor.
instance Monoidal Parser where
pure' :: a -> Parser a
pure' = pure
<.>) :: Parser a -> Parser b -> Parser (a, b)
(<.>) = (<.>*) (
Invertible parsers
IParser0
is the product of two monoidal functors, which is monoidal as well.
instance Monoidal IParser0 where
pure' :: a -> IParser0 a
pure' a = IParser0 (pure' a) (pure' a)
<.>) :: IParser0 a -> IParser0 b -> IParser0 (a, b)
(IParser0 pa qa) <.> (IParser0 pb qb) = IParser0 (pa <.> pb) (qa <.> qb) (
Demonstration: parsing a pair
Here is an invertible parser of a pair of numbers separated by whitespace.
We define the (.>)
(“then”) combinator which ignores the unit result of
its first operand, using imap
to restructure the tuple produced by
(<.>)
.
It is similar to (*>) :: Applicative m => m a -> m b -> m b
from the
standard library. The restriction that the left argument returns a unit result
is necessary to avoid loss of information.
-- "then"
.>) :: Monoidal m => m () -> m a -> m a
(mu .> ma = imap f f' (mu <.> ma)
where
f ((), m) = m
f' m = ((), m)
pairInt0 :: IParser0 (Int, Int)
pairInt0 = int0 <.> (whitespace0 .> int0)
Using the invertible parser:
> runParser (asParser0 pairInt0) "2048 2187"
2048, 2187), "")
((> runPrinter0 (asPrinter0 pairInt0) (2048, 2187)
"2048 2187"
Monads
Applicative
or Monoidal
sequence independent operations, thus their
expressiveness remains quite limited.
A generic kind of format we cannot parse with those is one where the input is
separated into a header and a body, with the header containing information
about the shape of the body.
For instance, consider strings that start with an integer n
(the header),
followed by n
more integers (the body).
For such a format, we need a monadic parser, and Parser
is indeed a Monad
.
That means that it exposes the following operation: (>>=)
(“bind”) runs the
first parser, and passes the result to the second parameterized parser before
running it.
class Applicative m => Monad m where
-- "bind"
>>=) :: m a -> (a -> m b) -> m b (
instance Monad Parser where
>>=) :: Parser a -> (a -> Parser b) -> Parser b
(pa >>= topb = Parser $ \s ->
let (a, s') = runParser pa s
in runParser (topb a) s'
Extending the header/body analogy, we can see that (>>=)
also
does not fit printers. If qa :: Printer0 a
is the printer of headers a
,
and toqb :: a -> Printer0 b
is the printer of bodies b
parameterized
by headers, their composition needs to accept a type containing
the header, whereas (>>=)
simply forgets the type of the header a
in
the result.
We can join the results of two computations in a pair,
similarly to the way we reshaped Applicative
into Monoidal
.
class Monoidal m => Monadoidal m where
-- "pairing bind"
>>+) :: m a -> (a -> m b) -> m (a, b) (
Every Monad
instance, including Parser
,
can be an instance of Monadoidal
.
>>+=) :: Monad m => m a -> (a -> m b) -> m (a, b)
(ma >>+= tomb = ma >>= \a -> tomb a >>= \b -> pure (a, b)
instance Monadoidal Parser where
>>+) :: Parser a -> (a -> Parser b) -> Parser (a, b)
(>>+) = (>>+=) (
A Printer0
is an instance of Monadoidal
.
instance Monadoidal Printer0 where
>>+) :: Printer0 a -> (a -> Printer0 b) -> Printer0 (a, b)
(qa >>+ toqb = Printer0 $ \(a, b) ->
runPrinter0 qa a ++
runPrinter0 (toqb a) b
Thus, so is IParser0
.
instance Monadoidal IParser0 where
>>+) :: IParser0 a -> (a -> IParser0 b) -> IParser0 (a, b)
(pqa >>+ topqb = IParser0 p q
where
p = asParser0 pqa >>+ (asParser0 . topqb)
q = asPrinter0 pqa >>+ (asPrinter0 . topqb)
Demonstration: parsing a list
Here is an invertible parser of a list of integers, written as the length n
followed by n
integers.
Given the length, we can iterate a parser with the replicate0
combinator
defined here.
replicate0 :: Monadoidal m => Int -> m a -> m [a]
replicate0 0 _ = pure' []
replicate0 n pq = imap cons uncons (pq <.> replicate0 (n - 1) pq)
where
cons (a, as) = a : as
uncons (a : as) = (a, as)
uncons [] = error "Unexpected empty list"
intList0 :: IParser0 [Int]
intList0 = imap f f' (int0 >>+ \n -> replicate0 n (whitespace0 .> int0))
where
f (_, xs) = xs
f' xs = (length xs, xs)
Using the invertible parser:
> runParser (asParser0 intList0) "3 0 1 2 "
0, 1, 2], " ")
([> runPrinter0 (asPrinter0 intList0) [0, 1, 2]
"3 0 1 2"
The approach outlined above leads to a type class hierarchy
Invariant
/Monoidal
/Monadoidal
which parallels a
well-established one Functor
/Applicative
/Monad
.
TODO: drawbacks? Tuples.
Invertible parsing as a profunctor
We study a different construction of invertible parsers, which is
actually an instance of Functor
/Applicative
/Monad
.
Recall the previously defined type of invertible parsers:
data IParser0 a = IParser0 (Parser a) (Printer0 a)
It is not an instance of Functor
(thus neither of Applicative
nor
Monad
) due to Printer0 a
being contravariant with respect to a
.
Let us reflect this difference in variance by generalizing the invertible
parser type, with a parameter x
in negative occurences, and a
in
positive occurences:
TODO: explain negative/positive. Basically contravariant/covariant.
data IParser1 x a = IParser1 (Parser a) (Printer0 x)
asParser1 :: IParser1 x a -> Parser a
asParser1 (IParser1 p _) = p
asPrinter1 :: IParser1 x a -> Printer0 x
asPrinter1 (IParser1 _ q) = q
IParser0 a
is equivalent to IParser1 a a
.
type IParser1' a = IParser1 a a
iparser0to1 :: IParser0 a -> IParser1' a
iparser0to1 (IParser0 p q) = IParser1 p q
Let us translate the elementary parsers digits0
and whitespace0
.
The following sections will demonstrate a different way to compose them.
digits1 :: IParser1' String
digits1 = iparser0to1 digits0
whitespace1 :: IParser1' ()
whitespace1 = iparser0to1 whitespace0
Profunctors
We can map over each parameter independently, the first “contravariantly”, the second “covariantly”. We call such a type a profunctor.
class Profunctor f where
lmap :: (x -> y) -> f y a -> f x a
rmap :: (a -> b) -> f x a -> f x b
instance Profunctor IParser1 where
lmap g (IParser1 p q) = IParser1 p (mapPrinter0 g q)
rmap f (IParser1 p q) = IParser1 (mapParser f p) q
Applying two functions at once results in a function equivalent to imap
(up
to the order of arguments), but with a much more general type:
dimap :: Profunctor f => (x -> y) -> (a -> b) -> f y a -> f x b
dimap g f = lmap g . rmap f
Demonstration
We can now define int1
from digits1
, equivalent to int0
.
int1 :: IParser1' Int
int1 = dimap show read digits1
Profunctors are functors
A profunctor is a covariant functor with respect to its second argument:
instance Functor (IParser1 x) where
fmap = rmap
Applicative functors and monoids
Invertible parsers can also be sequenced via an Applicative
instance.
Parser
is already an instance of Applicative
. Printer0
is not an instance of Applicative
, but we only need it to be a Monoid
.
Printer0 x
, equivalent to the type of functions x -> String
, is a monoid
where the binary operation is the pointwise concatenation of strings.
instance Monoid (Printer0 x) where
-- Identity element
mempty :: Printer0 x
mempty = Printer0 $ \_ -> ""
-- Associative operation
mappend :: Printer0 x -> Printer0 x -> Printer0 x
mappend p p' = Printer0 $ \x ->
runPrinter0 p x ++
runPrinter0 p' x
The binary operation of that monoid seems to be the only reasonable1
implementation of the printer component of (<*>)
for IParser1
, given its
type.
instance Applicative (IParser1 x) where
pure a = IParser1 (pure a) mempty
<*>) :: IParser1 x (a -> b) -> IParser1 x a -> IParser1 x b
(pqf <*> pqa = IParser1 pb qb
where
pb = asParser1 pqf <*> asParser1 pqa
qb = asPrinter1 pqf <> asPrinter1 pqa
-- (<>) = mappend
Partial printers
The type of the binary operation
(<>) :: Printer0 x -> Printer0 x -> Printer0 x
seems surprising at first: what
use is printing the same value of type x
twice?
The answer is that a Printer0 x
does not necessarily print a complete
representation of x
.
It may be a partial printer of x
.
For instance, given a printer q :: Printer0 x
, we can construct
(mapPrinter0 fst q) :: Printer0 (x, y)
printing only the first component of a given pair.
We can similarly obtain a printer for the second component, and finally
combine them.
pairPrinter0 :: Printer0 x -> Printer0 y -> Printer0 (x, y)
pairPrinter0 qx qy = mapPrinter0 fst qx <> mapPrinter0 snd qy
Applicative style sequences parsers concisely, allowing users to provide their own functions to combine results. Here they are simply put in a pair.
pairParser :: Parser a -> Parser b -> Parser (a, b)
pairParser pa pb = (,) <$> pa <*> pb
Note that pairParser
and pairPrinter0
are equal to (<.>)
. The point
here is that Monoidal
simply turns out to be a composition of more
elementary abstractions. We already mentioned that Monoidal
and
Applicative
are equivalent for types which are covariant functors (e.g.,
Parser
).
Above, pairPrinter0
shows that a type which is both a contravariant functor
and a monoid is also a monoidal functor (the identity morphism pure'
is
equal to \_ -> mempty
).
Below, pair
combines these implications, applying lmap
(renamed as the infix
operator (=.)
for a record-like notation) to obtain two values
fst =. pqa) :: f (x, y) a
(snd =. pqb) :: f (x, y) b (
under the same context f (x, y)
which can then be combined with the
applicative product (<*>)
, using the products of parsers (Applicative
)
and printers (Monoid
) when f ~ IParser1
.
=.) :: Profunctor f => (x -> y) -> f y a -> f x a
(=.) = lmap
(
-- Very general type
pair
:: (Profunctor f, Applicative (f (x, y)))
=> f x a -> f y b -> f (x, y) (a, b)
pair pqa pqb =
(,)<$> (fst =. pqa)
<*> (snd =. pqb)
-- Specializes to a (<.>)-looking type
pair1 :: IParser1' a -> IParser1' b -> IParser1' (a, b)
-- Expanded type
pair1 :: IParser1 a a -> IParser1 b b -> IParser1 (a, b) (a, b)
Applicative functors are in fact a generalization of monoids.
Indeed, the Const
type (constant type function) turns monoids into
applicative functors.
data Const w a = Const w
instance Functor (Const w) where
fmap _ (Const w) = Const w
instance Monoid w => Applicative (Const w) where
pure _ = Const mempty
Const w <*> Const w' = Const (w <> w')
Thus, IParser1 x _
is not an applicative functor by any fortuitous accident,
but because it is actually the product of two applicative
functors (Parser _
and Const (Printer0 x) _
, or perhaps
x -> Const String _
).
Demonstration
We no longer need a new (.>)
operator, we can now reuse Applicative
’s
(*>)
.
With (=.)
(i.e., lmap
), we apply the unit
function to the
whitespace1
invertible parser, indicating that it produces/requires no
information.
unit :: x -> ()
unit _ = ()
pairInt1 :: IParser1' (Int, Int)
pairInt1 =
(,)<$> (fst =. int1)
<*> (snd =.
unit =. whitespace1) *> int1)) ((
A monadic printer
Printer0 x
is not a monad, we shall replace it with a type which is one.
Recall that Const
creates an applicative functor out of a monoid,
but since its second type parameter is ignored, there is no way to
implement a monadic “bind” operator (>>=)
.
The writer monad
The writer monad arises out of any monoid. Values are annotated
with a log, an element of some monoid w
. The Monoid
structure
provides an empty log for pure values, and an operation to append logs
when combining values with (<*>)
or (>>=)
.
data Writer w a = Writer w a
-- The embedding must now have a restricted type,
-- as opposed to Const :: w -> Const w a.
write :: w -> Writer w ()
write w = Writer w ()
runWriter :: Writer w a -> w
runWriter (Writer w _) = w
instance Functor (Writer w) where
fmap f (Writer w a) = Writer w (f a)
instance Monoid w => Applicative (Writer w) where
pure a = Writer mempty a
Writer wf f <*> Writer wa a = Writer (wf <> wa) (f a)
instance Monoid w => Monad (Writer w) where
Writer wa a >>= toWb =
let Writer wb b = toWb a
in Writer (wa <> wb) b
The new printer
The original Printer0
can also be seen as the composition of the reader
(x -> _
) and the constant (Const String _
) functors: for any a
,
Printer0 x a
is equivalent to x -> Const String a
.
The new Printer
owes its instances of Functor
/Applicative
/Monad
to its being the composition of reader (x -> _
) and writer
(Writer String _
).
data Printer x a = Printer (x -> Writer String a)
runPrinter :: Printer x a -> x -> String
-- Instances in the appendix:
-- Profunctor, Functor, Applicative, Monad.
Our final version IParser
of invertible parsers is: a parser of a
and a
printer of a
contained in x
.
More precisely, as a printer, it accepts an argument x
, from which it
extracts a value a
, prints it, and returns it (so that it can be used
with (>>=)
).
An IParser x a
is the product of two monads, and therefore it is a monad.
data IParser x a = IParser (Parser a) (Printer x a)
asParser :: IParser x a -> Parser a
asPrinter :: IParser x a -> Printer x a
-- Instances in the appendix:
-- Profunctor, Functor, Applicative, Monad.
type IParser' a = IParser a a
Since whitespace1
is always going to be used as (unit =. whitespace1)
,
we might as well include that in its translation to whitespace
.
Parametricity tells us from just its type that whitespace
uses no
information from the input x
so it might as well be ()
, but
polymorphism makes it more convenient to use.
iparser1to_ :: IParser1' a -> IParser' a
iparser1to_ (IParser1 p q) = IParser p q'
where
q' = Printer $ \a -> Writer (runPrinter0 q a) a
int :: IParser' Int
int = iparser1to_ int1
whitespace :: IParser x ()
whitespace = (unit =. iparser1to_ whitespace1)
Demonstration
Let us write again an invertible parser of lists.
We still need a special replicate1
function.
(:)
is the constructor of lists used as a regular identifier.
In contrast with IParser0
functions such as replicate0
,
we no longer need to construct/deconstruct intermediate tuples,
instead we can use normal constructors and accessors straightforwardly.
replicate1
:: (Profunctor f, Applicative (f [x]))
=> Int -> f x a -> f [x] [a]
replicate1 0 _ = pure []
replicate1 n pq =
:)
(<$> (head =. pq)
<*> (tail =. replicate1 (n - 1) pq)
-- Specializes to
replicate1 :: Int -> IParser' a -> IParser' [a]
Since IParser'
is an instance of Monad
, we can use Haskell’s do-notation,
which desugars to expressions using (>>=)
.
intList1 :: IParser' [Int]
intList1 = do
n <- length =. int
replicate1 n (whitespace *> int)
A type class based interface
In the examples above, the only components specific to the application of parsing and printing are the “elementary” actions. They are then composed using polymorphic combinators.
These combinators require constraints involving general type classes:
Profunctor
, Applicative
and Monad
.
The latter two are well-known interfaces against which functional programmers
compose many sorts of computations.
We have shown that, contrary to what the initial approach suggested, invertible
parsers can also implement these type classes.
The abstractness of these constraints suggests that we can use these combinators to create bidirectional transformations other than parsers/printers.
From functor to profunctor
In fact, we have here a generalization of the
Functor
/Applicative
/Monad
hierarchy for “unidirectional”
computations.
Indeed, every instance m
of Functor
can be lifted to a Profunctor
by adding a phantom type parameter:
data Pro m x a = Pro (m a)
unPro :: Pro m x a -> m a
unPro (Pro ma) = ma
instance Functor m => Profunctor (Pro m) where
lmap _ (Pro ma) = Pro ma
rmap f (Pro ma) = Pro (fmap f ma)
And Functor
/Applicative
/Monad
instances are simply inherited:
instance Functor m => Functor (Pro m x) where
fmap = rmap
instance Applicative m => Applicative (Pro m x) where
pure a = Pro (pure a)
Pro mf <*> Pro ma = Pro (mf <*> ma)
instance Monad m => Monad (Pro m x) where
Pro ma >>= toprob = Pro (ma >>= (unPro . toprob))
We can recognize that construction to be equivalent to the parser component of
the IParser
type above.
Similarly, if we focus on the printer component, we obtain another
general way to turn a functor into a profunctor.
-- As it's named by the profunctors package.
data Star n x a = Star (x -> n a)
unStar :: Star n x a -> x -> n a
unStar (Star q) = q
instance Functor n => Profunctor (Star n) where
lmap g (Star q) = Star (q . g)
rmap f (Star q) = Star (fmap f . q)
instance Functor n => Functor (Star n x) where
fmap = rmap
instance Applicative n => Applicative (Star n x) where
pure a = Star (\_ -> pure a)
Star qf <*> Star qa = Star (\x -> qf x <*> qa x)
instance Monad n => Monad (Star n x) where
Star qa >>= tostarb = Star (\x -> qa x >>= \a -> unStar (tostarb a) x)
Thus IParser
consists of the product of Pro
and Star
,
respectively specialized to the Parser
and Writer w
monads.
Programming lenses
A lens is a bidirectional transformation from a source s
,
which can “focus” on a fragment called view v
, using a function
get' :: s -> v
, and reflect an update of the view into the source:
put' :: s -> v -> s
.
data Lens' s v = Lens'
get' :: s -> v
{ put' :: v -> s -> s
, }
Given two lenses lb :: Lens' a b
and lc :: Lens' b c
, we can obtain a
Lens' a c
:
to define get'
, from a
, we can get b
using the lens lb
, and
then get c
using lc
;
to define set'
, an updated c
can be put back into b
using lc
,
and the result again put back into a
using lb
.
In fact, lenses are the morphisms of a category of types.
idLens' :: Lens' a a
idLens' = Lens' (\a -> a) (\_ a -> a)
composeLens' :: Lens' a b -> Lens' b c -> Lens' a c
composeLens' lb lc = Lens'
get' = get' lc . get' lb
{ put' = \c a ->
, let b = get' lb a
in put' lb (put' lc c b) a
}
This composition is great to access nested structures.
A more interesting way for us to compose lenses is to access two values in
parallel from the same source.
The resulting operator corresponds to Monoidal
’s (<.>)
.
<.>~) :: Lens' s a -> Lens' s b -> Lens' s (a, b)
(la <.>~ lb = Lens'
get' = \s -> (get' la s, get' lb s)
{ put' = \(a, b) s -> put' lb b (put' la a s)
, }
Like invertible parsers, we can generalize the lens type in order to create an
instance of Applicative
and Monad
.
First, we may split the invariant parameter v
into a contravariant x
and a covariant a
.
data Lens0 s x a = Lens0
get0 :: s -> a
{ put0 :: x -> s -> s
, }
We can recognize that s -> _
is a monad (which can be lifted with Pro
),
and that x -> s -> s
is of the form x -> w
where w ~ (s -> s)
is
the monoid of endofunctions. The type of put0
is equivalent to
x -> Const w a
, and we can transform it as we did for Printer
to x -> Writer w a
, or equivalently, Star (Writer (s -> s)) x a
.
data Lens s x a = Lens
get :: s -> a
{ put :: x -> (s -> s, a)
,
}
instance Profunctor (Lens s) where
lmap g (Lens get put) = Lens get (put . g)
rmap f (Lens get put) = Lens (f . get) ((fmap . fmap) f put)
instance Functor (Lens s x) where
fmap = rmap
instance Applicative (Lens s x) where
pure a = Lens (\_ -> a) (\_ -> (id, a))
lf <*> la = Lens
get = \s -> get lf s (get la s)
{ put = \x ->
, let (r , f) = put lf x
r', a) = put la x
(in (r' . r, f a)
}
instance Monad (Lens s x) where
la >>= f = Lens
get = \s -> get (f (get la s)) s
{ put = \x ->
, let (r , a) = put la x
r', b) = put (f a) x
(in (r' . r, b)
}
composeLens :: Lens s t t -> Lens t x a -> Lens s x a
composeLens lt la = Lens
get = get la . get lt
{ put = \x ->
, let (f, a) = put la x
put' s = let (g, _) = put lt (f (get lt s)) in g s
in (put', a)
}
Demonstration: a lens to the spine of a tree
Consider a type of trees with values at every node.
data Tree a
= Leaf
| Node a (Tree a) (Tree a)
Start with crude lenses to get and put values at nodes, and to access the children of a node.
node :: Lens (Tree a) (Maybe a) (Maybe a)
node = Lens get put
where
get Leaf = Nothing
get (Node a _ _) = Just a
put Nothing = (\_ -> Leaf, Nothing)
put (Just a) = (put', Just a)
where
put' Leaf = Node a Leaf Leaf
put' (Node _ l r) = Node a l r
rightChild :: Lens (Tree a) (Tree a) (Tree a)
rightChild = Lens
get = \(Node _ _ r) -> r
{ put = \r -> (\(Node a l _) -> Node a l r, r)
,
}
maybeHead :: [a] -> Maybe a
maybeHead (a : _) = Just a
maybeHead [] = Nothing
Then we can compose them to obtain the elements in the right spine of the tree. In the put direction, fine grained structural modifications are possible and allow to match the lengths of an input list and the spine of the updated tree.
spine :: Eq a => Lens (Tree a) [a] [a]
spine = do
m <- maybeHead =. node
case m of
Nothing -> pure []
Just a -> do
as <- tail =. (composeLens rightChild spine)
pure (a : as)
- Higher constraints: ForallF Applicative f
- Codec
- Generable sets
- More combinators
Appendix
Printer
instances
-- :: Printer x a -> x -> String
runPrinter q x = runWriter (runPrinter' q x)
runPrinter' :: Printer x a -> x -> Writer String a
runPrinter' (Printer q_) = q_
instance Profunctor Printer where
lmap g (Printer q_) = Printer (q_ . g)
rmap = fmap
instance Functor (Printer x) where
fmap f (Printer q_) = Printer $ \x ->
fmap f (q_ x)
instance Applicative (Printer x) where
pure a = Printer $ \_ -> pure a
Printer qf_ <*> Printer qa_ = Printer $ \x ->
qf_ x <*> qa_ x
instance Monad (Printer x) where
Printer qa_ >>= toqb = Printer $ \x ->
let toWb a = runPrinter' (toqb a) x
in qa_ x >>= toWb
IParser
instances
asParser (IParser p _) = p
asPrinter (IParser _ q) = q
instance Profunctor IParser where
lmap g (IParser p q) = IParser p (lmap g q)
rmap = fmap
instance Functor (IParser x) where
fmap f (IParser p q) = IParser (fmap f p) (fmap f q)
instance Applicative (IParser x) where
pure a = IParser (pure a) (pure a)
pqf <*> pqa = IParser pb qb
where
pb = asParser pqf <*> asParser pqa
qb = asPrinter pqf <*> asPrinter pqa
instance Monad (IParser x) where
pqa >>= topqb = IParser pb qb
where
pb = asParser pqa >>= (asParser . topqb)
qb = asPrinter pqa >>= (asPrinter . topqb)
Non reasonable implementations include ignoring the printer in one of the operands and doing nonsensical combinations of strings instead of a simple concatenation.↩︎