foreverglade (@foreverglade)

The two simplest recursion schemes are catamorphisms and anamorphisms. With catamorphisms you turn a data structure into a single value by recursing into them and at the "tips" of the data structure you replace it with a value of what you are turning it into. An example of a "tip" would be the leafs of a tree or the nil at the end of a list. Example: Summing a list of ints by turning the nil of a list into a 0 and then continually replacing the last cons cell with the sum of both ints. In the end you will be left with an int which is the sum of a list. Anamorphisms on the other hand are the dual to catamorphisms. You start with a seed value and have a way to turn that into a data structure. Then you recurse into the data structure you just made and repeat the process. This process will goon forever until you end it with a tip. Example: Creating a list of positive numbers by starting with the seed of 0 and then continually taking the current seed adding 1 to get the new seed and putting the new seed in the next cons cell.