Which algorithms can be expressed using a total functional language with data parallel operators? Imagine a functional programming language whose only data types are numerical scalars and arbitrary nestings of arrays. The language lacks any means of unbounded iteration, so the following are disallowed:


explicit loops (not much use without side-effects anyhow)
recursion
arbitrary first-class functions (no y-combinator)


The language does, however, have:


top-level functions
lexically scoped let bindings
branching control flow
common scalar math and logic functions
some simple array constructor like fill(n,x) which creates an n-element array with identical values x
most importantly: a restricted set of higher-order operators which perform parallel structured iteration (such as map, reduce, scan, all-pairs).


To be more specific about the data parallel operators: 


y = map(f,x) => y[i] = f[i] 
y = reduce(f, a, x) => y = f(a, f(y[p[0]], f(y[p[1]], ...))) for some permutation p
y = scan(f, a, x) => y[i] = reduce(f, a, y[0...i-1])  
y = allpairs(f, x, y) => y[i,j] = f(x[i], y[j])


We could have other operators as well, but to qualify they should have polynomial running time, be implementable under some reasonable model of data parallel computation, and use at most polynomial space. 

There are obviously some constructs which can't be expressed in this language, such as:

while f(x) &gt; tol:
    x &lt;- update(x)   


What can we express in this system? Are we limited only to search problems in FP? Can we capture all polynomial time algorithms? Also, is there some minimal set of operators for this class?
You might want to look at the old programming language NESL which took these ideas seriously. The language is based on operations on collections, essentially lists and lists of lists and so forth, but I think trees and graphs were also considered, via tricky encodings. Some of the research done in that project (in the mid 1990s) could help answer your question. The PhD thesis (available as a book) Guy E. Blelloch. Vector Models for Data-Parallel Computing. MIT Press, 1990 may provide some answers. It was some time ago since I looked at it.

Work done on the Bird-Meertens Formalism (BMF) falls into this category too, as did the language Charity. From the Charity wikipedia page it says that the language is not Turing complete, but can express Ackermann's function, which means that it's more than primitive recursive. Both BMF and Charity involve operators like folds and scans (catamorphisms, anamorphisms, etc), and they have their roots in Category Theory.

I short, imprecise answer is that you can express quite a lot.