### 9 releases (4 breaking)

Uses old Rust 2015

0.5.2 | Jan 11, 2016 |
---|---|

0.5.1 | Aug 13, 2015 |

0.4.1 | Aug 11, 2015 |

0.3.1 | Aug 8, 2015 |

0.1.0 | Aug 7, 2015 |

**52** downloads per month

**MIT/Apache**

8KB

82 lines

# rust-coyoneda

Functor composition via the Co-Yoneda Lemma

## License

Licensed under either of

- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

### Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

###
`lib.rs`

:

# Functor composition via the Co-Yoneda Lemma

## Functors in Rust

Let's implement functors in Rust!

Working around the lack of higher-kinded types, our trait for a functor will look something like this:

`pub` `trait` `Param` `{` `type` `Param``;` `}`
`pub` `trait` `ReParam`<B>: Param `{` `type` `Output``:` `Param``<`Param=B`>``;` `}`
`pub` `trait` `Functor`<'a, B>: ReParam<B> `{`
`fn` `fmap``<`F`:` `Fn``(``Self``::`Param`)` `->` B `+` `'a``>``(``self`, F`)`` ``->` `Self``::`Output`;`
`}`

This works great as long as we write functions that take specific
types which are functors, but it is not possible to write a function
operating on a generic functor type and using

more than once.
For example, the following will not compile:`fmap`

`fn` `add_and_to_string``<``'a`, F`>``(``x``:` F`)`` ``->` `<`F `as` ReParam`<``String``>``>``::`Output
`where` F`:` `Param``<`Param=`i32``>` + `Functor``<``'a`, `i32``>` + `Functor``<``'a`, `String``>` `{`
x`.``fmap``(``|``n``:` `i32``|` `n ``+` `1``)`
`.``fmap``(``|``n``:` `i32``|` `n``.``to_string``(``)``)`
`}`

While functors in general can be encoded to some extend
in Rust's trait system, what we can't encode for a lack of higher-kinded
types, is the fact that a functor

maps a function between `Box`

and `A`

to a function between `B`

and `Box``<`A`>`

, not between `Box``<`B`>`

and `Box``<`A`>`

.`Option``<`B`>`

Especially when looking at functor composition, it is useful to
be able to encode this fact, because it allows us to chain
multiple calls to

, knowing that the result is also a functor,
and can be `fmap`

'ed further.`fmap`

## The Co-Yoneda Lemma

Let's define a data type called

:`Coyoneda`

`pub` `struct` `Coyoneda``<``'a`, T`:` Param, B`>`` ``{`
`point``:` T,
`morph``:` Fn`(``T``::`Param`)` -> B + `'a`
`}`

This datatype is a functor, which uses function composition
to accumulate the mapping function, without changing the captured

. The implementation for `T`

is trivial:`Functor`

`impl``<``'a`, T`:` Param, B, C`>`` ``Functor``<``'a`, C`>` `for`` ``Coyoneda``<``'a`, T, B`>` `{`
`type` `Output` `=` `Coyoneda``<``'a`, T, C`>``;`
`fn` `fmap``<`F`:` `Fn``(`B`)` `->` C `+` `'a``>``(``self`, `f``:` F`)`` ``->` `Coyoneda``<``'a`, T, C`>` `{`
`let` g `=` `self``.`morph`;`
Coyoneda`{`point`:` `self``.`point`,` morph`:` `move` `|`x`|` `f``(``g``(`x`)``)``}`
`}`
`}`

The co-yoneda lemma states that for a covariant functor

,
this `f`

is naturally isomorphic to `Coyoneda f`

.
Practically speaking, this means that we can lift any `f`

into a `f a`

,
and given a function `Coyoneda f a`

, we can retrieve back a `(`a `->` b`)` `->` f b

from a `f b`

.`Coyoneda f b`

## Composing Coyoneda

Now here's the catch: Since we have a parameterized datatype that is isomorphic to any functor, we can lift functors into Coyoneda to compose them safely within Rust's type system!

For example, let's implement a function that is generic for any functor,
by operating on our

type:`Coyoneda`

`fn` `add_and_to_string``<`T`:` Param`>``(``y``:` `Coyoneda``<`T, `i32``>``)`` ``->` `Coyoneda``<`T, `String``>` `{`
y`.``fmap``(``|``n``:` `i32``|` `n ``+` `1``)`
`.``fmap``(``|``n``:` `i32``|` `n``.``to_string``(``)``)`
`}`

Given we implemented a functor for

, we can now do the following:`Option`

`let` y `=` `add_and_to_string``(``From``::`from`(``Some``(``42``)``)``)``;`
`assert_eq!``(`y`.``unwrap``(``)``,` `Some``(``"`43`"``.``to_string``(``)``)``)`

... or for

:`Box`

`let` y `=` `add_and_to_string``(``From``::`from`(``Box``::`new`(``42``)``)``)``;`
`assert_eq!``(`y`.``unwrap``(``)``,` `Box``::`new`(``"`43`"``.``to_string``(``)``)``)`

... and for every other functor as well. Yay!

#### Dependencies

~18KB