This was started in a different thread, but I figure it’s better to avoid derailing that conversation.
The main idea is that if you look at foldl for example:
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
and you compare it with, say, maybe:
maybe :: b -> (a -> b) -> Maybe a -> b
You can see a bit of a pattern here. The main idea is, you provide cases for each constructor of the type. Both have an empty constructor, so they both need a
b value for that case.
Maybe is simpler since it can only contain at most one value, so we only need a basic function
a -> b.
List, on the other hand can have multiple values (as demonstrated by its
Cons a (List a) constructor.
This works for product types just as well. For example,
Tuple can be folded using
uncurry :: (a -> b -> c) -> (a, b) -> c.
The common idea is factored out in recursion-schemes via the
Base type family (which basically describes the constructors for a type) and the
Recursive type class.