方案：将列表拆分为偶数和奇数位置的两个子列表的列表

Question

我正在尝试使用直接递归将列表排序为偶数和奇数位置的子列表。

So (split '(1 2 3 4 5 6)) returns ((1 3 5) (2 4 6))

and (split '(a 2 b 3)) returns ((a b) (2 3))

到目前为止，我有以下代码：

(define split
  (lambda (ls)
    (if (or (null? ls) (null? (cdr ls))) 
        (values ls '())
        (call-with-values
          (lambda () (split (cddr ls)))
          (lambda (odds evens)
            (values (cons (car ls) odds)
                    (cons (cadr ls) evens)))))))

但是，现在我对如何将多个输出存储到一个列表中感到困惑。

我知道这样称呼它：

(call-with-values (lambda () (split '(a b c d e f))) list)

returns 是一个子列表列表，但是我希望函数本身是 return 一个子列表列表。有没有更好的方法来做到这一点，而不涉及使用值和调用值？

Answer 1

当然可以。这是您的代码的改编版本：

(define (split ls)
  (if (or (null? ls) (null? (cdr ls)))
      (list ls '())
      (let ((next (split (cddr ls))))
        (list (cons (car ls) (car next))
              (cons (cadr ls) (cadr next))))))

Answer 2

我喜欢问题中的代码的一件事是它以反映规范的方式使用 odds 和 evens。

此解决方案的目标是：

可读性。
在代码中体现规范的语言。
在执行过程中使用 O(n) space。

它使用带有累加器和蹦床的内部函数。

#lang racket

;; List(Any) -> List(List(Any) List(Any))
(define (split list-of-x)

  (define end-of-list (length list-of-x))

  ;;  List(Any) List(Any) List(Any) Integer -> List(List(Any) List(Any))
  (define (looper working-list odds evens index)
    (cond [(> index end-of-list)
           (list (reverse odds)
                 (reverse evens))]
          [(odd? index)
           (looper (rest working-list)
                   (cons (car working-list) odds)
                   evens
                   (add1 index))]
          [(even? index)
           (looper (rest working-list)
                   odds
                   (cons (car working-list) evens)
                   (add1 index))]
          [else
           (error "split: unhandled index condition")]))

  (looper list-of-x null null 1))

Answer 3

如果您熟悉 match 语法，这里的答案应该很清楚。它在形式和功能上与 Chris Jester-Young 的回答相同，但使用 match 来阐明列表操作。

#lang racket

(define (split ls)
  (match ls
    [`(,first ,second ,rest ...) 
     (match (split rest)
       [`(,evens ,odds) (list (cons first evens)
                              (cons second odds))])]
    [_ (list ls '())]))

Answer 4

(: split ((list-of natural) -> (list-of (list-of natural))))
(define split
  (lambda (xs)
    (list (filter even? xs) (filter odd? xs))))

(: filter ((%a -> boolean) (list-of %a) -> (list-of %a)))
(define filter
  (lambda (p xs)
   (fold empty (lambda (first result)
                   (if (p first)
                       (make-pair first result)
                       result)) xs)))

(check-expect (split (list 1 2 3 4 5 6)) (list (list 2 4 6) (list 1 3 5)))

我觉得这个也很好理解..

方案：将列表拆分为偶数和奇数位置的两个子列表的列表

Scheme: Split list into list of two sublists of even and odd positions

scheme

racket