functional-programming - 函数式程序——写一个函数从中间重新排列一个数组

Question

任务是编写一个函数，它接受一个列表，例如 (7 8 2 9 5 6)，然后从中心“展开”它，将其重新排列为 2 9 然后是 2 9 8 5 最后输出是 2 9 8 5 7 6

我已经大致弄清楚了伪代码:

• 取出数组A中的最后一个元素，将其追加到数组B的前面
• 从数组 A 中移除最后一个元素
• 取出数组A的第一个元素，将其追加到数组B的前面
• 从数组A中移除第一个元素

所以，

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 正确的最终输出

这是我的代码到目前为止的位置(根本不是很远)

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

在我的语法错误评论中，我想做的是..如果 array U 是 !null，那么在 lastElement L 前面加上到一个新数组...然后不知何故我必须弄清楚如何从 U 中删除 lastElement L 然后获取第一个元素并将其删除..哪个我相信会通过 car 和/或 cdr。

编辑——替代可能的方法？

(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

我采用经典的乌龟和兔子递归将列表分成两半。你用 cdr 和 cddr(cdr 的 cdr)来遍历它，所以当更快的循环一半为空时或单例列表较慢的一半为您提供列表的后半部分。我还积累了列表的前半部分，因为它稍后会派上用场。

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