Can all recursive structures be replaced by a non recursive solution?

Question

For example, could you define a list in Haskell without defining a recursive structure? Or replace all lists by some function(s)?

data List a = Empty | (a, List a) -- <- recursive definition

EDIT

I gave the list as an example, but I was really asking about all data structures in general. Maybe we only need one recursive data structure for all cases where recursion is needed? Like the Y combinator being the only recursive function needed. @TikhonJelvis 's answer made me think about that. Now I'm pretty sure this post is better suited for cs.stackexchange.

About current selected answer

I was really looking for answers that looked more like the ones given by @DavidYoung & @TikhonJelvis, but they only give a partial answer and I appreciate them. So, if any has an answer that uses functional concepts, please share.

Answer 1

That's a bit of an odd question. I think the answer is not really, but the definition of the data type does not have to be recursive directly.

Ultimately, lists are recursive data structures. You can't define them without having some sort of recursion somewhere. It's core to their essence.

However, we don't have to make the actual definition of List recursive. Instead, we can factor out recursion into a single data type Fix and then define all other recursive types with it. In a sense, Fix just captures the essence of what it means for a data structure to be recursive. (It's the type-level version of the fix function, which does the same thing for functions.)

data Fix f = Roll (f (Fix f))

The idea is that Fix f corresponds to f applied to itself repeatedly. To make it work with Haskell's algebraic data types, we have to throw in a Roll constructor at every level, but this does not change what the type represents.

Essentially, f applied to itself repeatedly like this is the essence of recursion.

Now we can define a non-recursive analog to List that takes an extra type argument f that replaces our earlier recursion:

data ListF a f = Empty | Cons a f

This is a straightforward data type that is not recursive.

If we combine the two, we get our old List type except with some extra Roll constructors at each recursive step.

type List a = Fix (ListF a)

A value of this type looks like this:

Roll (Cons 1 (Roll (Cons 2 (Roll Empty))))

It carries the same information as (Cons 1 (Cons 2 Empty)) or even just [1, 2], but a few extra constructors sprinkled through.

So if you were given Fix, you could define List without using recursion. But this isn't particularly special because, in a sense, Fix is recursion.