Introduction to Recursion Schemes • Amy Wong • YOW! 2018

Introducing recursion schemes, a powerful tool for solving recursion problems without explicit recursive function definitions, and exploring catamorphisms, anamorphisms, and paramorphisms through a factorial example.

Key takeaways

The presentation introduces recursion schemes, discussing catamorphisms and anamorphisms as fundamental recursion patterns.
Catamorphisms and anamorphisms can be used to solve recursion problems without needing explicit recursive function definitions.
The algebraic data type is defined as a functor, which allows for better compositionality of the recursive function.
The key idea is to identify the abstraction of the nested structure and then use the recursion scheme to handle the iteration and pattern matching.
The example of calculating the factorial number demonstrates the use of both catamorphisms and anamorphisms to simplify the recursive function definition.
The paramorphism is a combination of catamorphism and anamorphism and can be used to solve more complex recursion problems.
Recursive schemes provide a way to avoid boilerplate code and make the code more modular and reusable.
The presentation also touches on the concept of fixed point and how it relates to recursion patterns.
The recursion schemes library provides various morphisms, such as cata, ana, and paramorphism, which can be used to solve different types of recursion problems.
The presentation concludes with a summary of the key concepts and the idea that recursion schemes can be used to make code more modular and reusable.

Introduction to Recursion Schemes • Amy Wong • YOW! 2018

More talks