Tail-recursive implementation of take-while

Question

I am trying to write a tail-recursive implementation of the function take-while in Scheme (but this exercise can be done in another language as well). My first attempt was

(define (take-while p xs)
 (if (or (null? xs)
 (not (p (car xs))))
 '()
 (cons (car xs) (take-while p (cdr xs)))))

which works correctly but is not tail-recursive. My next attempt was

(define (take-while-tr p xs)
 (let loop ((acc '())
 (ys xs))
 (if (or (null? ys)
 (not (p (car ys))))
 (reverse acc)
 (loop (cons (car ys) acc) (cdr ys)))))

which is tail recursive but needs a call to reverse as a last step in order to return the result list in the proper order.

I cannot come up with a solution that

1. is tail-recursive,
2. does not use reverse,
3. only uses lists as data structure (using a functional data structure like a Haskell's sequence which allows to append elements is not an option),
4. has complexity linear in the size of the prefix, or at least does not have quadratic complexity (thanks to delnan for pointing this out).

Is there an alternative solution satisfying all the properties above? My intuition tells me that it is impossible to accumulate the prefix of a list in a tail-recursive fashion while maintaining the original order between the elements (i.e. without the need of using reverse to adjust the result) but I am not able to prove this.

Note

The solution using reverse satisfies conditions 1, 3, 4.

• user7043: Well, you can append to the end of the accumulator list at every step, but that takes quadratic time rather than linear, which makes it offensively stupid.
• Giorgio: @delnan: Maybe I should add this as an extra condition. Of course, using reverse you still have linear complexity, while appending at each steps makes the complexity quadratic.
• WuHoUnited: I'm going to agree that this should not be possible. With the other conditions, I think using reverse is the best you can do since it is big-o linear time and memory (proportional to the prefix which is the best you can do). Also since you're not producing a lazy sequence, the call to reverse is not making something eager which otherwise wouldn't have been.

Answer 1

Hmm, some cleverness continuations might work

First we write a function which takes a continuation, and returns a new continuation which cons a value onto the result

(define cons-later
 (lambda (c x)
 (lambda (r)
 (cons x (c r)))))

Now take-while

(define take-while
 (lambda (pred xs)
 (define worker
 (lambda (c xs)
 (if (pred (car xs))
 (worker (cons-later c (car xs)) ; Make our new continuation
 (cdr xs)) 
 (c '())))) ; Call the continuation
 (worker (lambda (x) x) xs)))

We still pay the piper at some point though; this version takes up a bit more room than with reverse.

This uses functions of course, but since your reverse implementation did and was still counted as satisfying 1 3 and 4 I'll just innocently whistle.

• Giorgio: Very interesting (and, IMHO, elegant) solution. Somehow it confirms my intuition that one needs some temporary memory to accumulate the partial prefixes: in your solution this is achieved by building nested continuations; in the non-tail-recursive solution this is achieved by using the stack; in the tail-recursive solution this is achieved by storing a temporary list that is reversed at the end. But it is not possible to output and forget each element of the result as we scan the prefix.
• daniel gratzer: @Giorgio Indeed I'm flummoxed how to get something to that effect
• Giorgio: I would like to discuss the topic in chat if you are interested (and if you can find the link to the chat).
• daniel gratzer: @Giorgio I just got that :/ If you're still online I'm happy to discuss this in chat :)