@christianp wikipedia has a page called "iterated binary operation" which also includes taking the intersection or union over indexed sets, as well as sums and products
@ccppurcell and the intro para says 'sequences of elements', so I think I'll go with 'sequences'.
Thanks for the link!
@kimreece @christianp @ccppurcell having stewed on this question for a while, I think I've come to the conclusion that the way most people think about folds doesn't reflect the most natural way. For instance, Foldable in Haskell implies using a binary operation. This makes sense for lists but not for trees where you have two children rather than one, and in fact implementing fold for trees requires you to make some arbitrary decision about traversal order. (1/?)
@kimreece @christianp @ccppurcell Let's take a look at the type signatures. We'll look at what I'll call "bottom-up" folds. For lists we have fold : b -> (a -> b -> b) -> list a -> b. In fact, this is the same as the recursion operator for lists. So in fact I'd argue that "fold" is just another name for recursion. So for binary trees we have a recursor b -> (a -> b -> b -> b) -> tree a -> b. And I would actually argue that this is a natural sort of folding. (2/3)
@kimreece @christianp @ccppurcell This isn't very satisfying, but the point is that there's nothing special about folding; a fold is just a linearization to a list followed by the list recursor. All the important information is in how one linearizes the type in the first place, and even for simple objects such as binary trees there often isn't a single natural way to do that. (3/3)
A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.
\) for inline LaTeX, and
\] for display mode.