search

precog / matryoshka

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

Shaky foundations for generalized recursion schemes #98

Open gelisam opened 6 years ago

gelisam commented 6 years ago

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.

gelisam commented 6 years ago

Speaking of bugs in the Haskell library which also affect Matryoshka: your ghisto implementation seems to have the same bug as ours did: https://github.com/ekmett/recursion-schemes/issues/48

Thankfully, fixing that bug is much easier than the foundational issues above :)