如何在球拍(方案)中将列表分成均匀大小的块? [英] How to split list into evenly sized chunks in Racket (Scheme)?

问题描述

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

Example:
How to convert list:
'(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))

Into list of lists:
'((0 1 2 3) (4 5 6 7) (8 9 10 11) (12 13 14 15))

根据到目前为止提供的答案，这是我想出的:

Based on answers provided here so far, this is what I've come up with:

第一个定义函数，从列表的开头开始占用'n'个元素:

First define function to take up to 'n' elements from beginning of the list:

(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 '()))

第二个与其余列表类似的功能:

Second is similar function for the rest of list:

(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'可以产生相同的结果，但是我是通过练习来完成的.

This could have been done as one function that returns two values and Racket has a function 'split-at' that produces same result, but I did this as an exercise.

ps.这是尾递归的正确使用吗?

ps. Is this correct use of tail recursion ?

像这样分割成块可以写成这样:

Than split-into-chunks can be written like this:

(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.可以进一步改善它还是足够好"?

pps. Can this one be improved even more or is it 'good enough' ?

推荐答案

Scheme中有一个常见的实用程序功能，位于

There's a common utility function in Scheme, in the SRFI-1 library (which Racket offers, but I don't recall how to import it), called take, which takes the initial n elements from a list:

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

同一库中还有一个名为drop的函数，该函数从列表中删除了初始的n元素:

There is also in the same library a function called drop which removes the initial n elements from a list:

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

您可以通过使用此类功能将问题分解为较小的部分.因此，解决您的问题的第一个(但不正确)近似是:

You can break down the problem into smaller pieces by using functions like these. So, a first (but incorrect) approximation to solving your problem would be this:

(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)))))

但是，正如我所指出的，这种解决方案是次优的.为什么?因为当列表xs的元素少于n时，(take n xs)会给您一个错误；转换为您的问题，如果列表包含非n多个元素，则会出现错误.但是，您可以通过编写一对函数take-up-to和drop-up-to来解决此问题，这些函数的作用与take和drop相似，但不存在问题.因此，这些函数的示例用法如下:

As I noted, however, this solution is suboptimal. Why? Because (take n xs) gives you an error when the list xs has fewer than n elements; translated to your problem, if the list has a non-n multiple of elements you get an error. However, you can fix this by writing a pair of functions, take-up-to and drop-up-to that work like take and drop but don't have that problem. So example usage of the functions would look like this:

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

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

这就是我要告诉你的.我建议您做这些事情:

This is as much as I'm going to tell you. I suggest you do these things:

• 编写自己的take，drop，take-up-to和drop-up-to的实现，并使用它们编写要尝试实现的功能.
• 通过 SRFI-1库的文档略过并熟悉自己了解那里的功能.这些列表中的许多问题都分解为这些功能的简单组合，因此您想了解它们.
• 了解如何将此库导入Racket. (无法在那帮您.)
• 作为练习，请尝试编写一些SRFI-1函数的自己的实现. (为便于练习，可以将它们简化一些；例如，尽管其中许多功能将处理多个列表参数，但出于练习目的，编写只处理一个列表的版本也是可以的.)

• Write your own implementations of take, drop, take-up-to and drop-up-to, and use them to write the function you're trying to implement.
• Skim through the documentation for the SRFI-1 library and familiarize yourself with what the functions there do. A lot of these list problems break down into easy combinations of these functions, so you want to know about them.
• Learn how to import this library into Racket. (Can't help you there.)
• As an exercise, try your hand at writing your own implementations of some of the SRFI-1 functions. (It's OK to simplify them a bit for the sake of the exercise; for example, while many of these functions will deal with multiple list arguments, it's OK for exercise purposes to write a version that deals with just one list.)

编辑:这是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)))))

仅使用尾部调用(可以在恒定的空间中运行)，就可以在此基础上进行一些改进.那是另一项练习.

It's possible to improve on this still some more to use only tail calls (and thus run in constant space). That's left as yet another exercise.

这篇关于如何在球拍(方案)中将列表分成均匀大小的块?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！