Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Provide stack-safe implementations of recursion schemes #7

Open
jnape opened this issue Feb 25, 2017 · 2 comments
Open

Provide stack-safe implementations of recursion schemes #7

jnape opened this issue Feb 25, 2017 · 2 comments
Assignees

Comments

@jnape
Copy link
Member

jnape commented Feb 25, 2017

Supporting type-safe, stack-safe recursion schemes in Java is no small feat, but I'm not convinced it's impossible.

First, attempt to provide reasonable, type-safe implementations of the following:

  • Algebra
  • Coalgebra
  • Fix
  • Free
  • Cofree
  • Catamorphism
  • Anamorphism
  • Hylomorphism
  • Paramorphism
  • Zygomorphism
  • Histomorphism
  • Apomorphism
  • G-apormophism
  • Prepromorphism
  • Postpromorphism
  • Dynamorphism
  • Chronomorphism

Assuming type-safe, working representations of each of these can be found, the real challenge of what to do about stack safety in lieu of a lazy type system must be overcome.

This is experimental. If by the end of this I can't arrive at reasonable stack-safe implementations without profoundly mutilating the natural and intuitive arguments to these functions (for instance, replacing canonical algebras with some terrible type explicitly representing an AST, to avoid immediate evaluation), I'll abandon this branch.

At the very least, this exercise can serve as a cautionary tale for the combined detrimental effects of hubris and determination versus Java's infuriating type system.

@jnape jnape self-assigned this Feb 25, 2017
@jnape
Copy link
Member Author

jnape commented Mar 12, 2017

Tracking this work on the recursion-schemes branch.

@jnape
Copy link
Member Author

jnape commented Mar 24, 2019

A New Hope: palatable/lambda#47

@jnape jnape transferred this issue from palatable/lambda Feb 8, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant