## Where communities thrive

• Join over 1.5M+ people
• Join over 100K+ communities
• Free without limits
##### Activity
• Apr 01 2020 16:34

precog-bot on v0.18.6

• Apr 01 2020 16:20
djspiewak closed #108
• Apr 01 2020 16:20

djspiewak on v0.18.x

Set up new infrastructure Bumped to newer slamdata-predef Added repl to the aggregation and 2 more (compare)

• Apr 01 2020 16:10
djspiewak synchronize #108
• Apr 01 2020 16:10

djspiewak on infra

Apparently we need *both* versi… (compare)

• Apr 01 2020 16:03
djspiewak synchronize #108
• Apr 01 2020 16:03

djspiewak on infra

Added repl to the aggregation (compare)

• Apr 01 2020 15:56
djspiewak synchronize #108
• Apr 01 2020 15:56

djspiewak on infra

• Apr 01 2020 15:52
djspiewak assigned #108
• Apr 01 2020 15:52
djspiewak labeled #108
• Apr 01 2020 15:52
djspiewak opened #108
• Apr 01 2020 15:52

djspiewak on infra

Set up new infrastructure (compare)

• Apr 01 2020 15:38
natefaubion removed as member
• Apr 01 2020 15:38
djspiewak unassigned #88
• Apr 01 2020 15:38
djspiewak unassigned #87
• Apr 01 2020 15:38
djspiewak unassigned #77
• Apr 01 2020 15:38
djspiewak unassigned #79
• Apr 01 2020 15:38
djspiewak unassigned #76
• Apr 01 2020 15:38
djspiewak unassigned #65
@wibisono
Any idea how to turn into factorial? https://scalafiddle.io/sf/zZ4J3im/0
A bit went over my head this recursive scheme but it's interesting.
Greg Pfeil
@sellout
@wibisono I think just
val fact: Coalgebra[Expr, Long] = x => {
if(x>1)  Mul(x, x-1) else Num(1)
}
@wibisono
I thought so too
but it stack overflow : https://scalafiddle.io/sf/zZ4J3im/1
Greg Pfeil
@sellout
But the pluses version didn’t?
@wibisono
yup
the left side of the plus is 1 so it won't get expanded again
the fact version seems to expand again both side
Greg Pfeil
@sellout
Ohhhhh! yeah, yeah.
Sorry.
Yeah, it would :D
So, I think you want an apo
@wibisono
ok I need to read first what creature is that :D
Greg Pfeil
@sellout
val fact: GCoalgebra[Either[Fix[Expr], ?], Expr, Long] = x => {
if(x>1)  Mul(Left(Fix(Num(x))), Right(x-1)) else Num(1)
}
(untested)
Uses Left to say “don’t recurse”
But it means you have to give it a completed Fix[F]
@wibisono
Works! but I need scalaz \/
:D thanks a lot
Now I need to understand why :P
Roman Tkalenko
@tkroman

How do I approach the problem of designing an AST for an SQL-like language that would allow for using matryoshka?
The issue I'm having right now is that if I have eg something like this, simplified:

sealed trait Expr

case class Select(fields: List[String], distinct: Boolean) extends Expr

sealed trait From
case class TableName(get: String) extends From
case class Subquery(expr: TopLevelQuery) extends From

case class TopLevelQuery(select: Select, from: From) extends Expr

definitions of TopLevelQuery and e.g From are "mutually" recursive (same would happen for join, union, in etc).
I can't come up with decomposition of this into non-self-referential set of ADT leaves. For example, how do I express TopLevelQuery as a GADT?
Am I approaching this from the right side? What are my options here?

Fredrik Skogberg
@freskog
Hi all, I was wondering if anyone knows whether it's possible to use recursion schemes with graphs?
Say implement something like topological sort
kczulko
@kczulko
Hi,
I'm starting my journey with Recursion Schemes so my issue may be elementary' for some of you. I'm wondering if I can apply the approach of "nanopass compilers" and do some kind of desugaring/preprocessing before applying some more complex transformations.
In my example (https://scalafiddle.io/sf/lemEEdz/1) I'd like to replace AddF(l,r) with MulF(NumF(2), r) if l == r.
Is there any way to compose two algebras and gain efficiency of single pass transformation? I've found this: https://gitter.im/slamdata/matryoshka?at=5b5766b5f9ffc4664bfcb3f6 and @sellout talk about nanopass compilers but I don't have the idea how to compose algebras in e.g. cata. Does anybody know what I'm doing wrong? Thanks in advance.
Greg Pfeil
@sellout
@kczulko Yeah – there are a number of ways to compose algebras for use in a single pass – operations like zipAlgebras for parallel composition, multiple ways to do sequential composition (e.g., zygo), then there are ways to combine algebras and coalgebras (e.g., hylo). And other stuff as well.
The AddF case can easily be handled with an addToMult: ExprF[Fix[ExprF]] => ExprF[Fix[ExprF]] function. Notice that that’s not strictly an algebra, but you can do addToMult >>> (_.embed) or addToMult <<< (_.project) to turn it into an Algebra or Coalgebra, respectively.
Writing your functions in the most natural way often makes it easier to use them more generally, rather than trying to pre-fit them to a particular structure.
Greg Pfeil
@sellout
@freskog Sorry for getting to this so late, but it is possible to use recursion schemes with graphs, but not ideal. We do that at work, and depending on the specific folds/unfolds, it can be delicate to ensure that you don’t re-process certain nodes, etc. Also, depending on your graph representation, it might be partial to do so – e.g., using an adjacency list, which might have broken references to nodes that don’t exist. Graph validation helps with that, but you still need to handle the possible error cases.
Note, that that representation is a single-sorted expression language. It was a lot of work to get something that was fairly compatible with SQL while being a more general/principled language. So, it doesn’t use GADTs, but using GADTs and recursion schemes is certainly feasible.
kczulko
@kczulko
@sellout, huge thank you for pointing me to a function ExprF[Fix[ExprF]] => ExprF[Fix[ExprF]] but... I still don't get it how can I compose it (or an Algebra after the composition with (_.embed)) with e.g. evaluateInt algebra to
achieve single pass execution :/. In my example (5.hylo(addToMulAlg >>> evaluateInt, unfoldSum)), I'd like to do substitution and evaluation at once. Is that possible?
Greg Pfeil
@sellout
@kczulko In your case, you might do something like addToMulAlgApo[A: Eq]: ExprF[A] => ExprF[Either[Fix[ExprF], A]], which I maybe should have presented that way initially anyway, or addToMulAlgNT: ExprF[Int] => ExprF[Int]. With the former, you can do case AddF(l,r) => if (l == r) MulF(Left(NumF(2).embed), Right(r)) else AddF(Right(l), Right(r)) and in the latter case a@AddF(l,r) => if (l == r) MulF(2, r) else a. They mean slightly different things, which may not matter for you. The former will treat the 2 as atomic, and not process that branch any more, but the latter will continue processing the branch, so maybe it becomes AddF(NumF(1), NumF(1)), depending on your unfoldSum. And then you could (with the latter algebra) do 5.hylo(evaluateInt, addToMulAlgNT <<< unfoldSum). The former case is a little more complicated, because I don’t think there’s a common name for a hylo that combines cata and apo. But (with a bunch more type annotations, 5.ghylo(distCata, distApo, evaluateInt, addToMultAlgApo <<< unfoldSum) should do the right thing.
Notice in both cases, you’re applying the addToMult on the unfold side. It doesn’t make sense (I don’t think) to do it in the same pass on the fold side, because by the time you got to AddF(l, r), l and r would already be evaluated. So, no point in AddF(5,5)MulF(2, 5)10. But, you could do that with 5.hylo(evaluateInt <<< addToMulAlgNT, unfoldSum).
kczulko
@kczulko
@sellout, thank you for such comprehensive answer. Now it's clear. I just didn't notice that I can choose "arbitrary" type for my "algebra" which I want to compose (vide ExprF[Int] => ExprF[Int]). My example can be silly at some point (which you inevitably have noticed) but all I wanted to know with it was how can I do some desugarnig/transformation on the fly. Thx once again for your help!
Nick Childers
@Voltir
Im playing with natural transformations (ie prepro), and was wondering if there is a hylo like combinator for doing something like : coalgebra -> nat -> algebra
Greg Pfeil
@sellout
@Voltir You can just compose the natural transformation on either side: hylo alg (nat . coalg) or hylo (alg . nat) coalg
Nick Childers
@Voltir
Yep - although I haven't been able to make the syntax in scala as clean as that
Nick Childers
@Voltir
Does matroshka define such a compose operator for nat and an algebra? cats.FunctorK and droste's Algebra don't seem to play that nice together
Greg Pfeil
@sellout
So, no promises, but <<< and >>> in either Scalaz or Cats should be able to make something like alg <<< nat.apply work. Algebra and Coalgebra are already Function1, so they should be enriched with those Category operators. Like nat.apply <<< coalg might not work, since apply is a method. But then (nat.apply[A](_)) <<< coalg would work or coalg >>> nat.apply.
I agree that composition in Scala is not as easy as it should be.
@Voltir
Marcin Pucilowski
@Pucilowski
All the examples I've found of matryoshka build trees that resolve to a single type: In the case of Expr[+A] the base case is Literal[A](value: Integer). I would like to have multiple types: NumberExpr, PointExpr, PolygonExpr as well as their sequenced equivalents. The operations would mix types, e:g: Voronoi(extent: PolygonExpr, seeds: Seq[PointExpr]) extends SeqExpr[Polygon]] (perhaps?). How achievable is this?
kczulko
@kczulko
Hi. Is there anywhere matryoshka-core artifact for Scala 2.13?
Luciano
@lJoublanc
Hi guys, I've been watching Greg's videos on Matryoshka and am very excited to start using it. All the material seems a little old though, and I can see the last commit to the project was last year.
Where is the most up-to-date quickstart/doc available? I assume the library is still actively maintained?
Luciano
@lJoublanc
How would I go about writing a depth-first search for a structure of type Free[Map[String,?],A]: a recursive, labelled structure, such as e.g. JSON (without arrays). I suspect I would need an unfold, as the order of traversal has to be from root-to-leaves.