Arc Forumnew | comments | leaders | submitlogin
Ask: When to use lists vs tables?
4 points by kinnard 1950 days ago | 5 comments
Is there any general analysis on when it's best to use lists vs tables? The pros + cons :) of each?


4 points by i4cu 1949 days ago | link

It's probably worth reading the arc tutorial [1].

I mention it because pg makes a fairly good point about using alists.

  "There is a tradition in Lisp going back to McCarthy's 1960 paper [2] 
  of using lists to represent key/value pairs:

  arc> (= codes '(("Boston" bos) ("Paris" cdg) ("San Francisco" sfo)))
  (("Boston" bos) ("Paris" cdg) ("San Francisco" sfo))

  This is called an association list, or alist for short.  I once
  thought alists were just a hack, but there are many things you can
  do with them that you can't do with hash tables, including sort
  them, build them up incrementally in recursive functions, have
  several that share the same tail, and preserve old values"
Of course none of this negates anything in akkartik's response. I just think there are some helpful tips in the tutorial.

1. http://www.arclanguage.org/tut.txt

-----

4 points by akkartik 1950 days ago | link

Lists are easy to split and merge, insert and delete nodes from, but searching them is slow. Tables are fast for searching and insertion and deletion, but they don't naturally encode ordering relationships.

Check out this chapter: http://www.gigamonkeys.com/book/they-called-it-lisp-for-a-re... Tables are often great for things Lisp historically used lists for. But the one thing they can't do is represent code and trees in general. That's where cons cells come in.

-----

3 points by krapp 1950 days ago | link

>But the one thing they can't do is represent code and trees in general. That's where cons cells come in.

They can if you can nest them, or include references to other keys (like foreign keys in SQL or something) It's inefficient but it's possible. You can even represent trees in a flat array if you work hard enough.

Although maybe I should be pedantic and clarify that you can represent trees with tables but not in tables natively, of course.

-----

2 points by akkartik 1949 days ago | link

You got me, I was careful to use the word 'natural' in the first paragraph but I forgot to do so in the second ^_^

-----

2 points by kinnard 1893 days ago | link

I realized belatedly that ordering matters for my application. . .

Even looked at Assocative Containers[1] before I thought, "alist!"

[1] https://en.wikipedia.org/wiki/Associative_containers

-----