How to split list into evenly sized chunks in Racket (Scheme)?

Question

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

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

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. 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. Can this one be improved even more or is it 'good enough' ?

Answer 1

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)

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

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:

• 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.)

EDIT: Here's simple implementation of 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.