Fsharpplus: Add Invariant Abstraction

[jhbertra]

Description

Add support for an abstraction that combines a Functor and a Contravariant in a way similar to a Profunctor, but where the output parameter is constrained to the input parameter.

From Haskell:

class Invariant f where
  invmap :: (a -> b) -> (b -> a) -> f a -> f b

This is a useful abstraction when dealing with bidirectional programming, for example:

type Decoder<'a> = (string -> Result<'a, string>)
type Encoder<'a> = ('a -> string)
type Codec<'a> =
  { decoder : Decoder<'a>
    encoder : Encoder<'a> }

type Decoder<'a> with
    static member Map(d : Decoder<'a>, f : 'a -> 'b) : Decoder<'b> = map f << d

type Encoder<'a> with
    static member Contramap(e : Encoder<'a>, f : 'b -> 'a) : Decoder<'b> = f >> e

type Codec<'a> with
    static member Invmap({ decoder = d; encoder = e } : Codec<'a>, f : 'a -> 'b, g : 'b -> 'a) : Codec<'b> =
        { decoder = map f d
          encoder = contramap g e }

A similar related abstraction is an Invariant2, a sort of Bifunctor analog of Invariant

class Invariant2 f where
  invmap2 :: (a -> c) -> (c -> a) -> (b -> d) -> (d -> b) -> f a b -> f c d

Which has a similar application, except that it allows the definition of types like Codec<'a, 'b>, where the encoded type is parametric in addition to the decoded type.

If you like the suggested additions, I would be happy to submit a PR with these abstractions added.

[gusty]

Thanks for the proposal, a PR is always welcome, however I don't think we'll be able to include it in 1.0 since it's a bit late already.

But we can consider it for v 1.next as AFAIK it wouldn't be a breaking change.

Now if you ask me, I'm still struggling to understand the real world use case for it, so if you can add a concrete example, for instance with the codec you described, it will help me to understand its value out of Kmett's HAST post (from what I read, most ,if not all, instances would be trivial by using the Const functor).

You could argue that the same applies for Arrows and Comonads, and I would say you're right, we don't have currently good sample use for those ones.

Having said that, if you want to proceed with a PR I can help you fight the type inference in order to get it right, my first advice would be to use the current Contravariant code as a template.

[jhbertra]

I know what you mean when you say it's hard to immediately see the real-world value of these abstractions. I find this is often the case with functional abstractions, until you actually encounter a situation where they're useful.

I have encountered a situation recently in one of my personal projects Data Blocks where this abstraction would be useful.

It is a more specific example of the sample code I gave above:

type JsonDecoder<'a> = JsonDecoder of (Json-> Result<'a, string>)
type JsonEncoder<'a> = JsonEncoder of ('a -> Json)
type JsonCodec<'a> =
  { decoder : JsonDecoder<'a>
    encoder : JsonEncoder<'a> }

The basis of the API is that for every operation you define for the JsonDecoder, there should be a corresponding operation defined for the JsonEncoder. e.g.:

let stringDecoder = JsonDecoder (function JsString s -> Ok s | _ -> Error "Expected a string value")
let stringEncoder = JsonEncoder JsString

let boolDecoder = JsonDecoder (function JsBool b -> Ok b | _ -> Error "Expected a boolean value")
let boolEncoder = JsonEncoder JsBool

let mapDecoder f (JsonDecoder d) = JsonDecoder (f << d)
let contramapDecoder f (JsonEncoder e) = JsonEncoder (f >> e)

given that the two sets of APIs are opposites, this allows a single codec API to be written that combines these:

let string = { decoder = stringDecoder; encoder = stringEncoder }
let bool = { decoder = boolDecoder; encoder = boolEncoder }
let invmap f g codec = 
  { decoder = mapDecoder f codec.decoder
    encoder = contramapEncoder g codec.encoder }

invmap is therefore required by the API, because it's the only way to combine a functor and a contravariant functor into a single unit that still allows mapping over the type parameter.

As a result of this, you only need to specify your JSON schema one time, when creating the codec:

// assume: val contact : Name -> string -> string option -> Contact

// Instead of
let contactDecoder : JsonDecoder<Contact> =
    contact
    <!> requiredDecoder "name" (stringDecoder |> mapDecoder Name)
    <*> requiredDecoder "email" stringDecoder
    <*> optionalDecoder "phone" stringDecoder

let contactEncoder : JsonEncoder<Contact> =
    object
    |> propertyEncoder "name" (fun c -> c.name) (stringEncoder |> contramapEncoder (fun Name n -> n))
    |> propertyEncoder "email" (fun c -> c.email) stringEncoder
    |> propertyEncoder "phone" (fun c -> c.phone) (nullableEncoder stringEncoder)

let contactDecoded = runDecoderString contactDecoder "''{"name":"John Doe", "email":"[email protected]"}"''
let json = runEncoderString contactEncoder contactDecoded


// We can do:
let contactCodec : JsonCodec<Contact> =
    contact
    |> ``{``
    |> required "name" (fun x -> x.name) (string |> invmap Name (fun Name n -> n))
    |> required "email" (fun x -> x.name) string
    |> optional "phone" (fun x -> x.name) string
    |> ``}``

let contactDecoded = decodeString contactCodec "''{"name":"John Doe", "email":"[email protected]"}"''
let json = encodeString contactCodec contactDecoded

[gusty]

Lovely !!!

I really like the example you wrote, I wish we had more sample code and docs like that.
Also had a look at your project, looks interesting, are you porting an existing Haskell project?

Please go ahead with a PR, it seems to be a nice addition and don't hesitate to contact me if you need help with the type inference/overload resolution (I have years fighting it until I get it right), you can also ping me directly on the F# Software Foundation Slack.

We might need to discuss how the (implicit) typeclass hierarchy will be updated with this abstraction, specially to define the defaults.

Btw this abstraction smells a bit to some optic stuff, like ISOs, isn't it?

Finally I wanted to point you to another project: https://github.com/mausch/Fleece which is heavily inspired in Aeson and we're trying to revamp. It seems to be related to the code you posted, I would like to hear your thoughts about it.

[jhbertra]

| I really like the example you wrote, I wish we had more sample code and docs like that.

Could always look into adding some! I've started using this library in a number of projects, I'd be happy to contribute code examples. I agree, examples are by far the most effective way to communicated the purpose / application of an abstraction. I think I've even got a few potential applications of Arrow...

Also had a look at your project, looks interesting, are you porting an existing Haskell project?

This is not a port of a Haskell project, in fact it's quite heavily inspired by Elm's Json.Decode and elm-decode-pipeline. The idea behind the DataBlocks project is to provide a similar interface, but with bidirectional capabilities (can encode or decode from the same spec).

In addition, the intent was not for this to be restricted to JSON. I'm working on genericizing it so that the building block is an Epimorphism that bidirectionally converts from any type to any other type (where the decode direction may fail). This means it can be combined like this:

val jsonCodec : DataBlock<Json, 'a> // can decode and encode JSON data
val jsonSerializer : DataBlock<string, Json> // can parse and write raw JSON

// it's an instance of Category
let jsonStringCodec : DataBlock<string, 'a> = jsonCodec <<< jsonSerializer

val xmlCodec : DataBlock<Xml, 'a> // can decode and encode XML data

// Since it's invariant in both type arguments, it is also a bidirectional category
let jsonXmlConverter : DataBlock<Json, Xml> = jsonCodec ``some additional compose operator`` xmlCodec

// Should be able to define an async version as well
val sqlCodec : AsyncDataBlock<SqlQuery, 'a>
let persistJson : AsyncDataBlock<Json, SqlQuery> = jsonCodec ``some operator`` sqlCodec 

Btw this abstraction smells a bit to some optic stuff, like ISOs, isn't it?

It's related! An Invariant is a functor over which an isomorphism can be mapped.

We might need to discuss how the (implicit) typeclass hierarchy will be updated with this abstraction, specially to define the defaults.

I suspect Haskell and PureScript docs would be a good place to start for this.

Finally I wanted to point you to another project: https://github.com/mausch/Fleece which is heavily inspired in Aeson and we're trying to revamp. It seems to be related to the code you posted, I would like to hear your thoughts about it.

There is another Aeson-based F# project called Chiron which seems to be quite similar in terms of API and implementation.

I do really like the fact that the typing is implicit! That makes the code a lot more terse. I'll have to look over it in more detail :)

[wallymathieu]

Chiron is unfortunately not as composable as you might want. The optics library used is based on data-lens abstractions rather than the current thinking more in line with what @gusty has implemented in f#+. So the optics might need a bit of work to bridge. Fleece could be taken to be more in line with f#+ abstractions rather the abstractions employed by the xyncro family of libraries.

[gusty]

It worth mentioning that Chiron is in fact a clone of Fleece. You can still recognize the original code there, it's basically intact (pitfalls included), the main difference is what @wallymathieu said about lensing. They added some Data Lenses which actually are also a clone of @mausch previous work on Data.Lenses in FSharpx libs.

I personally prefer to contribute back to the original projects.

[jhbertra]

Interesting background there, thanks for sharing!

[wallymathieu]

There is this project for haskell.

[wallymathieu]

In the example:

// We can do:
let contactCodec : JsonCodec<Contact> =
    contact
    |> ``{``
    |> required "name" (fun x -> x.name) (string |> invmap Name (fun Name n -> n))
    |> required "email" (fun x -> x.name) string
    |> optional "phone" (fun x -> x.name) string
    |> ``}``

where does contact come from?

[gusty]

There is this project for haskell.

Yes, I saw it. I guess it's our main reference.

where does contact come from?

I think it's a default definition of the record.

[wallymathieu]

Thanks!

On 11 Apr 2018, at 21:32, Gustavo Leon [e-mail] wrote:

There is this project for haskell.

Yes, I saw it. I guess it's our main reference.

where does contact come from?

I think it's a default definition of the record.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub, or mute the thread.

[wallymathieu]

I was a bit confused by the construction.

From what I read on the haskell project, seems like there are reasons why you would like to have both optics and invariant (though I might not have understood half of it). Though, question is how it plays together with different optics definitions?

I would love to see this idea fleshed out further!

It would be nice to define a codec for LSON? Since a minimal definition of that sort of format contain fewer constructs than JSON.

[wallymathieu]

Being able to get a complete codec for a complex type without having to decorate the type with FromX/ToX would be quite sweet (for instance if you don't want a dependency on X in the domain definition).

[jhbertra]

@wallymathieu

where does contact come from?

I omitted it for brevity, but I realize that may have been confusing, as it's not immediately obvious that it is combining an Applicative and a Divisible (contravariant analogue of Applicative for a divide-and-conquer approach to consuming a data structure). Pretend that code contained this prelude:

type Name = Name of string

type Contact =
  { name : Name
    email : string
    phone : string option }

// IMO F# should auto-generate these constructor functions for records, but oh well...
let contact name email phone = { name = name; email = email; phone = phone }

It would be nice to define a codec for LSON? Since a minimal definition of that sort of format contain fewer constructs than JSON.

This project is still quite new (really, I started it a month ago...) but it is intended to be extensible, so I suspect defining a decoder / encoder / codec for LSON wouldn't be hard.

Being able to get a complete codec for a complex type without having to decorate the type with FromX/ToX would be quite sweet

mhm, that's the idea 🙂 the idea of the library is to pretend domain models aren't allowed to have "static members"

[gusty]

@jhbertra If technically speaking the only difference between Profunctor and Invariant is that the signature of invmap is like a restricted dimap, then it might be convenient to just define invmap like:

let inline invmap (f : 'A->'B) (g: 'B->'A) (source : '``Invariant<'A>``) : '``Invariant<'B>`` =
    Dimap.Invoke g f source

compare to:

let inline dimap (f : 'A->'B) (g: 'C->'D) (source : '``Profunctor<'B,'C>``) : '``Profunctor<'A,'D>`` =
    Dimap.Invoke f g source

This will avoid a lot of code duplication and we'll have automatically an Invariant with each Profunctor.
Unless the instances are different? If so please advise.

[gusty]

Also read https://stackoverflow.com/questions/48708805/how-to-use-data-functor-invariant
It seems to be aligned with my previous comment.

What about divisible?
That seems to be nice a nice addition.

[gusty]

After studying this proposal, I think adding an invmap function alone will not be 100% correct.

The reason is that some types are invariants but not profunctors. Take for instance a JsonCodec defined like this:

type JsonCodec<'t> = JsonCodec of (Json -> Result<'t, string>) * ('t -> Json)

We could define a Dimap static member for this type, but it would have the said invariant restriction.

This would technically work in principle but:

1 - It's not 100% correct in theory
2 - It will give the false impression that JsonCodec is a profunctor but it will only compile if the mapping are of the form 'a->'b and 'b->'a so the compiler error will be hard to interpret (they are already hard, but this will only make things worst).

Note that a key difference with Profunctor is that any Profunctor is also a Functor and a Contravariant (we can just map/contra id on the other side), but an Invariant is not a Functor, nor a Contravariant. For example, you can't just map over JsonCodec, you need to provide the way back at the same time, and id doesn't go back (and it hasn't the expected signature). So:

3 - It will give the false impression that it's a functor and a contravariant, but it will only compile if the mappings are monomorphics ('t -> 't).

So, I propose to do a full implementation of Invariant.

An easy way to do this is to copy-paste Profunctor's Dimap static members, rename them to Invmap and change its f and g signature.

PS: an interesting article involving optics and invariants here: http://oleg.fi/gists/posts/2017-12-23-functor-optics.html

[gusty]

After trying to implement this, I realized that although a Functor can always be made an Invariant (same can be said for a Contravariant Functor) it's a bit arbitrary to do this automatically, and even worst it would lead to inconsistencies with Profunctors, since an invariant over a Profunctor will have the signature Profunctor<'T,'T> -> ('T -> 'U) -> ('U -> 'T) -> Profunctor<'U,'U> which is not coherent with Profunctor<'T,'T> -> ('T -> 'U) -> ('U -> 'T) -> Profunctor<'T,'U>, moreover T and U would have to be unified: Profunctor<'T,'T> -> ('T -> 'T) -> ('T -> 'T) -> Profunctor<'T,'T> which is not a very useful default for Profunctors.

As result, I will add a simple implementation of Invariant with no defaults.