Return to 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, 2, 4.

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.

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 (the solution using reverse satisfies this condition), 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.

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, 2, 4.

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).

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.

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 (the solution using reverse satisfies this condition), 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.