Process arbitrarily large lists without explicit recursion or abstract list functions?

Question

This is one of the bonus questions in my assignment.

The specific questions is to see the input list as a set and output all subsets of it in a list. We can only use cons, first, rest, empty?, empty, lambda, and cond. And we can only define exactly once.

But after a night's thinking I don't see it possible to go through the arbitrarily long list without map or foldr.

Is there a way to perform recursion or alternative of recursion with only these functions?

Answer 1

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).

(define foldr
  (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 fix3, foldr and any other auxiliary function you may need local definitions. And then write your single function as an application:

(define subsets
  ((lambda (fix3)
     ((lambda (foldr it)
        (lambda (l) (foldr it '() l)))
      (fix3 …)
      (lambda (x sets) …)))
   (lambda (phi) …)))