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

Posted by Erica Xu on Programmers See other posts from Programmers or by Erica Xu
Published on 2011-11-26T22:53:19Z Indexed on 2011/11/27 2:01 UTC
Read the original article Hit count: 320

Filed under:

lisp

|

recursion

|

Scheme

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?

© Programmers or respective owner

Related posts about lisp

Why do you like Lisp ?

as seen on Programmers - Search for 'Programmers'
Why does Paul Graham advocate Lisp? Why did ITA Software choose Lisp over other High Level languages? Lisp obviously is an advantage for the AI stuff but I don't think Lisp is any faster than Java, C# or as a matter of fact faster than C. Still it is considered as a Hackers language? I am not a master… >>> More
Why is Lisp useful?

as seen on Programmers - Search for 'Programmers'
Lisp obviously is an advantage for the AI stuff but it doesn't appear to me that Lisp is any faster than Java, C#, or even C. I am not a master of Lisp, but I find it incredibly difficult to understand the advantage one would get in writing Business Software in Lisp. Yet it is considered as a hacker's… >>> More
Emacs 23.1 make error 139 in Mac OS X 10.6.3

as seen on Stack Overflow - Search for 'Stack Overflow'
When I try to compile GNU Emacs 23.1 on my machine with Mac OS X 10.6.3 I repeatedly get the following ending: Directories: /src/emacs-23.1/lisp/. /src/emacs-23.1/lisp/./calc /src/emacs-23.1/lisp/./calendar /src/emacs-23.1/lisp/./emacs-lisp /src/emacs-23.1/lisp/./emulation /src/emacs-23.1/lisp/./erc… >>> More
Why not port Linux kernel to Common Lisp?

as seen on Stack Overflow - Search for 'Stack Overflow'
Conventional wisdom states that OS kernels must be written in C in order to achieve the necessary levels of performance. This has been the justification for not using more expressive high level languages. However, for a few years now implementations of Common Lisp such as SBCL have proven to be… >>> More
Lisp Style question label local functions or not?

as seen on Stack Overflow - Search for 'Stack Overflow'
I was wondering if there is a standard practice regarding the use of labels in Lisp. I've been messing around with a Lisp implementation of the algorithm described in the first answer here http://stackoverflow.com/questions/352203/generating-permutations-lazily My current version uses labels to… >>> More

Related posts about recursion

tail recursion vs. forward recursion

as seen on Stack Overflow - Search for 'Stack Overflow'
Can someone give me the difference between these two kinds recursions and example? specifically in ocaml. Thanks >>> More
Are there advantages for using recursion over iteration - other than sometimes readability and elegance?

as seen on Programmers - Search for 'Programmers'
I am about to make two assumptions. Please correct me if they're wrong: There isn't a recursive algorithm without an iterative equivalent. Iteration is always cheaper performance-wise than recursion (at least in general purpose languages such as Java, C++, Python etc.). If it's true that recursion… >>> More
Python recursive function error: "maximum recursion depth exceeded"

as seen on Stack Overflow - Search for 'Stack Overflow'
I solved Problem 10 of Project Euler with the following code, which works through brute force: def isPrime(n): for x in range(2, int(n**0.5)+1): if n % x == 0: return False return True def primeList(n): primes = [] for i in range(2,n): if isPrime(i): … >>> More
Dynamic Programming Recursion and a sprinkle of Memoization

as seen on Stack Overflow - Search for 'Stack Overflow'
I have this massive array of ints from 0-4 in this triangle. I am trying to learn dynamic programming with Ruby and would like some assistance in calculating the number of paths in the triangle that meet three criterion: You must start at one of the zero points in the row with 70 elements. Your… >>> More
How does the recursion here work?

as seen on Stack Overflow - Search for 'Stack Overflow'
code 1: public static int fibonacci (int n){ if (n == 0 || n == 1) { return 1; } else { return fibonacci (n-1) + fibonacci (n-2); } } how can you use fibonacci if you haven't gotten done explaining what it is yet? I've been able to understand… >>> More