How much theory have you studied? If you've had classes about the lambda calculus, now is the time to put them to good use.
At this point, pause and think back to what you've studied. Do you remember anything about recursion in the lambda calculus?
The specification cannot be met by a constant-time program. (Proof: the size of the output is superlinear in the size of the input.) Yet all the primitives you list operate in constant time. You can't make a non-constant time program out of constant-time primitive constructs.
Ok, what I've written is true, but confusing in this context: the primitive constructs provided by the language include more than the functions you have at your disposal. Recursion obviously allows you to write any computable program out of constant-time functions. You don't have recursion here, however. But you have function application. That's not a constant-time operation — it can reach any complexity, depending on the function you're applying. And you can build recursion out of function application.
Does this trigger any memories yet?
It's called a fixpoint combinator. I'll refer you to your lecture notes or the Wikipedia article for an explanation of how they work. For completeness, here's a definition of a fixpoint combinator in Scheme, for a function that takes one argument:
(define (fix1 phi)
((lambda (rec) (phi (lambda (x) ((rec rec) x))))
(lambda (rec) (phi (lambda (x) ((rec rec) x))))))
Now you can define a list iterator (using here a three-argument variant of the fixpoint combinator for clarity).
(fix3 (lambda (foldr)
(lambda (f l a)
(if (empty? l) a (f (first l) (foldr f a (rest l))))))))
And I guess you know how to go on from there already.
One last point: we've used
define more than once. But that's for convenience only. You can make
foldr and any other auxiliary function you may need local definitions. And then write your single function as an application:
((lambda (foldr it)
(lambda (l) (foldr it '() l)))
(lambda (x sets) …)))
(lambda (phi) …)))