search

precog / matryoshka

Generalized recursion schemes and traversals for Scala.
Apache License 2.0
811 stars 87 forks source link

Define more operations in terms of cata, ana, and hylo. #72

Closed sellout closed 7 years ago

sellout commented 7 years ago

This is especially useful for Mu/Nu, since these operations will now use the specialized ana/cata rather than the naïve implementations.

Also greatly reduces the number of places we use general recursion.

sellout commented 7 years ago

@paulp I’m guessing this should remove ~19 of the 68 warnings from the Recursion wart. It’s a start.

paulp commented 7 years ago

Very much an improvement. From my POV the entire endeavor is much clearer when the hylomorphism takes center stage and the rest is understood relative to that (e.g. ana and cata as degenerate hylomorphisms) where possible. So to see the implementations take that approach is excellent.

Baccata commented 7 years ago

Wow this makes so much sense ! Really helps wrapping my head around the concepts. Seems like it will make for a much simpler expression of why recursion schemes matter.

sellout commented 7 years ago

Yeah, I often explain things like cata(f) === hylo(f, project), and the implementations are actually identical, so I don‘t know why I didn’t actually define it this way before. The Recursion wart really helps highlight the things we want to avoid, though 😆

sellout commented 7 years ago

@paulp BTW, there are at least a handful of other cases I’d like to fix in this PR if you don’t mind waiting a bit. The shorter warning list made a few other changes obvious.

tscholak commented 7 years ago

just out of curiosity, for cata(f) === hylo(f, project), are there impacts on speed, either during compile or run time?

sellout commented 7 years ago

@tscholak I haven’t benchmarked it, the implementation is pretty much identical. The only difference is that project is passed as a parameter to each recursive call and I’m not sure what the overhead of that might be. Also, there is the indirection of one more function call – cata -> hylo.

sellout commented 7 years ago

@paulp Ok, I think that’s all for the time being.

sellout commented 7 years ago

@paulp Ok, merged in master and made a couple more small changes. Should be ready for merge for reals.

paulp commented 7 years ago

It would be great to leverage this very library to compare the precise operation counts of various approaches. No reason we should have to speculate about what's happening under the hood.