Scheme拆分操作不起作用

Question

我是计划的新手,在调试代码时遇到了一些麻烦.

; 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正在失去中间价值,但我一次又一次地检查它,它似乎失去了中间价值.似乎一个简单的解决方案是摆脱它(+ 1),(+ (/ (length L) 2) 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

你知道乌龟和野兔算法吗？乌龟走在名单上,野兔以双倍的速度奔跑.当野兔到达列表的末尾时,分裂发生在乌龟的位置.这是大部分代码; 我会告诉你剩下的事情:

(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是乌龟已经检查过的物品清单,顺序相反.

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