问题描述
示例:
如何转换清单:
'(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中有一个常见的实用程序功能,位于 SRFI-1库(Racket提供,但我不记得如何导入它),称为take
,它从列表中获取初始的n
元素:
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
anddrop-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.
这篇关于如何在球拍(方案)中将列表分成均匀大小的块?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!