list - 方案拆分操作不起作用

Question

我是 scheme 的新手，在调试我的代码时遇到了一些问题。

; returns number of elements in a list
(define (length L)
  (cond ((null? L) 0)
        (else (+ (length (cdr L)) 1))))

; split the list in half:
; returns ((first half)(second half))
(define (split L)
  (cond 
    ((= (length L) 0) (list L L) )
    ((= (length L) 1) (list L '() ))
    (else 
      (list (sublist L 1 (/ (length L) 2) 1)
            (sublist L (+ (/ (length L) 2) 1) (length L) 1)))))

; extract elements start to end into a list
(define (sublist L start end counter)
  (cond ((null? L) L)
        ((< counter start) (sublist (cdr L) start end (+ counter 1)))
        ((> counter end) '())
        (else (cons (car L) (sublist (cdr L) start end (+ counter 1))))))

对我来说，这感觉就像是将一个列表拆分为两个子列表。可能有更简单的方法来执行此操作，如果这看起来很麻烦，我深表歉意。

不管怎样，结果:

Expected: (split '(1 2 3 4 5)) = ('(1 2) '(3 4 5))
Actual:  (split '(1 2 3 4 5)) = ('(1 2) '(4 5))

很明显length或者split是丢中间值，但是我查了一遍又一遍好像是丢中间值。似乎一个简单的解决方案是摆脱 (+ (/(length L) 2) 1) 的 (+ 1) 但这似乎违反直觉我，作为:

Assume L = '(1 2 3 4 5), (/ (length L) 2) = 2, and (+ (/ (length L) 2) 1) = 3
(sublist L 1 (2) 1) = '(1 2)
(sublist L (3) 5 1) = '(3 4 5)
** I put parens around the 2 and 3 to indicate that they were length calculations.

显然我所做的假设是错误的，或者我忽略了一些微不足道的事情。

提前致谢!

Answer 1

你知道龟兔赛跑算法吗？乌龟走单子(monad)，兔子以双倍速度跑单子(monad)。当兔子到达列表末尾时， split 发生在乌龟的位置。这是大部分代码；我会让你弄清楚剩下的:

(define (split xs)
  (let loop ((ts xs) (hs xs) (zs (list)))
    (if (or (null? hs) (null? (cdr hs)))
        (values (reverse zs) ts)
        (loop ...))))

这里ts是乌龟剩下的要检查的项目列表，hs是兔子剩下的要检查的项目列表，zs是乌龟已经检查过的项目列表，倒序。

请注意，您永远不需要计算输入列表中的项目。