All of matryoshka's recursion operators at the moment are not stack-safe. However, always trampolining them can be a performance issue. Therefore, is there any interest in representing recursion schemes in a recursion-less fashion, so that they can be executed in a trampolined or partially-trampolined (a la http://blog.higher-order.com/blog/2015/06/18/easy-performance-wins-with-scalaz/) context?

One way to do this without sacrificing the ability to make plain (not trampolined) recursive calls for data which is known to be small is to write recursion schemes in CPS, such that an ordinary recursive function

def f(a: A): B

is represented as:

def f(a: A, loop: A => Trampoline[B]): Trampoline[B]) 

Then the scheme can make calls to loop instead of explicitly recursing, and it can be executed with each step trampolined, or with none of them trampolined, or with only steps exceeding some maximum stack size trampolined.

Are there any plans for this? Most of this project looks to be pure Scala as far as I can tell.

Hopefully this can be done as a subproject, otherwise we'all need a separate repo.

It'd be great to create a tutorial using the scala-exercises/scala-exercises tool, so users can interactively solve Matryoshka problems.

Hi, I saw the talk from Greg Pfeil and found the park on mutual recursion really appealing.

I created a simple example of numeric and boolean operations that I would be happy to add to a documentation once I figure how to do traversals. It is a nice domain to document due to some obvious rewrites on boolean expressions.

I appreciate that we need a natural transformation to transform A (is higher-kinded Functor a thing?). But not sure if there is further infrastructure around this.

sealed trait BoolAndCalcF[A[_],I]
// Using AtLeastTwoList as a more complex use case
case class And[A[_]](expressions: AtLeastTwoList[A[Boolean]]) extends BoolAndCalcF[A, Boolean]
case class Or[A[_]](expressions: AtLeastTwoList[A[Boolean]]) extends BoolAndCalcF[A, Boolean]
case class Not[A[_]](wrapped: A[Boolean]) extends BoolAndCalcF[A, Boolean]
case class BoolVal[A[_]](value: Boolean) extends BoolAndCalcF[A, Boolean]

// A bridge from calculation to booleans
case class Compare[A[_],I : Numeric, J: Numeric](left: A[I], op: CompOp, right: A[I]) extends BoolAndCalcF[A, Boolean]

case class Add[A[_], I : Numeric](left: A[I], right: A[I]) extends BoolAndCalcF[A, I]
//To show it would not compose with the rest due to Option
case class Divide[A[_], I : Numeric](left: A[I], right: A[I]) extends BoolAndCalcF[A, Option[I]]
case class Num[A[_], I : Numeric](value: I) extends BoolAndCalcF[A, I]

sealed trait CompOp
object CompOp {
  case object GT extends CompOp
  case object LT extends CompOp
  case object EQ extends CompOp
  case object NE extends CompOp
  case object GE extends CompOp
  case object LE extends CompOp
}
//import cats.data.OneAnd
//type AtLeastTwoList[A] = OneAnd[OneAnd[List,A],A]
case class AtLeastTwoList[A](head: A, second:A, tail: List[A]) {
  def map[B](f: A => B) = AtLeastTwoList(f(head), f(second), tail.map(f))
  def fold[B](h: A => B)(f: (B, A) => B): B = tail.foldLeft[B](f(h(head), second))(f)
}

To use Fix etc., it is insufficient to import only

import matryoshka._
import matryoshka.implicits._

An explicit import of matryoshka.data.Fix etc. is required. It would be helpful if the README said so more prominently; right now, this is buried in the eval example.

E.g., is there something we can do, like (Recursive t f, PatternMonoid f) => Monoid t (where PatternMonoid is the missing piece), and similarly for other type classes.

We have (or maybe used to have?) things like this for Functor and Foldable, but should try to expand it as much as possible. I think I remember seeing some instances like this in the Haskell world (perhaps in @pa-ba /compdata).

FunctorT (and TraverseT) was originally created to support transformations on types that had some way to “map” over the pattern functor, but lacked either a project or embed (i.e., {Co}Free). However, there’s no way to change those type classes to the directly recursive approach and maintain that property. I’m not sure what the right approach is going forward.

1. {Co}Free no longer works with FunctorT, so the original use case is already gone (the old implementations relied on incorrect semantics for those types, so it’s just as well)
2. But maybe there are other types that would benefit from that approach?
3. With some constraint changes, we could fold them into the Recursive and Corecursive type classes.
4. But at that point, there are just generic algebra transformations that would avoid needing additional folds at all.

Ok, so I think I’ve convinced myself that those type classes should go away and we should just implement algebra transformations (e.g., AlgebraicTransform => Algebra) to allow us to continue to write transformations the way we already do.

As described in Unifying Structured Recursion Schemes, we can define adjoint folds that cover all of the current Comonadic folds as well as a number of others that don’t fall under the Comonad model (mutu being the one non-comonadic case we currently have implemented).

This would make it easier to depend on it from a project I'm working on where bringing in scalaz as a dependency is a point of contention.

Without all the associated machinery, we want something like this (but less hand-wavy):

sealed abstract class ABT[F[_], A]
final case class Var[F[_], A](v: String) extends ABT[F, A]
final case class Abs[F[_], A](v: String, term: F[A]) extends ABT[F, A]

type BoundExpr[F[_], A] = HCoproduct(ABT, Expr, F, A)

which relies on us having mutual recursion, but gives us multi-sorted ABTs pretty simply, I think.

Hi,

Is there any possibility to publish matryoshka-core artifact for scala 2.13?

Can I help with that?

CC: @djspiewak

Best regards,
Karol

To make it simple for clients to use the library (and to try to encourage a particular usage pattern), we should organize it so a user almost always needs only a single import per file. Here are the three use cases I see for different parts of a program:

when defining algebras

• algebra types
• Recursive/Corecursive/FunctorT/TraverseT types
• project/embed/map/traverse

when using algebras

• AlgebraOps
• folds/unfolds/refolds
• Possibly rec/Corecursive/etc instances
• Distributive laws

when creating recursive data

• fixpoint types & their rec/Corecursive/... Instances

For each of these cases, there should be two imports – one that provides everything via “ops” and one that provides package methods.

For instances on refined types.

E.g. Birecursive.Aux[Int With NonNegative, Option]

The direct approach of

sealed trait Birecursive[T] extends Recursive[T] with Corecursive[T]

doesn’t seem to cut it when an abstract type member is in play, so we need something more clever.

I, @paulp, and @edmundnoble have taken swipes at this so far.

Having a dependency on "com.slamdata" %% "matryoshka-core" % "0.18.0" brings the Scala.js version of monocle-core, scalaz-core and simulacrum.

This creates problems, for example, if you depend on a binary-compatible but different version of scalaz, you will have both on the classpath because sbt can't evict one of them as the artifact names are different. Also sbt-assembly will fail on merge because duplicated .class files are not equals.

Hi! I wanted to let you know about a subtle but pretty fundamental bug we've found in Haskell's recursion-schemes library. Since Matryoshka uses the same "recursion-schemes from comonads" approach as we do, and exposes the same gcata, distZygoT, and histHisto building blocks as we do, I'm pretty sure the bug affects Matryoshka as well.

Now, the bug is pretty subtle. Only zygomorphic histomorphisms and their generalizations (such as the infamous zygo-histomorphic prepromorphism) seem to be affected, and even then, they only compute an incorrect answer when the input tree's depth is at least 3. Another symptom is that histomorphisms do more work when implemented via gcata and distHisto than when implemented by hand. That's the symptom I noticed first, but be sure to read further down, it really is a correctness issue, not just a performance issue.

In our Haskell implementation, we have decided to move away from comonads, but that's a pretty big change, so you might consider the following slightly less drastic but still painful change: remove gzygo and distZygoT from the library. zygo and distZygo are still fine. Manually reimplementing histo might be a good idea too. Keep in mind, however, that these are merely the symptoms I have noticed; there might be more.

Anyway, I wrote a lot more about the problem in the upstream issue, but since the problem is pretty subtle, let me know if you have any question.

Matryoshka could definitely benefit from library-specific advice when it comes to compiler errors. See here for how: https://github.com/softwaremill/scala-clippy#library-specific-advice

It would be good to add an examples module to the project to show usages of different recursion schemes. I'd be happy to have a go at this.

What are your thoughts?

At Scala by the Bay I asked @sellout if recursion schemes could be used on data structures which are not only recursive, but actually contain cycles. If you ever figure it out, please let me know. Thanks!

Because things like Cofree are shaped like [?[_], A] rather than just [?[_]] we end up needing to annotate folds like

p.cata[Cofree[ProfF, Unit]](Cofree((), _))

however, we might be able to create something like cataU (analogous to traverseU) that allows us to avoid the type annotation.

E.g.

• Birecursive#iso should pass the monocle.Iso laws.
• x.ana(f).cata(g) ≟ x.hylo(g, f) (for some generic f and g)
• x.cata(g) ≟ x.hylo(g, _.project) and its dual
• either make other operations (gcata, futu, etc.) final or add laws comparing them to the default impls

Symptoms

cata and other recursion patterns unavailable for Fix and related types.

scalaVersion := "2.11.8"
"com.slamdata"  %% "matryoshka-core" % "0.16.4",

Causes

Ambiguity between recursiveTRecursive and birecursiveTBirecursive, apparently in top-level package object.

How to reproduce

import matryoshka._
import matryoshka.implicits._
import matryoshka.data.Fix
implicitly[Recursive[Fix[Option]]]

<console>:19: error: ambiguous implicit values:
 both method recursiveTRecursive in package matryoshka of type [T[_[_]], F[_]](implicit evidence$81: matryoshka.RecursiveT[T])matryoshka.Recursive.Aux[T[F],F]
 and method birecursiveTBirecursive in package matryoshka of type [T[_[_]], F[_]](implicit evidence$83: matryoshka.BirecursiveT[T])matryoshka.Birecursive.Aux[T[F],F]
 match expected type matryoshka.Recursive[matryoshka.data.Fix[Option]]
       implicitly[Recursive[Fix[Option]]]
                 ^

Same problem for Mu and Nu.

Workaround

def r(implicit r: BirecursiveT[Fix]) = matryoshka.birecursiveTBirecursive(r)