Are all foldable data structures also recursive?

Question

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.

Answer 1

No, not all foldable data structures are recursive, although the in the non-recursive case what we have is really a degenerate version of a fold.

For example, we can view the function if : Bool -> a -> a -> a as a fold over the type Bool.

In general, when dealing with recursive or non-recursive types, the fold are called eliminators, since they are how we consume values of a given datatype. Eliminators are particularly interesting for dependent types and indexed type families, where the eliminator corresponds to an induction principle for that data type. See this paper for more info on this.

Eliminators always terminate, which means that if you have only eliminators (in place of general recursion) you will not be Turing Complete. You can even encode a data structure as its eliminator, using something called Church Encodings. Using this, you can write lists and other data types in a language that only has functions, like System F.