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
- is tail-recursive,
- does not use
reverse, - 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),
- 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.
3
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.
4