函数式程序——写一个函数从中间重新排列一个数组
Functional program - write a function to rearrange an array from the middle
任务是编写一个函数，它接受一个列表，例如 (7 8 2 9 5 6)，然后从中心开始 "unwinds"，将其重新排列为 2 9，然后 2 9 8 5最后最终输出是 2 9 8 5 7 6
我已经大致弄清楚了伪代码：
- 取数组A的最后一个元素，追加到数组B的前面
- 从数组 A 中删除最后一个元素
- 取数组A的第一个元素，追加到数组B的前面
- 从数组 A 中删除第一个元素
所以，
7 8 2 9 5 6 -> </code></p>
<p><code>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
</code> -> <code>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 and/or 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))
这很棘手……这是一种接近您在问题中描述的方法，包括正确处理边缘情况（空列表、包含奇数个元素的列表）：
(define (unwind lst)
(let loop ((lst lst)
(acc '())
(last? #t))
(cond ((null? lst)
acc)
((null? (cdr lst))
(if last?
(append acc lst)
(cons (car lst) acc)))
(last?
(loop (drop-right lst 1)
(cons (last lst) acc)
#f))
(else
(loop (cdr lst)
(cons (car lst) acc)
#t)))))
请注意，我使用了几个内置函数来简化操作，尤其是 append, last and drop-right 过程。关键的见解是传递一个布尔标志，指示在每一步我们是否应该获取列表的第一个或最后一个元素，这甚至用于只剩下一个元素的情况。它按预期工作：
(unwind '())
=> '()
(unwind '(7 6))
=> '(7 6)
(unwind '(7 8 2 9 5 6))
=> '(2 9 8 5 7 6)
(unwind '(7 8 2 0 9 5 6))
=> '(2 9 8 5 7 6 0)
我用经典的乌龟和兔子递归将列表分成两半。你用 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)
一个更简单的解决方案是创建列表的反向副本，然后交替获取每个列表的第一个元素。停止条件是结果列表与初始列表的长度相同时：
(define (unwind lst)
(define maxlen (length lst))
(let loop ((lst1 lst) (lst2 (reverse lst)) (res null) (len 0))
(if (= len maxlen)
res
(if (even? len)
(loop lst1 (cdr lst2) (cons (car lst2) res) (add1 len))
(loop (cdr lst1) lst2 (cons (car lst1) res) (add1 len))))))
测试：
> (unwind '(1 1 2 3 5 8 13))
'(3 2 5 1 8 1 13)
> (unwind '(7 8 2 9 5 6))
'(2 9 8 5 7 6)
我想添加另一个解决方案，使用我从 Haskell 了解到的 zipper。
基本上，列表上的拉链由一个点组成，标记当前焦点，一个列表显示该点左侧的内容，另一个列表显示该点右侧的内容。
;; Creating our zipper abstraction
(define (make-zipper l p r)
"Create a zipper with what's to come left of point,
what's at point and what's right of the point."
(list l p r))
(define (zipper-point z)
"Get the point of the zipper."
(cadr z))
(define (zipper-left z)
"Get what's left of the zipper, in the order as if
the point moved to the left."
(car z))
(define (zipper-right z)
"Get what's right of the zipper."
(caddr z))
一个列表可以很容易地转换成一个带第一个元素的点的拉链：
;; Conversion into our new data type
(define (zipper-from-list l)
"Create a zipper from a (non empty) list, and
place the point at the first element."
(make-zipper '() (car l) (cdr l)))
带拉链的酷事来了：四处走动。基本上这就像 C 或 C++ 等语言中的指针。您可以向左或向右移动，并且可以修改当前指向的值（无需像使用简单列表那样进行昂贵的重建和遍历所有值）。
;; Movement on zippers.
;; (2 1) 3 (4 5)
;; move-right => (3 2 1) 4 (5)
;; move-left => (1) 2 (3 4 5)
(define (zipper-move-right z)
"Return a zipper with the point moved one to the
right."
(make-zipper
(cons (zipper-point z) (zipper-left z))
(car (zipper-right z))
(cdr (zipper-right z))))
(define (zipper-move-left z)
"Return a zipper with the point moved one to the
left."
(make-zipper
(cdr (zipper-left z))
(car (zipper-left z))
(cons (zipper-point z) (zipper-right z))))
现在我希望我的拉链为这个任务做一件特别的事情：销毁点的值并用左边或右边的值填充产生的间隙：
;; A special kind of moving, destructing the value at point.
;; (2 1) 3 (4 5)
;; zipper-squash-left => (1) 2 (4 5)
;; zipper-squash-right => (2 1) 4 (5)
(define (zipper-squash-right z)
"Squash the value at point and close the gap
with a value from right."
(make-zipper
(zipper-left z)
(car (zipper-right z))
(cdr (zipper-right z))))
(define (zipper-squash-left z)
"Squash the value at point and close the gap
with a value from left."
(make-zipper
(cdr (zipper-left z))
(car (zipper-left z))
(zipper-right z)))
添加一些无聊的测试功能...
;; Testing for the end points of the zipper.
(define (zipper-left-end? z)
"Check whether the zipper is at the left end."
(eq? '() (zipper-left z)))
(define (zipper-right-end? z)
"Check whether the zipper is at the right end."
(eq? '() (zipper-right z)))
...我们来到我的答案的核心："Pulling" 一个拉链列表。把拉链想象成绳子上的标记。当你拉动那个标记时，绳子的两部分会折叠在一起。如果绳子上有标记（即数字），您将首先看到最接近您拉动标记的标记。
;; Pull out a list from the current position of the
;; point.
(define (pull-list-from-zipper z)
"Pull out a list from the current point of the
zipper. The list will have the point as first value, followed
by the one right to it, then the one left of it, then another
one from the right and so on."
(cond
((zipper-left-end? z) (cons (zipper-point z) (zipper-right z)))
((zipper-right-end? z) (cons (zipper-point z) (zipper-left z)))
(else
(let* ((p1 (zipper-point z))
(z1 (zipper-squash-right z))
(p2 (zipper-point z1))
(z2 (zipper-squash-left z1)))
(cons p1 (cons p2 (pull-list-from-zipper z2)))))))
请注意，存在第二种变体，它首先取左值，然后取右值。
有了这个，写你的 unwind 就变得微不足道了：你把列表转换成拉链，移动到中间值，然后拉：
;; What we wanted to to.
(define (unwind l)
"Move to the mid and pull a list out of the list."
(let ((steps (quotient (- (length l) 1) 2)))
(pull-list-from-zipper
((repeated zipper-move-right steps) (zipper-from-list l)))))
性能方面，这需要完整遍历列表，加上将拉链移动一半的距离，当然拉出一个新列表将在 O(n) 中。上面的代码没有针对性能（尾递归..）进行优化，而是为了便于理解。
一个完整的例子是here。
最后一点，拉链可以在没有点值的情况下实现，但是点在两个值之间（例如，在 emacs 中完成），但我想保持接近Haskell 版本。
任务是编写一个函数，它接受一个列表，例如 (7 8 2 9 5 6)，然后从中心开始 "unwinds"，将其重新排列为 2 9，然后 2 9 8 5最后最终输出是 2 9 8 5 7 6
我已经大致弄清楚了伪代码：
- 取数组A的最后一个元素，追加到数组B的前面
- 从数组 A 中删除最后一个元素
- 取数组A的第一个元素，追加到数组B的前面
- 从数组 A 中删除第一个元素
所以，
7 8 2 9 5 6 -> </code></p>
<p><code>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
</code> -> <code>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 and/or 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))
这很棘手……这是一种接近您在问题中描述的方法，包括正确处理边缘情况（空列表、包含奇数个元素的列表）：
(define (unwind lst)
(let loop ((lst lst)
(acc '())
(last? #t))
(cond ((null? lst)
acc)
((null? (cdr lst))
(if last?
(append acc lst)
(cons (car lst) acc)))
(last?
(loop (drop-right lst 1)
(cons (last lst) acc)
#f))
(else
(loop (cdr lst)
(cons (car lst) acc)
#t)))))
请注意，我使用了几个内置函数来简化操作，尤其是 append, last and drop-right 过程。关键的见解是传递一个布尔标志，指示在每一步我们是否应该获取列表的第一个或最后一个元素，这甚至用于只剩下一个元素的情况。它按预期工作：
(unwind '())
=> '()
(unwind '(7 6))
=> '(7 6)
(unwind '(7 8 2 9 5 6))
=> '(2 9 8 5 7 6)
(unwind '(7 8 2 0 9 5 6))
=> '(2 9 8 5 7 6 0)
我用经典的乌龟和兔子递归将列表分成两半。你用 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)
一个更简单的解决方案是创建列表的反向副本，然后交替获取每个列表的第一个元素。停止条件是结果列表与初始列表的长度相同时：
(define (unwind lst)
(define maxlen (length lst))
(let loop ((lst1 lst) (lst2 (reverse lst)) (res null) (len 0))
(if (= len maxlen)
res
(if (even? len)
(loop lst1 (cdr lst2) (cons (car lst2) res) (add1 len))
(loop (cdr lst1) lst2 (cons (car lst1) res) (add1 len))))))
测试：
> (unwind '(1 1 2 3 5 8 13))
'(3 2 5 1 8 1 13)
> (unwind '(7 8 2 9 5 6))
'(2 9 8 5 7 6)
我想添加另一个解决方案，使用我从 Haskell 了解到的 zipper。
基本上，列表上的拉链由一个点组成，标记当前焦点，一个列表显示该点左侧的内容，另一个列表显示该点右侧的内容。
;; Creating our zipper abstraction
(define (make-zipper l p r)
"Create a zipper with what's to come left of point,
what's at point and what's right of the point."
(list l p r))
(define (zipper-point z)
"Get the point of the zipper."
(cadr z))
(define (zipper-left z)
"Get what's left of the zipper, in the order as if
the point moved to the left."
(car z))
(define (zipper-right z)
"Get what's right of the zipper."
(caddr z))
一个列表可以很容易地转换成一个带第一个元素的点的拉链：
;; Conversion into our new data type
(define (zipper-from-list l)
"Create a zipper from a (non empty) list, and
place the point at the first element."
(make-zipper '() (car l) (cdr l)))
带拉链的酷事来了：四处走动。基本上这就像 C 或 C++ 等语言中的指针。您可以向左或向右移动，并且可以修改当前指向的值（无需像使用简单列表那样进行昂贵的重建和遍历所有值）。
;; Movement on zippers.
;; (2 1) 3 (4 5)
;; move-right => (3 2 1) 4 (5)
;; move-left => (1) 2 (3 4 5)
(define (zipper-move-right z)
"Return a zipper with the point moved one to the
right."
(make-zipper
(cons (zipper-point z) (zipper-left z))
(car (zipper-right z))
(cdr (zipper-right z))))
(define (zipper-move-left z)
"Return a zipper with the point moved one to the
left."
(make-zipper
(cdr (zipper-left z))
(car (zipper-left z))
(cons (zipper-point z) (zipper-right z))))
现在我希望我的拉链为这个任务做一件特别的事情：销毁点的值并用左边或右边的值填充产生的间隙：
;; A special kind of moving, destructing the value at point.
;; (2 1) 3 (4 5)
;; zipper-squash-left => (1) 2 (4 5)
;; zipper-squash-right => (2 1) 4 (5)
(define (zipper-squash-right z)
"Squash the value at point and close the gap
with a value from right."
(make-zipper
(zipper-left z)
(car (zipper-right z))
(cdr (zipper-right z))))
(define (zipper-squash-left z)
"Squash the value at point and close the gap
with a value from left."
(make-zipper
(cdr (zipper-left z))
(car (zipper-left z))
(zipper-right z)))
添加一些无聊的测试功能...
;; Testing for the end points of the zipper.
(define (zipper-left-end? z)
"Check whether the zipper is at the left end."
(eq? '() (zipper-left z)))
(define (zipper-right-end? z)
"Check whether the zipper is at the right end."
(eq? '() (zipper-right z)))
...我们来到我的答案的核心："Pulling" 一个拉链列表。把拉链想象成绳子上的标记。当你拉动那个标记时，绳子的两部分会折叠在一起。如果绳子上有标记（即数字），您将首先看到最接近您拉动标记的标记。
;; Pull out a list from the current position of the
;; point.
(define (pull-list-from-zipper z)
"Pull out a list from the current point of the
zipper. The list will have the point as first value, followed
by the one right to it, then the one left of it, then another
one from the right and so on."
(cond
((zipper-left-end? z) (cons (zipper-point z) (zipper-right z)))
((zipper-right-end? z) (cons (zipper-point z) (zipper-left z)))
(else
(let* ((p1 (zipper-point z))
(z1 (zipper-squash-right z))
(p2 (zipper-point z1))
(z2 (zipper-squash-left z1)))
(cons p1 (cons p2 (pull-list-from-zipper z2)))))))
请注意，存在第二种变体，它首先取左值，然后取右值。
有了这个，写你的 unwind 就变得微不足道了：你把列表转换成拉链，移动到中间值，然后拉：
;; What we wanted to to.
(define (unwind l)
"Move to the mid and pull a list out of the list."
(let ((steps (quotient (- (length l) 1) 2)))
(pull-list-from-zipper
((repeated zipper-move-right steps) (zipper-from-list l)))))
性能方面，这需要完整遍历列表，加上将拉链移动一半的距离，当然拉出一个新列表将在 O(n) 中。上面的代码没有针对性能（尾递归..）进行优化，而是为了便于理解。
一个完整的例子是here。
最后一点，拉链可以在没有点值的情况下实现，但是点在两个值之间（例如，在 emacs 中完成），但我想保持接近Haskell 版本。