recursion-algorithms

██████╗ ███████╗ ██████╗██╗   ██╗██████╗ ███████╗██╗ ██████╗ ███╗   ██╗
██╔══██╗██╔════╝██╔════╝██║   ██║██╔══██╗██╔════╝██║██╔═══██╗████╗  ██║
██████╔╝█████╗  ██║     ██║   ██║██████╔╝███████╗██║██║   ██║██╔██╗ ██║
██╔══██╗██╔══╝  ██║     ██║   ██║██╔══██╗╚════██║██║██║   ██║██║╚██╗██║
██║  ██║███████╗╚██████╗╚██████╔╝██║  ██║███████║██║╚██████╔╝██║ ╚████║
╚═╝  ╚═╝╚══════╝ ╚═════╝ ╚═════╝ ╚═╝  ╚═╝╚══════╝╚═╝ ╚═════╝ ╚═╝  ╚═══╝

 █████╗ ██╗      ██████╗  ██████╗ ██████╗ ██╗████████╗██╗  ██╗███╗   ███╗███████╗
██╔══██╗██║     ██╔════╝ ██╔═══██╗██╔══██╗██║╚══██╔══╝██║  ██║████╗ ████║██╔════╝
███████║██║     ██║  ███╗██║   ██║██████╔╝██║   ██║   ███████║██╔████╔██║███████╗
██╔══██║██║     ██║   ██║██║   ██║██╔══██╗██║   ██║   ██╔══██║██║╚██╔╝██║╚════██║
██║  ██║███████╗╚██████╔╝╚██████╔╝██║  ██║██║   ██║   ██║  ██║██║ ╚═╝ ██║███████║
╚═╝  ╚═╝╚══════╝ ╚═════╝  ╚═════╝ ╚═╝  ╚═╝╚═╝   ╚═╝   ╚═╝  ╚═╝╚═╝     ╚═╝╚══════╝

This respository is a collection of various algorithms written using recursion schemes. Recursion schemes brings a brilliant perspective guided by Category Theory to recursive data structures and algorithms. I was particularly impressed by “A Duality of Sorts” written by R. Hinze et al. that pointed out that there is a nice duality between the well-known sorting algorithms.

The purpose of this repository is to provide a broad and comprehensive collection of algorithms written by recursion schemes to discover hidden relationships between algorithms. This is a work in progress and I can only work on it in my free time, so contributions will be greatly appreciated. For more information on how to contribute, please refer to “How to get involved” below.

This repository uses recursion-schemes to implement the algorithm. If any recursion schemes are missing, they are implemented in the Extra Recursion Schemes.

Table of Contents

Data Structures

• Nat
• List
• Tree
• Levels

Algorithms

• Natural Number
  • Basic Operations
    • add
    • product
    • factorial
    • lessThan
  • Fibonacci Numbers
  • Catalan Numbers
• List
  • Basic Operations
    • length
    • filter
    • map
    • zip
    • iterate
    • reverse
    • span
    • groupBy
    • subsequences
    • permutations
    • scanr / scanl
    • take / drop
    • takeWhile / dropWhile
    • inits / tails
  • Edit Distance
  • Longest Common Subsequence
  • Run Length Conversion
  • Matrix Chain Multiplication
  • Sorting
    • Insertion Sort
    • Selection Sort
• Tree
  • Basic Operations
    • depth
  • Depth First Search
  • Breadth First Search
• Extra Recursion Schemes

How it works

All algorithms have been tested by doctest. To make the code test compatible with the markdown used in GitHub Pages, there’s a conversion process from markdown to Haskell in the stack test.

How to get involved

Please, feel free to send a PR with

• implementing an algorithm that doesn’t yet exist (don’t forget to explain and doctest),
• adding a recursive data structure that can be represented as an fixed point,
• adding a description of some recursion schemes,
• and fixes of typos/bugs/etc.

And if any of the references are wrong or not appropriate, please let me know. If you have any feedback, please make an issue or contact @lotz84_.

Related Projects

• tayllan/awesome-algorithms: A curated list of awesome places to learn and/or practice algorithms.

This site is open source. Improve this page.