Is there any practical algorithm / data-structure that can't be done with non-recursive Lambda Calculus augmented with foldl?

Question

In my search for a practical non-turing complete programming language, I've been paying attention to lambda-calculus with disallowed self-application - that is, x x forbidden. After taking that language and augmenting it with lists and the foldl and range operations, pretty much any algorithm I've tried so far is implementable. It is trivial to implement filter, reverse, head, tail, map, scanl, zip and many others - foldl replaces the need for recursion.

Can you think in any practical, important algorithm that would be undoable in that language?

It is no coincidence that all of them use self-application—the application of an expression to itself. It is through self-application that repetitive computation can be simulated in the lambda calculus. Indeed, the third of the previous three examples is famous because it can encode recursive function definitions.

From http://people.cis.ksu.edu/~schmidt/705s13/Lectures/ch6.pdf .

Answer 1

tl;dr (or I don't know what a Y combinator is)

This question is based on the assumption that the above defined language is not Turing-complete, it actually is Turing-complete and therefore the question is invalid - all algorithms can be expressed in the language defined above as is the meaning of Turing-completeness.

---

Ok. Well apparently this has to be explicitly written out.

Proof of turing completeness follows trivially from unbounded recursion which can be derived from a fixpoint combinator.

Note the traditional Y combinator

Y f = (\x -> f (x x)) (\x -> f (x x))

Define

cons = \a b f -> f a b
car  = \x y -> x
cdr  = \x y -> y

fst  = \p -> p car
snd  = \p -> p cdr

This is just the standard encoding of church pairs.

nil = \x -> x -- Or anything really
fold = \x -> cons x nil
unfold = \x -> fst x

Then

Y f = (\x -> f (unfold x x)) (fold (\x -> f (unfold x x)))

No self application, but this still correctly encodes the Y combinator. I previously wrote this out in Haskell. There fold and unfold require more interesting jiggery-pokery because of types, but since lambda calculus has none we can safely ignore it :)

We've just proven we have a Turing-complete language. Every algorithm is therefore exactly as efficient as can be encoded in a Lambda Calculus. This also invalidates the question's original premise that the language is Turing-incomplete.