split-by.lisp

; https://stackoverflow.com/a/25264944/69545

; ================================================================
; This is the usual evolution

; 1) simple recursive version
; 2) more efficient tail-recursive version
; 3) efficient loop



; ================================================================
; First improved version

; * Don't use EQ to compare numbers, here we use ZEROP and PLUSP
; * ASSERT instead of ERROR allows interactive repair of the provided list
; * TAKE and DROP replaced with built-in SUBSEQ
; * LIST parameter is first in the parameter list
; * FORMAT is not needed for ERROR and ASSERT, they already support format strings.

; Problems
; * limited recursion by stack size
; * each iteration checks the length

(defun split-by (list n &aux length)

"splits a list into multiple lists of length n.

Parameters:
  * list - the list to be split
  * n    - the size of the lists it should be broken into.

Returns:
 A list of smaller lists of the specified length (or signals an error).

Examples:
  (split-by '(1 2 3 4) 2)   ; => ((1 2) (3 4))
  (split-by '(1 2 3)   2)   ; => not evenly divisible"

  (assert (zerop (mod (setf length (length list)) n))
      (list)
    "list is not evenly divisible by ~A: ~A" n list)
 
  (if (plusp length)
      (cons (subseq list 0 n)
            (split-by (subseq list n) n))
    '()))


; ================================================================
; Second improved version

; * replace recursion with tail recursion
; * ASSERT and LENGTH are called only once

; Problems:
; * tail recursion optimization is not required in Common Lisp
; * needs a reverse at the end

(defun split-by (list n)

"splits a list into multiple lists of length n.

Parameters:
  * list - the list to be split
  * n    - the size of the lists it should be broken into.

Returns:
 A list of smaller list of the specified length (or signals an error).

Examples:
  (split-by '(1 2 3 4) 2)   ; => ((1 2) (3 4))
  (split-by '(1 2 3)   2)   ; => not evenly divisible"

  (assert (zerop (mod (length list) n))
      (list)
    "list is not evenly divisible by ~A: ~A" n list)

  (labels ((split-by-aux (list result)
             (if list
                 (split-by-aux (subseq list n)
                               (cons (subseq list 0 n)
                                     result))
               result)))
    (nreverse (split-by-aux list '()))))


; ================================================================
; Third improved version

; replace tail recursion with a LOOP
; REVERSE no longer needed

(defun split-by (list n)

"splits a list into multiple lists of length n.

Parameters:
  * list - the list to be split
  * n    - the size of the lists it should be broken into.

Returns:
 A list of smaller list of the specified length (or signals an error).

Examples:
  (split-by '(1 2 3 4) 2)   ; => ((1 2) (3 4))
  (split-by '(1 2 3)   2)   ; => not evenly divisible"

  (assert (zerop (mod (length list) n))
      (list)
    "list is not evenly divisible by ~A: ~A" n list)

  (loop while list
        collect (loop repeat n
                      collect (pop list))))