2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Derek Elkins Jun 23 at 21:07
  • 2
    $\begingroup$ 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? $\endgroup$ – Derek Elkins Jun 23 at 21:09
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.