How to break a list into pieces with uniform size in Racket (Scheme)?

Question

Example:
How to convert a list:
'' (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)

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

Based on the answers so far presented here, this is what I came up with:

First define a function to go to the 'n' elements from the 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 '())) 

A second similar function for the rest of the 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 '())) 

This could be done as a single function that returns two values, and Racket has a split-at function that gives the same result, but I did it as an exercise.

ps. Is tail recursion used correctly?

Than divided into pieces 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))))) 

SFC. Could this be improved further or is it "good enough"?

Answer 1

There is a general utility function in Scheme, in the SRFI-1 library (which Racket offers, but I don’t remember how to import it), called take , which takes the original n elements from the list:

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

In the same library there is a function called drop , which removes the original elements n from the list:

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

You can break the problem into smaller parts using such functions. So, the first ( but incorrect ) approximation to solving your problem will be as follows:

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

As I already noted, this solution is suboptimal. What for? Since (take n xs) gives you an error message if the list xs fewer n elements; translates to your problem, if the list has not n multiple items, you get an error. However, you can fix this by writing a couple of take-up-to and drop-up-to functions that work like take and drop but don't have this problem. Therefore, an example of the use of functions will 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 tell you. I suggest you do the following:

• Write your own implementations of take , drop , take-up-to and drop-up-to and use them to write the function you are trying to implement.
• Compile the documentation for the SRFI-1 library and see what functions are performed there. Many of these list problems are broken down into simple combinations of these functions, so you want to know about them.
• Learn how to import this library into Racket. (I can't help you there.)
• As an exercise, try your hand at writing your own implementations of certain SRFI-1 functions. (It’s normal to simplify them for the sake of exercise, for example, although many of these functions will deal with multiple list arguments, in order to use a version that deals with only one list.)

EDIT: Here's a simple take-up-to implementation:

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

It is possible to improve this a bit more so that only tail calls are used (and therefore work in a constant space). This left another exercise.

Answer 2

You ask a good general question, but I think what you want here is what uses byte strings, not lists. Here's some code (including error checking) as well as a test case:

 #lang racket (require rackunit) ;; given a byte string, split it into a vector of byte-strings ;; of length 4 (define (split-bytes bytes) (define len (bytes-length bytes)) (unless (= 0 (modulo len 4)) (raise-type-error 'split-bytes "byte string of length divisible by 4" 0 bytes)) (for/vector ([i (in-range (/ len 4))]) (subbytes bytes (* 4 i) (* 4 (add1 i))))) (check-equal? (split-bytes #"hhoh.h9ew,n49othsv97") (vector #"hhoh" #".h9e" #"w,n4" #"9oth" #"sv97")) 

Answer 3

as for me it's something like

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

eg

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

gives

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

Answer 4

If you want to improve the solution to such problems, I highly recommend The Little Schemer . He will teach you to think in terms that will make these problems obedient, and it takes only a few hours to complete all of this. Cover-cover.

Answer 5

Another way to do this is to provide a higher-order function-n-function that takes n values ​​from a list and applies the function to them:

 (define (map-n n fn l . lists) (if (any (lambda(l)(< (length l) n)) (cons l lists)) '() (cons (apply fn (append-map (lambda(l)(take ln)) (cons l lists))) (apply map-n n fn (map (lambda(l)(drop ln)) (cons l lists)))))) (eg (map-n 4 + '(1 2 3 4 5 6 7 8)) ===> (10 26)) (eg (map-n 3 (lambda (abc) a) '(1 2 3 4 5 6)) ===> (1 4)) 

With this feature, you can simply

 (define (split-by nl) (map-n n list l)) 

The disadvantage may be that if the list length is not divisible by n, the remainder will be rejected from the result.

Another interesting way is to create a function that splits the list into pieces of arbitrary size:

 (define (chunk-list l . chunk-sizes) (assert (and (list? l) (every natual? chunk-sizes) (<= (fold + 0 chunk-sizes) (length l)))) (let loop ((result '()) (sizes chunk-sizes) (rest l)) (match sizes (() (reverse result)) ((size . sizes) (let-values (((this rest) (split-at rest size))) (loop `(,this ,@result) sizes rest)))))) (eg (chunk-list '(1 2 3 4 5 6 7 8 9 10) 0 1 2 3 4) ===> (() (1) (2 3) (4 5 6) (7 8 9 10)) 

and then define split-by with make-list:

 (define (split-by nl) (let ((size (quotient (length l) n))) (apply chunk-list l (make-list size n)))) 

Note that the map-n definition uses the any function from srfi-1 , and the chunk-list uses Alex Shinn pattern matching (although it could be easily rewritten using plain if, eq ?, car and cdr)

Answer 6

If you are looking for a solution with a recursive tail, one way is to use the let name:

 (define (group n xs) (let loop ([grouped '()] [xs xs]) (if (empty? xs) (reverse grouped) (loop (cons (take xs n) grouped) (drop xs n))))) 

However, this fails if xs has the remaining elements, so we need to add a case that checks this:

 (define (group n xs) (let loop ([grouped '()] [xs xs]) (cond [(empty? xs) (reverse grouped)] [(<= (length xs) n) (loop (cons xs grouped) '())] [else (loop (cons (take xs n) grouped) (drop xs n))]))) 

It works, but we can do better. The problem is that the calculation (length xs) is done in linear time, because the only way to find the length of a simple list is the whole list. Since this is inside a loop that executes several times in proportion to the size of xs , this code works in quadratic time, when it just needs to be executed in linear time. We can get around this problem by calculating the length xs once, and then subtracting n from it every iteration:

 (define (group n xs) (let loop ([grouped '()] [xs xs] [l (length xs)]) (cond [(empty? xs) (reverse grouped)] [(<= ln) (loop (cons xs grouped) '() 0)] [else (loop (cons (take xs n) grouped) (drop xs n) (- ln))]))) 

And we will return to linear time, while maintaining tail recursion and, therefore, constant space. However, there is another improvement. The Racket split-at function combines the take and drop functions and returns both lists as two values. To use functions with multiple values, we can use let-values :

 (define (group n xs) (let loop ([grouped '()] [xs xs] [l (length xs]) (cond [(empty? xs) (reverse grouped)] [(<= ln) (loop (cons xs grouped) '() 0)] [else (let-values ([(taken dropped) (split-at xs n)]) (loop (cons taken grouped) dropped (- ln)))]))) 

This is a little faster because split-at can avoid repeated work by ignoring the first n elements in drop its functionality, since these elements will already be consumed by take . However, this code does not account for bad user input. If the user supplies n more than the length xs , he throws an error when he should return (list xs) . It's simple enough to check, but our code is terribly expanding to the right with all this socket. In addition to checking for this, we can split the loop into an internally defined function:

 (define (group n xs) (define (loop grouped xs l) (cond [(empty? xs) (reverse grouped)] [(<= ln) (loop (cons xs grouped) '() 0)] [else (let-values ([(taken dropped) (split-at xs n)]) (loop (cons taken grouped) dropped (- ln)))])) (let ([l (length xs)]) (if (>= nl) (list xs) (loop '() xs l)))) 

This function is tail recursive, does not calculate (length xs) more than once, ensures that (group 4 '(1 2 3)) evaluates to '((1 2 3)) , and an uneven grouping such that (group 2 '(1 2 3) is evaluated to '((1 2) (3)) , working in linear time and constant space.