3 ms·
Nope. Example of recursion schemes: You have a binary tree data Tree a = Branch (Tree a) (Tree a) | Leaf a This is a recursive structure since a Tree can
by Tarean 9y ago
Nope. Example of recursion schemes:
You have a binary tree
data Tree a = Branch (Tree a) (Tree a) | Leaf a
This is a recursive structure since a Tree can be made up of other Tree's. We can take a slice of the tree:
data TreeNode a child = Branch child child | Leaf a
data Fix f = F (f (Fix f))
type Tree a = Fix (TreeNode a)
sumTree :: Tree Int -> Int
sumTree = cata algebra
where
algebra (Branch a b) = a + b
algebra (Leaf a) = a
You might notice that we didn't do any recursion in sumTree because cata captures how to traverse the tree. Catamorphisms are the simplest recursion schemes, there are variants that keep track to our position in relation to the rest of the tree or memoize computations and so on.
- bcherny 9y agoI see. You might pass a combinator into a catamorphism, but the morphism itself isn't a combinator?