Add monadic zygomorphism

[kanterov]

I'm developing compiler with matryoshka, my original motivation is to annotate tree with types, and then compile, both phases operate under M = Error \/ ?. Basically, I want to do zygomorphism where both algebras are effectful.

I'm very new to recursion schemes, but I have a feeling there is something wrong because I wasn't able to describe zygoM in terms of gcataM. I'm not sure that this function is called zygoM, because probably it should be:

  def zygoM[A, B, M[_]: Monad]
    (t: T)
    (f: Algebra[Base, B], g: GAlgebraM[(B, ?), M, Base, A])
    (implicit BF: Traverse[Base])
      : M[A]

But then I'm not sure what is the right function for the particular use case I had.

I didn't add any tests because I'm not yet sure this is the right thing. I would be glad to get any help or feedback on this.

[CLAassistant]

All committers have signed the CLA.

[kanterov]

Just realized that in my particular case I need something like

  def elgotZygoM[A, B, M[_]: Monad]
    (t: T)
    (f: AlgebraM[M, Base, B], g: ElgotAlgebraM[(B, ?), M, Base, A])
      : M[A]

[sellout]

@kanterov Feel free to add that, too 😄

[kanterov]

@sellout I added tests. I had to extract zygomorphism tests because compilation time of specs.scala is terrible. Can you please take a look?

[kanterov]

@sellout I've updated zygoM, I had problem with implicit resolution, so I had to introduce W[_] before, I've cleaned it up and extracted signature of gcataM as it probably should be. Could you please take a look?

[kanterov]

Signing CLA is WIP, need to check with my employer first, but it shouldn't be a problem.

[kanterov]

@sellout squashed, signed CLA, generalized gcataM, can you please take a look again? :)

[sellout]

Trying to trigger a Travis build …

[sellout]

I know this looks mergable, but our merge script says it’s not. Can you merge master into this branch? Then we should be good.

[kanterov]

@sellout I've rebased latest master on this branch.

Are these scripts public? Your release process looks awesome.

By the way, I'm not familiar with it, but probably this change needs to be documented as breaking.

[sellout]

Breaking because of the change to gcataM? This is what I get for not having better test coverage … I had assumed that there were already uses of gcataM in definitions of other monadic, but alas that’s not true.

So, the gist of the breaking change is that def cataM(t: T)(f: AlgebraM) = gcataM(t)(distCata, f) will no longer work because we need to do something about the new M ∘ in the gcataM DistributiveLaw, right?

[sellout]

Also, our merge script is at https://github.com/slamdata/devtools/blob/master/bin/merge, and any of the publishing releases stuff is in https://github.com/slamdata/sbt-slamdata it’s not perfect, but I’m putting together a blog post that describes it and what parts of it we do & don’t like currently.

[kanterov]

Yes, true, but I didn't find any open source codebase using gcataM, and it's possible to write a function from DistributiveLaw[F, W] to DistributiveLaw[F, M ∘ W] for any M[_]: Applicative, so I see it mostly as a change breaking binary compatibility.