Functional program - write a function to rearrange an array from the middle

Question

The task is to write a function that takes a list such as (7 8 2 9 5 6) and then "unwinds" it from the center, rearranging it to be 2 9 then 2 9 8 5 then finally the end output is 2 9 8 5 7 6

I have figured out ROUGHLY the pseudocode:

• take the last element in an array A, append it to a array B in the front
• remove last element from array A
• take the first element in array A, append it to array B in the front
• remove the first element from array A

So,

7 8 2 9 5 6 ->

7 8 2 9 5 -> 6

8 2 9 5 -> 7 6

8 2 9 -> 5 7 6

2 9 -> 8 5 7 6

2 -> 9 8 5 7 6

-> 2 9 8 5 7 6 Correct final output

Here is where my code is so far (not very far at all)

(define (lastElement L) ;returns the last element of array L
 (if (null? (cdr L)) (car L)
 (lastElement (cdr L))))

(define (unwind U)
 (if (null? U) ( (cons (lastElement L) '() )) ;generates a syntax error
 (U)
  )

At my syntax error comment, what I am trying to do is.. if array U is !null, then prepend lastElement L to a new array... and then somehow from there I have to figure out how to remove lastElement L from U and then get the first element and remove that.. Which would be through car and/or cdr, I believe.

edit-- alternate possible approach?

(define (lastElement L)
 (if (null? (cdr L)) (car L)
 (lastElement (cdr L))))

(define (trim lst)
    (if (null? (cdr lst))
        '()
        (cons (car lst) (trim (cdr lst)))))

(define (first-half lst)
  (take lst (quotient (length lst) 2)))



(define (unwind U)
 (if (= (length U) 1 ) 999
  ( (lastElement (first-half U))
     (car (list-tail U (length(first-half U))))
          (unwind (cons
                   (trim (length (first-half U)))
                   (cdr (list-tail U (length(first-half U))))
                   )
                  )
  )
 )
)



(unwind '(7 8 2 9 5 6))

Answer 1

I took a classic turtle and hare recursion to split the list in half. You walk it with a cdr and cddr (cdr of the cdr) so when the faster recurring half is null or a singleton list the slower half gives you the last half of the list. I also accumulated a reversed front half of the list as it comes in handy later.

   (define (unwind L)
       (let loop ((HalfR '()) (Turtle L) (Hare L))
          (cond ((null? Hare) (interleave HalfR Turtle))
                ((null? (cdr Hare)) 
                 (cons (car Turtle) (interleave HalfR (cdr Turtle))))
                (else (loop (cons (car Turtle) HalfR)
                            (cdr Turtle)
                            (cddr Hare))))))

(define (interleave L1 l2)
  (OR (AND (null? L1) L2)   ;;**to catch cases where L1 and L2 are not equal.
      (AND (null? L2) L1)   ;;after interleaving to the extent possible. 
      (cons (car L1)        
            (cons (car L2) 
                  (interleave (cdr L1) (cdr L2)))))) 

1 ]=> (unwind '(1 1 2 3 5 8 13))
;Value 11: (3 2 5 1 8 1 13)

1 ]=> (unwind '(7 8 2 9 5 6))
;Value 12: (2 9 8 5 7 6)