Table of contents

• Introduction
• Goal
  • Use Cons as double pointers
  • Keep It Simple
• Summary of available functions
• Technical details
  • Modify the argument list
  • Files
  • Circular lists
  • Next / Previous vs After / Before
  • Remove vs Delete
  • Functions in arguments
  • Assoc
• Examples
• Warning

Introduction

Duo is a library of in place list operations in Emacs-Lisp. Its functions modify the original list when :

• It’s easy to get back : rotate, reverse, move, etc
• The name is clear : push, pop, add, drop, insert, remove, etc
  • When an element is removed, a reference to it is often returned

However, when it’s difficult or impossible to reverse the operation, a new list is created, with copies of the values using purecopy. For instance :

• filter
• partition

If in doubt, check their doc.

Goal

Use Cons as double pointers

This library is implemented with (CAR . CDR) cons, which are called duo, hence the name. These cons are everywhere in Elisp, either explicitely created or as brick components in lists. A list variable list is itself the cons at the beginning of the list. (cdr list) is the second cons in the list. And so one with (cddr list), (nthcdr N list). Generally speaking, a member of a list is a cons (value . next-member-in-list). Most of Elisp is built around these (CAR . CDR) double pointers. You can even construct binary trees with it.

Keep It Simple

Primarily use Elisp tools from C source code :

• Built-ins :
  • cons, list
  • car, cdr
  • setcar, setcdr
  • nth, nthcdr
  • etc
• Special forms :
  • if, cond
  • while
  • etc

Some functions defined in subr.el are also used.

Summary of available functions

• Finding cons in list
• Finding previous / next cons
  • In plain list
  • In virtual circular list
• Replace element
• Map
• Join
• Truncate
• Next / Previous in group
• Next / Previous matching filter
• Push, Add
• Pop, Drop
• Rotate <- or ->
• Roll until a cons is first or last
• Reverse
• Insert
• Remove, Delete
  • One occurence
  • All occurence of a value
• Teleport : move after or before another cons or element
• Move previous or next
  • In plain list
  • In virtual circular list
• Exchange cons or elements
• Insert in sorted list
• Insert at group beginning or end
• Partition with a key function to form an alist

Technical details

Modify the argument list

When you pass a list as argument of a function, the calling scope list-var holds the address of the first cons of the list. The argument arg-list-var holds a copy of it. Using (setq list ...) inside the definition of the function changes the argument list reference, not the calling scope one. So, the calling scope address is not updated. As a result, you need either :

• to use the list symbol in argument (*-sym-* functions)
  • (function ... 'list ...)
• to pass a reference to the list as argument (*-ref-* functions)
  • (setq reflist (cons list nil))
  • (function ... reflist ...)
• to recover the modified list as the returned value (*-return-* functions)
  • (setq list (function ... list ...))

A common case of this situation is with functions which modify the first cons of the list : push, pop, etc.

Check their doc to know how to recover the updated list.

Files

• duo-common.el holds the functions which don’t modify the list
• duo-symbol.el holds the *-sym-* functions
• duo-referen.el holds the *-ref-* functions
• duo-return.el holds the *-return-* functions

Circular lists

Caution : applying some of these functions to circular lists would produce infinite loops.

However, some functions, like *-circ-* or *-rotate-*, simulate virtual circular lists by :

• Continuing at the beginning once arrived at the end
• Continuing at the end once arrived at the beginning

Next / Previous vs After / Before

There is a slight difference between next/previous and after/before functions :

• Next / Previous use a cons as main argument
• After / Before use the value of an element of the list as main argument

Remove vs Delete

There is a slight difference between remove and delete functions :

• Remove removes a cons given as argument
• Delete remove the first cons whose car matches an element given as argument

Functions in arguments

Some functions accept a function fn-* in argument. Among these fn-*, some takes two arguments. When this is the case, they are called internally like this :

(funcall fn-* elem-or-cons-from-argument cons-from-loop)

Assoc

The classic assoc function return the cons (key . value), which is the content of the Alist element, whereas the duo-assoc function return the duo ((key . value) . next-member-in-alist), real member of the Alist.

Examples

(require 'duo-common)

(setq mylist '(1 2 3 4 5 6 7))
(print (duo-slice mylist 3 -1))

(setq mylist '(1 2 3 4 5 6 7 1 1))
(duo-replace-all 1 2 mylist)
(print mylist)

(require 'duo-symbol)

(setq mylist '(1 2 3 4 5 6 7))
(duo-sym-rotate-left 'mylist)
(print mylist)
(duo-sym-rotate-right 'mylist)
(print mylist)

(setq mylist '(1 2 3 4 5 6 7))
(duo-sym-roll-to-end 3 'mylist)
(print mylist)

(setq mylist '((1 . 2) (2 . 4) (3 . 6) (4 . 2) (5 . 3)))
(duo-sym-roll-to-beg 3 'mylist 'duo-x-match-car-p)
(print mylist)

(setq mylist '(1 2 3 4 5 6 7))
(duo-sym-reverse 'mylist)
(print mylist)

(require 'duo-referen)

(setq ref (list '(1 2 3 4 5 6 7)))
(duo-ref-reverse ref)
(print ref)
(print (duo-deref ref))

(require 'duo-return)

(setq mylist '(1 2 3 4 5 6 7))
(setq ret (duo-return-reverse mylist))
(print ret)

Warning

Despite abundant testing, some bugs might remain, so be careful.