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

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?

• This sounds like quite good problem. It could be difficult to solve if you're used to some other primitives than what was provided. – tp1 Nov 26 '11 at 23:16
• Yes, it is the ultimate challenge among the bonuses. Easier ones allow recursion or abstract list functions. – Erica Xu Nov 26 '11 at 23:29

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) …)))
``````
• Sorry we haven't studied lambda calculus yet. But wow, this is very eye-opening! – Erica Xu Nov 27 '11 at 2:45
• @EricaXu Fixpoint combinators are indeed an “oh wow” idea, and they're an important idea in programming language theory. They're not something I'd expect a student to come up with on their own, however. Are you sure the assignment said no recursion at all? If the assignment allowed a single recursive function, it may have been after the use of `foldr` as the ultimate list iterator (another very important idea, this time in understanding data structures), or after the encoding of `let` into `lambda` (a minor but nonetheless important idea in programming language theory). – Gilles 'SO- stop being evil' Nov 27 '11 at 2:52
• The requirements are quoted here: "(c) For the ultimate challenge, write the Scheme function subsets3. As always, the func- tion produces the list of subsets of an input list of numbers. Do not write any helper functions, and do not use any explicit recursion (i.e., your function cannot call itself by name). Do not use any abstract list functions. In fact, use only the following list of Scheme functions, constants and special forms: cons, first, rest, empty?, empty, lambda, and cond. You are permitted to use define exactly once, to define the function itself. (Value: 5%)" – Erica Xu Nov 27 '11 at 2:56
• I think the profs don't want us to "come up with" the solution but only to put some thoughts into it. For example I would not have known the name "lambda calculus" if there were not a question like this. – Erica Xu Nov 27 '11 at 2:57
• Hi this course just ended today. It turns out that the last module is the CS history, from Charles Babbage all the way to the post Turing era. My prof illustrated the changes along the way. As for lambda calculus, we saw how to construct 0, 1, 2, etc, and were told that general recursive is hard but still possible. I guess this is their initial intention: to let us think this was hard or even impossible, and when our curiosity is ready, learning this history is more fun. I really enjoyed today's lecture!!! – Erica Xu Dec 1 '11 at 18:53