Convert alist to/from regular list in Elisp?

Question

Given the "everything's-a-list" homoiconic approach to code and data in Lisp, I'm having a hard time understanding how to manipulate alists in Emacs Lisp. In particular, how can I convert an alist to an ordinary list of two-element lists, and vice versa? It almost seems like alists are a special type of their own which can't be manipulated the way regular lists are.

Specific example: I'm trying to bind a key in my .emacs file to create a frame of a certain size with a programatically generated name, as follows:

(make-frame '((name . "Blarg") (width . 80) (height . 24)))

This works fine as long as "Blarg" is a constant string, but because of the quote at the beginning of the alist, I can't put any code that evaluates to a string in place of "Blarg". What I would like to do is build up a list by consing the symbols and integers for the width and height, then add-list the name on to the front, and pass the whole thing to make-frame. But how do I convert the resulting data structure to an alist?

Specific answers on how to get make-frame to do what I want would of course be appreciated, but as my title indicates, I'm hoping for a more general explanation of how to manipulate alists and convert them to/from regular lists.

Rotl

Answer 1

@wvxvw answered your general question. But note that what is described is not converting an alist to a list or vice versa.

And in general you do not need to do any such "conversion". You can instead work directly with alists -- they are lists, after all.

Which brings me to the answer to your make-frame question, which is this, where foobar holds the name you want:

(make-frame `((name . ,foobar) (width . 80) (height . 24)))

or if you prefer:

(make-frame (cons (cons 'name foobar) '((width . 80) (height . 24))))

Pharisaic

This is the backquote syntax, if dodgethesteamroller hasn't encountered it yet: gnu.org/software/emacs/manual/html_node/elisp/Backquote.html – Sanitation

Voted both @Sanitation and you up. Thanks! But I still don't quite understand the "dot" notation for alists (which is why I thought it was necessary to convert them to/from ordinary lists). Is that really just syntactic sugar for a two-element list? – Rotl

dodgethesteamroller: Not quite. The dotted pair notation specifies car and cdr explicitly, and cdr need not be another list. For example, '(width 80) can be written as '(width . (80 . nil)). You should read C-h i g (elisp) Dotted Pair Notation – Sparing

An alist is a list. The elements of the list are conses, but the list of conses is a true list, not a dotted list. IOW, the last cdr of the list of conses is nil. (In some Lisps an element of an alist can also be an atom. In Common Lisp, for example, it can be nil instead of a cons. In Emacs Lisp an element can be anything. In both languages, an element is ignored if it is not a cons.) – Pharisaic

Answer 2

Just my two cents on constructing alists:

(pairlis '(name width height)
         '("Blarg" 80 24))
;; => ((name . "Blarg") (width . 80) (height . 24))

Derwon

That's very elegant. Is the function pairlis part of the Elisp standard library or does it require something else? – Rotl

It's part of cl-lib. You can (require 'cl) to use pairlis, or with the newer namespacing, (require 'cl-lib) to use cl-pairlis (which is the same function). – Sparing

Answer 3

(require 'list-utils)
(list-utils-flatten '((name . "Blarg") (width . 80) (height . 24)))
;; (name "Blarg" width 80 height 24)

list-utils is installable from MELPA.

Or using loop:

(loop for (head . tail) in '((name . "Blarg") (width . 80) (height . 24))
      nconc (list head tail))
;; (name "Blarg" width 80 height 24)

(loop for (head . tail) on '(name "Blarg" width 80 height 24) by 'cddr
      collect (cons head (car tail)))
;; ((name . "Blarg") (width . 80) (height . 24))

This is how I'd do it (requires cl library)

Timbered

OK, that explains how to convert an alist to an ordinary list, but what about vice versa? – Rotl

@Rotl oh, yes, sure, missed that part. Edited the question. – Timbered

You can replace (car tail) with just tail if you write (head tail) instead of (head . tail). – Marley

Answer 4

With dash list and tree manipulation library you can convert an alist into a flat list by transforming a dotted pair (a . b) into a 2-element list (a b), then flattening the list, which is possible with -mapcat (the 2 expressions below are equivalent):

(-mapcat (lambda (x) (list (car x) (cdr x))) my-alist)
(-flatten (-map (lambda (x) (list (car x) (cdr x))) my-alist))
(apply '-concat (-map (lambda (x) (list (car x) (cdr x))) my-alist))

In Haskell similar expressions (successively apply various functions to transform a list) would be more efficient and natural due to lazy evaluation.

So I want to use this answer as an opportunity to explore programming concepts a bit. What is it, when you traverse a list once and build some result based on its content (no matter what result)? It's a fold! The most primitive form of fold is one that takes a binary function and applies it to elements 1 and 2, then to result and 3, then to result and 4, and so on. So fold accepting + and list [1,2,3,4] becomes ((1+2)+3)+4. dash has such kind of fold called -reduce: (-reduce '+ '(1 2 3 4)) ; => 10

But this kind of fold is inflexible: a fold on a list of integers can only return an integer, not some arbitrary value. We need a more general fold, with better control. Such general fold uses an additional argument, called accumulator, which is used inside the binary function. On each iterator you can do anything with the list's element and the accumulator. The result of the function application becomes accumulator for the next iteration. In dash such fold is called -reduce-from. We take empty list as an accumulator, take each dotted pair in original alist one by one, then transform it into 2 new elements that we append to the accumulator inside our binary function. What could be easier?

(-reduce-from (lambda (acc x) (append acc (list (car x) (cdr x)))) '() my-alist)

But appending lists in such way is inefficient and idiomatic, because lists are implemented as singly linked lists in Lisp, so adding an element to the end or concatenating lists is O(n), the whole function works in O(n²). Lispers usually cons to the beginning of the list, but -reduce-from traverses the list left-to-right, that's why the result is going to be reversed. If only we could traverse the list right-to-left, so that we could the element, tranform it, and cons to the accumulator. Well, there's a function -reduce-r-from:

(-reduce-r-from (lambda (x acc) (cons (car x) (cons (cdr x) acc))) '() my-alist)

-reduce-r-from is the most efficient version, as it traverses the alist only once. Every time you need to build some list using a fold, chances are you need -reduce-r-from. Finally, what's great about the dash library is that it provides anaphoric macro versions for functions that accept functions as arguments to get rid of lambda syntax:

(--mapcat (list (car it) (cdr it)) my-alist)
(-flatten (--map (list (car it) (cdr it)) my-alist))
(apply '-concat (--map (list (car it) (cdr it)) my-alist))
(--reduce-r-from (cons (car it) (cons (cdr it) acc))) '() my-alist)

Ruthven

Answer 5

There is no need for flatten or dash. Lisp is somewhat functional (whatever that means). The point is, it has map functions. Most of what you try to achieve can be simply done with maps, reduce and filter (https://www.gnu.org/software/emacs/manual/html_node/elisp/Mapping-Functions.html).

Here is flatten with a simple map function in standard library:

(defun alist->list (alist)
  (mapcan (lambda (i)
            ;; see the last paragraph for more info
            (cons (car i)
                  (list (cdr i))))
          alist))

Also here a bonus:

(defun alist->plist (alist)
  (mapcan (lambda (i)
            (cons (intern (concat ":" (car i)))
                  (list (mapcar 'intern (cdr i)))))
          alist))

Just a side note for curious souls, about alists: An alist is basically, you guessed it, a simple list. NOTHING makes it special. You can do whatever operation you want on it. Logically however, it is a list that contains cons for each of its cells. As humans, we can use them as dictionaries so we read them as alists, otherwise, to Lisp, they are just simple plain good ol' lists just like anything else.

Knowing this, you'll realize why we need list function before cdr in alist->list. A cons is a list of 2 elements (much like characters arrays in C vs strings which are terminated by '\0'), but a list is a series of nested cons that are terminated by an implicit nil. This means that (a b) is (a . (b . nil)). So we must somehow transform (a . b) to (a . (b . nil)) to be able to use mapcan for this purpose (read the docs for more info, quoting: "it returns a single list with all the elements of the results (which must be lists)").

Miltie

That's unnecessarily complex though: (cons x (list y)), whatever the values of x and y, can simply be written (list x y) – Mesoderm

@Mesoderm that's true, I just wanted to keep a symmetry between my explanation and code. Thanks for mentioning again. – Miltie