Tail-recursive implementation of take-while
- by Giorgio
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.
