In this example, there is a list of miscellaneous orphan floats '(9.9 10.1 10.3 10.5 10.7 10.9 11.1) that needs to be incorporated in numerical order into a second main / master list (10.0 10.2 10.4 10.6 10.8 11.0), with the hard bounds being car and (cdr (last ...)); i.e., the orphan floats will be remainders if they are less than car or greater than (cdr (last ...)) of the main / master list. The end result for the main / master list will be '(10.0 10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8 10.9 11.0), and the end result for the remainders will be '(9.9 11.1). How can this be accomplished programmatically by an Emacs user?

[My only thoughts of an approach at this point in time are using the ring library to give me next and previous of the selected item while looping through the main list; however, I suspect there is a better approach.]

EDIT: Example output of solution: '((remainders (9.9 11.1)) (master (10.0 10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8 10.9 11.0)))

  • What happened to 10.0?
    – NickD
    Commented Mar 30, 2022 at 3:46
  • Both lists above are sorted - is that always the case?
    – NickD
    Commented Mar 30, 2022 at 3:48
  • @ NickD -- the main / master list will always be sorted numerically, however, the orphan list that will end up having some remainders is not going to be sorted; i.e., a few zeros, a few 0.03, a few 0.05, and some floats what will fall within the parameters of the main / master list. For duplicates, that fall within the main / master list, I will be creating a list of text properties containing details of each element being incorporated that matched -- however, that is not needed for a minimal working example.
    – lawlist
    Commented Mar 30, 2022 at 3:56
  • So you want to sort the unsorted list, and merge with the original list. Or just combine the two as-is and sort the result. You know that sort exists, yes?
    – phils
    Commented Mar 30, 2022 at 4:00
  • @phils --thank you. The orphan list does not need to be sorted, and the remainder list does not need to be sorted. The main / master list, however, should be sorted.
    – lawlist
    Commented Mar 30, 2022 at 4:01

2 Answers 2

(require 'cl-lib)

(defun incorporate (master orphans)
  (let* (;; remove call to `cl-sort' if `master' is already sorted
         (master (cl-sort (cl-copy-list master) #'<))
         ;; remove call to `cl-sort' if `orphans' is already sorted
         (orphans (cl-sort (cl-copy-list orphans) #'<))
         (lb (car master))
         (ub (car (last master)))
         (pred (lambda (elem) (or (< elem lb) (> elem ub))))
         (to-incorporate (cl-remove-if pred orphans))
         (remainders (cl-remove-if-not pred orphans)))
    (list (list 'remainders remainders)
          ;; since both `master' and `to-incorporate' are sorted, we can use `cl-merge'
          (list 'master (cl-merge 'list (cl-copy-list master) to-incorporate #'<)))))

(incorporate '(10.0 10.2 10.4 10.6 10.8 11.0)
             '(9.9 10.1 10.3 10.5 10.7 10.9 11.1))


'((remainders (9.9 11.1))
  (master (10.0 10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8 10.9 11.0)))

Why do you think the ring library would help with this problem?

  • Thank you ... I will try out this answer later in the day when back at the computer. I had initially thought of the ring library because it provides a preview of what is next, whereas, the basic while or mapc would necessitate an additional check of the current's position in the list to locate what would be next. Along those lines, at each element of the master list, knowing what is next, I was thinking of looping through the remainders to see if anything should be inserted. Then, I was thinking of inserting the remainders at the right location. However, I knew that idea was awkward.
    – lawlist
    Commented Mar 30, 2022 at 13:49

So as @d125q has posted a nice high level solution (where he could also have used the map-merge and seq-remove/sort variants), I will post my somewhat lower level 'list-eater' style solution (for completeness, and in addition to my comment). The solution might read a little less nicely than the high level solution, but the steps are very intuitive and logical.

;; First sort your lists (which they already are here), and create the
;; `remainders' and `new-main' lists
(let ((orphan '(9.9 10.1 10.3 10.5 10.7 10.9 11.1))
      (main '(10.0 10.2 10.4 10.6 10.8 11.0))
      remainders new-main)

  ;; then 'eat' orphan and push to remainders as long (car orphan) is smaller
  ;; than (car main)
  (while (< (car orphan) (car main))
    (push (car orphan) remainders)
    (setq orphan (cdr orphan)))

  ;; now 'eat' both lists, take a bite depending on which has the smallest
  ;; 'car', and push to `new-main', as long as there are members in main
  (while main
    (let ((o (car orphan))
          (m (car main)))
      (cond ((< o m)
             (push o new-main)
             (setq orphan (cdr orphan)))
             (push m new-main)
             (setq main (cdr main))))))

  ;; subsequently because the push prepends elements, nreverse the `remainder' and
  ;; the `new-main' lists, and append final remainders to initial remainders. I
  ;; use cons as I don't know why you would want the cdr's of the elements to be
  ;; nested lists
  (list (cons 'remainders (append (nreverse remainders)
        (cons 'main (nreverse new-main))))

when I say bite, I mean taking the cdr of the list for the next iteration (from the books 'land of lisp' or 'realm of racket').

Finally, I set the results as cdr directly using cons instead of 'adding' an extra (seemingly redundant) list around it.

Extending the algorithm to handle duplicates should be quite straightforward (handle the case when both cars are equal, and check if new-main already contains the element before pushing).

  • I have removed a redundant step, and while doing that, I have added a hint for how to extend the algorithm to handle duplicates. Commented Mar 31, 2022 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.