如何在Racket(Scheme)中将列表拆分为大小均匀的块？

Question

示例:
如何转换列表:
'(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)

列入名单:
'((0 1 2 3)(4 5 6 7)(8 9 10 11)(12 13 14 15))

根据目前为止提供的答案,这就是我提出的:

首先定义从列表的开头接受'n'个元素的函数:

(define (take-up-to n xs)
  (define (iter xs n taken)
    (cond
      [(or (zero? n) (empty? xs)) (reverse taken)]
      [else (iter (cdr xs) (- n 1) (cons (car xs) taken))]))
  (iter xs n '()))

第二个是列表其余部分的类似功能:

(define (drop-up-to n xs)
  (define (iter xs n taken)
    (cond
      [(or (zero? n) (empty? xs)) xs]
      [else (iter (cdr xs) (- n 1) (cons (car xs) taken))]))
  (iter xs n '()))

这可以作为一个返回两个值的函数完成,而Racket有一个函数'split-at',它产生相同的结果,但我这样做是一个练习.

PS.这是正确使用尾递归吗？

分裂成块可以像这样写:

(define (split-into-chunks n xs)
  (if (null? xs)
      '()
      (let ((first-chunk (take-up-to n xs))
            (rest-of-list (drop-up-to n xs)))
        (cons first-chunk (split-into-chunks n rest-of-list)))))

PPS.这个可以进一步改善还是"足够好"？

Answer 1

Scheme中有一个常见的实用工具函数,在SRFI-1库(Racket提供,但我不记得如何导入它)中,调用take它n从列表中获取初始元素:

(take 4 '(0 1 2 3 4 5 6 7 8))
=> '(0 1 2 3)

在同一个库中还有一个函数调用drop,它n从列表中删除初始元素:

(drop 4 '(0 1 2 3 4 5 6 7 8))
=> '(4 5 6 7 8)

您可以使用这些函数将问题分解为更小的部分.因此,解决问题的第一个(但不正确的)近似值是这样的:

(define (split-into-chunks n xs)
  (if (null? xs)
      '()
      (let ((first-chunk (take n xs))
            (rest (drop n xs)))
        (cons first-chunk (split-into-chunks n rest)))))

然而,正如我所指出的,这种解决方案并不是最理想的.为什么？因为(take n xs)当列表xs少于n元素时会给你一个错误; 转换为您的问题,如果列表中有n多个元素,则会出现错误.但是,您可以通过写一对函数,解决这一问题take-up-to及drop-up-to类似的工作take和drop,但不存在这样的问题.因此,函数的示例用法如下所示:

(take-up-to 4 '(0 1 2))
=> '(0 1 2)

(drop-up-to 4 '(0 1 2))
=> '()

这就像我要告诉你的那样多.我建议你做这些事情:

• 写你自己的实现take,drop,take-up-to和drop-up-to,并用它们来写你想实现的功能.
• 浏览SRFI-1库的文档,熟悉其中的功能.很多这些列表问题都分解为这些函数的简单组合,因此您需要了解它们.
• 了解如何将此库导入Racket.(在那里帮不了你.)
• 作为练习,请尝试编写自己的一些SRFI-1函数的实现.(为了练习,可以稍微简化它们;例如,虽然这些函数中的许多函数将处理多个列表参数,但是为了练习,可以编写仅处理一个列表的版本.)

编辑:这里的简单实现take-up-to:

(define (take-up-to n xs)
  (if (or (zero? n) (null? xs))
      '()
      (cons (car xs) (take-up-to (- n 1) (cdr xs)))))

有可能仅使用尾部调用(因此在恒定空间中运行)进一步改进.这是另一项练习.

Answer 2

对我来说，就像

(define (split-by lst n)
   (if (not (empty? lst))
       (cons (take lst n) (split-by (drop lst n) n))
       '() ))

例如

(split-by '(3 2 1 43 54 25 100 -14 -42) 3)

产量

'((3 2 1) (43 54 25) (100 -14 -42))