I was checking what Wikipedia has to say on reduce. It says:
In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a return value.
This raises the question: Are foldable data structures always recursive (or can be seen as such)? This is obvious for things such as lists and trees (in Haskell):
data List a = Nil | Cons a (List a) data Tree a = Empty | Node (a, Forest a) data Forest a = Nil | Cons (Tree a) (Forest a)
In other words, are all iterable data structures also recursive?* How would one go about proving this?
*I'm assuming that being iterable is sufficient to be foldable.
data Bool = True | Falsewhich is not a recursive type in the sense that
Booldoesn't occur recursively in its definition. It is an inductive type though. Does this count as a recursive data structure? $\endgroup$