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-applicationthe  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 denitions.From http://people.cis.ksu.edu/~schmidt/705s13/Lectures/ch6.pdf .
Is there any practical algorithm / data-structure that can't be done with non-recursive Lambda Calculus augmented with foldl?
programming languages;functional programming;data structures;lambda
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 combinatorY f = (\x -> f (x x)) (\x -> f (x x))Definecons = \a b f -> f a bcar  = \x y -> xcdr  = \x y -> yfst  = \p -> p carsnd  = \p -> p cdrThis is just the standard encoding of church pairs.nil = \x -> x -- Or anything reallyfold = \x -> cons x nilunfold = \x -> fst xThenY 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.