2

As an elisp beginner I'm trying to grasp what the "best practice" data structure is. For example, I did the simple adding (C-x a, i, g) of things to my abbrev_defs and when I look I see this:

...

(define-abbrev-table 'global-abbrev-table
  '(
    ("crwdesc" ":PROPERTIES:
:SEMANTIC:
:DESC:
:END:" nil 10)
    ("propid" ":PROPERTIES:
:CUSTOM_ID:
:SEMANTIC:
:DESC:
:END: " nil 0)
   ))

I also see org-element taking a "lisp representation" and turning it into org-mode output:

#+BEGIN_SRC emacs-lisp :results raw
(org-element-interpret-data
 '(headline (:title "One headline" :level 1)
            (property-drawer nil ((node-property (:key "property1" :value "value1"))
                                  (node-property (:key "property2" :value "value2"))))
            (#("Some much longer content."))))
#+END_SRC

#+RESULTS:
* One headline
:PROPERTIES:
:property1: (org-clock-in (quote (16)))
:property2: value2
:END:
Some much longer content.

Also, the org-element-parse-buffer seems to produce a very elaborate AST which, again, is nested lists. Is this the main data structure when working with elisp? It would seem so -- almost duh! so since this is a lisp. But are there other data structures that are also used? I ask because other data storage and config files (XML, RDF, etc.) generally don't use nested lists. For example, does elisp ever favor the more typical config text layout of simple lines? Or is the mantra "keep it lists?" And I might as well ask about alists while I'm at it. When are they desirable?

I ask all this because your typical tutorial might show you how to use alists, but they rarely talk about its real-world application, when to use it, when not to, or its importance to the language's eco-system.

closed as too broad by Drew, Luke, Scott Weldon, zck, glucas Aug 31 '15 at 14:25

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    (If XML isn't data nested lists, I don't know what is. And RDF.) – Drew Aug 29 '15 at 1:43
  • Straight, unpackaged RDF Turtle is no list format. – 147pm Aug 29 '15 at 1:51
  • 3
    Welcome to Emacs Lisp, where "Best Practices" just don't exist and people use whatever is convenient in the respective context. So, lists in nearly all cases. – wasamasa Aug 29 '15 at 8:42
  • 2
    Your question is very broad right now. Could you please edit it to make it more discrete? – Dan Aug 29 '15 at 11:58
  • 1
    You could try to rephrase the question to “When I should use other data structures than lists” — this will leave existing answers applicable and your question will be less broad and thus on-topic for this sort of site. – Mark Karpov Aug 29 '15 at 13:42
6

Modern Lisp dialects usually have something like arrays and hash-tables, as any mature programming language does. These data structures allow to lookup data by index and by key — two most obvious ways to retrieve data from compound object.

It turns out that lists can do all this stuff too. The only problem with them that they are not so efficient. For example, associative list (alist) or parameter list (plist) are not as efficient as hash tables due to their implementations (you need to traverse their elements one by one until you hit “right” element).

Emacs Lisp is not most sophisticated Lisp dialect, it's rather minimalistic. And tasks that Emacs Lisp needs to perform often don't need performance of arrays (except for strings, they are arrays) or hash tables. Thus we get situation where everything is usually represented as a list.

Here is what Richard Stallman says about data structures in Lisp in his hilarious “How I do my computing” thing:

The most powerful programming language is Lisp. If you don't know Lisp (or its variant, Scheme), you don't know what it means for a programming language to be powerful and elegant. Once you learn Lisp, you will see what is lacking in most other languages.

Unlike most languages today, which are focused on defining specialized data types, Lisp provides a few data types which are general. Instead of defining specific types, you build structures from these types. Thus, rather than offering a way to define a list-of-this type and a list-of-that type, Lisp has one type of lists which can hold any sort of data.

Where other languages allow you to define a function to search a list-of-this, and sometimes a way to define a generic list-search function that you can instantiate for list-of-this, Lisp makes it easy to write a function that will search any list — and provides a range of such functions.

In addition, functions and expressions in Lisp are represented as data in a way that makes it easy to operate on them.

Although he underestimates merits of many modern programming languages (that have already copied a lot of things from Lisp), he is right. However, there are object oriented systems for Lisp (see CLOS in Common Lisp for example), which may seem more modern for some, and yes, they are definitely useful. Not sure if there is object system for Emacs Lisp, as I said it's quite minimalistic.

1

This answer is going to be a little more general, than is generally expected, but few things need clarification before giving a more specific answer.

What are data structures?

Data structures are mathematical models studied in graph theory, a subfield of combinatorics. In mathematical jargon, a model is a particular way to present some axioms (a priori rules) of a system of axioms, typically using some mathematical objects described by the axioms. The mathematical description is useful for us because we can use it to predict the time and space spent by an algorithm. Another common description typically found in CS course books is to define them by saying that they are things which implement contracts established by abstract data types, which I find to be a taxonomically bad attempt at locating the subject.

Building blocks

Cons[tructor] cell is the minimal building block of a data structure. It describes an arc with two vertices. By continuing this analogy, an array is a cons cell with a fixed number of elements--equivalent to a "forest" in some sense, or to a vertex spanning multiple arcs to a number of other vertices. Similarly, there are ways to describe other data structures, for example, a heap, is a binary tree with an added condition pertaining to the order of the nodes in the tree hierarchy. Hashtable is a more complex data structure with multiple rules governing the distribution of nodes and the way of adding and removing them and so on.

Lists

Or, more generally cons cells are the fundamental data structure of any language, but some languages may choose not to expose them directly and instead provide more high-level data structures, possibly inside containers, combined with implementation of algorithms which operate on the data structure and so on.

Best practices

Simple programs benefit from simple solutions, but non-trivial programs will usually benefit from higher level of abstraction. Lists are the fundamental building blocks, but a good deal of learning how to program is to learn to build abstractions. So, it is typically best to create data structures which encapsulate lists, be it simple structs, or more complex ones like trees, hash-tables etc.

XML, RDF and Co

XML and RDF are not data structures. They are formats for representing data. It is up to implementation to choose how to implement these formats, including what data structure should be used.


In conclusion

List (cons) is the most common data structure, and for a good reason. But you shouldn't choose data structure based on popularity, instead you need to choose (or create) an abstraction that is the best solution to the problem at hand.

  • Typically, we learn programming alone, with written material. But so often that text doesn't tell us "best practice," and, hence, we go off half-cocked, doing things not exactly wrong, but inefficiently and non-standard . . . because we didn't know any better. For example, in Land of Lisp there is a graph data structure that I instinctually know is not meant for big, real-world use. Hence, a very important part of learning programming is finding out best practices, i.e., not going off down the wrong road or re-inventing the wheel. – 147pm Aug 29 '15 at 16:05
0

There is no "best practice data structure". It looks like you didn't do much programming, so let me get you into basics.

Data structures are abstractions that allow us to talk about some things on higher level. We have "list" or "array", not bits. Each of data structres is laid out in some way that allows us to do some things easier or faster, and others are slower and harder(compare inserting element in the middle of the array, versus middle of the list).

Hence, it does not really matter what language you are using, but rather what problem you are trying to solve - if you choose your data structures well, you will end up with readable and fast program that is scalable for larger data. If you pick them wrong, however, you might never solve your problem.

There are some exceptions, of course. In C you have arrays out of the box, so you mostly use them(plus, they are convenient most of the time). In Lisp, you have lists, and since most of your programs won't benefit from 0.0001s speedup, you can use them just fine.

You want to do simple stuff? Use lists, Lisp has many functions that make using lists easier. Have some large base of ordered pairs? You might want to use hash maps(or whatever they are called in your language). Something different? Choose data structure accordingly.

Programming responsibly and thinking before coding is the Best Programming Practice.

  • “It does not really matter what language you are using, but rather what problem you are trying to solve”. Then you talk about “exceptions”, but they are not really exceptions, they confirm a different idea: “programming languages influence how you think about the problem”. So, yes, it does matter which language you're using. The notion “data structure” may designate different things in different languages: algebraic data type, class, etc. Of course once you hit bottleneck of some sort you will need to understand why it happens. At this point it's useful to know how underlying algorithms work. – Mark Karpov Aug 29 '15 at 12:17
  • So, in other words, your answer is definitely correct in a way, but the phrase: “does not really matter what language you are using” is far from truth in many cases. – Mark Karpov Aug 29 '15 at 12:21
  • > It looks like you didn't do much programming, so let me get you into basics. This sentence is not useful for anybody. – clemera Aug 29 '15 at 12:28
  • 2
    @Mark algebraic data types or classes are not data structures in any language. Types belong in type theory, which, in programming, is used to verify / give formal proofs of your program correctness, data structures come from a different field of study: graph theory, possibly combinatorics. We don't use them to prove correctness of a program, instead we study them in order to understand the performance of a program. – wvxvw Aug 29 '15 at 12:49
  • @wvxvw, thanks for the comment, that example wasn't correct, I admit. The point is that tools provided by language (by design) do influence the way in which particular problem is (usually) solved in that language unless you are beginning to have performance issues or problems with scalability, etc. – Mark Karpov Aug 29 '15 at 13:13

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