CODEWITHSUNDEEP
listcommon-lisp
Martin Buchmann
Martin Buchmann

Reputation: 1231

Splitting a list of a-lists into sub-lists

For a hobby project I deal with lists of a-lists like

((0 . 0) (0 . 1) (0 . 3) (0 . 4) (0 . 7) (0 . 8))

where the list could have up to nine elements and the a-lists consists of just integers from 0 to 9. I want to split the list into the sub-units with consecutive cdrs.

(((0 . 0) (0 . 1)) ((0 . 3) (0 . 4)) ((0 . 7) (0 . 8)))

A sub-unit can have just one element and the list can have no sub-unit at all, like:

((0 . 0) (0 . 1) (0 . 2) (0 . 4)) or ((0 . 0) (0 . 1) (0 . 2) (0 . 3) (0 . 4))

The results should be:

(((0 . 0) (0 . 1)) ((0 . 3) (0 . 4)) ((0 . 7) (0 . 8)))

(((0 . 0) (0 . 1) (0 . 2)) ((0 . 4)))

(((0 . 0) (0 . 1) (0 . 2) (0 . 3) (0 . 4)))

Using iterate I came up with a two-step approach. First, scan the list and check whether there are sub-units or not, returning the positions of the gaps. And second, split the list apart using a function split-at I implemented before:

(defun split-at (count original-list)
  (unless (or (null original-list) (minusp count)
              (>= count (length original-list)))
    (list (subseq original-list 0 count)
          (subseq original-list count))))

(defun sub-units (units)
  "Scan UNITS for sub-units."
  (iter
    (for (a . b) in units)
    (for last-b previous b initially -1)
    (for pos from 0)
    (unless (= 1 (- b last-b))
      (collecting pos))))

(defun split-sub-units (units)
  "Splits UNITS into its sub-units."
  (iter
    (with pos = (or (sub-units units) (list 0)))
    (for p in pos)
    (for last-p previous p)
    (for (head tail) first (split-at p units) then (split-at last-p tail))
    (when head
      (collect head into result))
    (finally (return (nconc result (list tail))))))

Is it possible to merge the two functions sub-units and split-sub-units into one? Does it make any difference regarding style or efficiency?

Upvotes: 0

Views: 163

Answers (1)

Renzo
Renzo

Reputation: 27414

I think the problem can be solved by iterating in the following way: collect all the elements in a list until their cdr are consecutive, and then repeat the previous process until the original list is empty, collecting all the produced lists. This can be done iteratively, with the total cost of O(n) where n is the length of the original list.

I use loop instead of iterate because I am more familiar with the first construct, it should be simple to convert it to iterate.

(defun split (l)
  (loop for (a b) = (loop for (x . y) on l
                          collect x into a
                          when (and y (/= (cdar y) (1+ (cdr x))))
                            do (return (list a y))   ; split here
                          finally (return (list a nil))) ; never split
        collect a        ; a list has been produced, collect it
        while b          ; if there are other elements
        do (setf l b)))  ; repeat splitting over them

A few tests:

CL-USER> (split '((0 . 0) (0 . 1) (0 . 2)))
(((0 . 0) (0 . 1) (0 . 2)))
CL-USER> (split '((0 . 0) (0 . 1) (0 . 3) (0 . 4) (0 . 7) (0 . 8)))
(((0 . 0) (0 . 1)) ((0 . 3) (0 . 4)) ((0 . 7) (0 . 8)))
CL-USER> (split '((0 . 0)))
(((0 . 0)))
CL-USER> (split '())
(NIL)

Upvotes: 3

Related Questions