# Are all foldable data structures also recursive?

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.

• The first step of proving (or disproving) this would be to define your terms. What's a "foldable data structure"? What's an "iterable data structure"? What's a "recursive data structure"? A few examples and/or some suggestive naming don't constitute a definition. – Derek Elkins Jun 23 at 21:07
• As one example of this issue. You can define a fold function for data Bool = True | False which is not a recursive type in the sense that Bool doesn't occur recursively in its definition. It is an inductive type though. Does this count as a recursive data structure? – Derek Elkins Jun 23 at 21:09

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.