Qqwy / Marten (Jul 01 2022 at 09:29): Qqwy / Marten (Jul 01 2022 at 09:29):Question: Why did we decide to name the sequential data structure in Roc List? Since it is not a linked list but rather a doubling-in-size array, it has very different performance characteristics than people coming from other languages would first expect, and a name like Seq(uence), Array or Vec(tor) might be more descriptive.
Especially in functional languages, the name 'List' is ubiquitously used for linked lists.
Of course, I'm pretty sure this ship has sailed, and I'm pretty sure this decision has not been made lightly.
I think the rationale for this choice might make a very good addition to the FAQ.
Folkert de Vries (Jul 01 2022 at 09:34):e.g. python does use the name "list" for what is an array
Folkert de Vries (Jul 01 2022 at 09:34):zig uses "arraylist"
Folkert de Vries (Jul 01 2022 at 09:35):list, I think, is only confusing to programmers from a different background. It is the most intuitive name for what it does
Qqwy / Marten (Jul 01 2022 at 09:36):I think it is confusing to people with a functional background, as the name linked list and list in general has been conflated there.
Folkert de Vries (Jul 01 2022 at 09:38):idk, it's confusing once and then you just know
Qqwy / Marten (Jul 01 2022 at 09:39):e.g. Haskell, Elm, PureScript, Elixir, Erlang, any lisps (including Clojure), F# all use List to mean linked list, and Array or Vec for the abstract sequential data type.
Anton (Jul 01 2022 at 09:42):I'm not sure how many of those using Haskell, Elm, PureScript... actually know what datastructure is behind the List.
Qqwy / Marten (Jul 01 2022 at 09:43):@Anton I expect most people, because of the major consequences it has to how you have to write your algorithms for them to be efficient.
Folkert de Vries (Jul 01 2022 at 09:43):well a big difference in those languages is that you can write inductive definitions
Folkert de Vries (Jul 01 2022 at 09:43):and in roc you have to just use e.g. walk
Qqwy / Marten (Jul 01 2022 at 09:44):e.g. prepending and copying is very cheap with linked lists, but appending and indexing is very slow.
For arrays it is vice-versa.
Folkert de Vries (Jul 01 2022 at 09:44):at least in elm, most people don't really care about the efficiency
Folkert de Vries (Jul 01 2022 at 09:44):you render 10 nodes, what matters is rendering performance, not how fast a 10-element list is
Qqwy / Marten (Jul 01 2022 at 09:50):True, but I'm pretty sure that argument does not hold up in Roc.
Qqwy / Marten (Jul 01 2022 at 09:51):(and of course Elm does have both List and Array)
Richard Feldman (Jul 01 2022 at 11:42):so the same argument could apply to Array - in C, C++, Zig, and Rust an array is a fixed-length data structure :big_smile:
Richard Feldman (Jul 01 2022 at 11:46):basically List seems like the nicest name, and the learning curve for functional programmers compared to Python programmers is not 0, but very very close to it.
It's hard to find a shorter learning curve than "it's not a linked list, it's backed by an array, the end" :smiley:
Richard Feldman (Jul 01 2022 at 11:47):so I thought about the concern but decided the risk that it was a problem in practice was low enough that we should try it and see how it felt, and so far I think it's felt nice!
Brendan Hansknecht (Jul 01 2022 at 14:30):I think that it should be fair enough to tell people, "roc really cares about performance. As such, we are not willing to pay the cost of linked lists. Instead we use 'normal' lists"
Brian Carroll (Jul 01 2022 at 17:13):On this Zulip I've see the explanation many times, including in this thread, that "list is really an array" or "list is backed by an array".
So maybe that suggests that the word "array" is clearer.
Brian Carroll (Jul 01 2022 at 17:14):But it's not a huge deal either
Brendan Hansknecht (Jul 01 2022 at 18:26):If you use "array", I think you will confuse everyone from lower level languages who expect arrays to be static. To me "list" is the correct word and "array" is not, but I don't come from a functional language background.
jan kili (Jul 01 2022 at 20:08):Speaking of backgrounds, Roc seems uniquely positioned at the intersection of multiple communities. It's faster than other pure langs, purer than other fast langs, both faster & purer than other scripting langs, and broader than Elm. Currently I see Roc's syntax/conventions as trying to take the best parts of everything else and its docs/framing as not being primarily aimed at one background/community. Is that true, should that change, and should individual backgrounds/communities be "targeted" by either conventions or docs?
Qqwy / Marten (Jul 01 2022 at 20:45):Thinking a little more about this:
List as "List is actually a [dynamic] array", which as @Brian Carroll already noted might indicate that it is the clearer name.Array to be a 'static' array at first, that is not a problem: Static arrays and dynamic arrays have virtually identical performance and memory characteristics; the main difference is that dynamic arrays permit a small amount of extra operations (growing/shrinking).Array is dynamic; and if you do encounter Array.append / Array.slice / Array.dropLast at some point, the change to your mental model will be tiny. Brendan Hansknecht (Jul 01 2022 at 20:56):Static arrays tend to be on a stack and never call malloc. That is a huge performance implication.
Brendan Hansknecht (Jul 01 2022 at 20:56):Though I will agree it is less surprising overall
Brendan Hansknecht (Jul 01 2022 at 20:57):Though also, if we ever add truely static arrays (which may happen), what would we call that?
Kas Buunk (Jul 04 2022 at 11:22):Go uses 'slices' to mean dynamically sized arrays. And it uses 'arrays' for fixed-sized arrays. Is that the same concept?
Qqwy / Marten (Jul 04 2022 at 11:42):In other languages, 'slice' is used to represent a 'subsequence' of a collection (represented as a start location and a size).
Kas Buunk (Jul 04 2022 at 11:53):So conventions between languages overlap and diverge. I'd then stick to those conventions of naming data structures that are (nearly) unanimously adopted. Give preference to good naming and emerging conventions that the Roc community itself creates - whatever works best for the languages use-cases - over 'picking the least surprise, given the majority of other language communities'. I'd say 'Array' is nearly unanimously fixed size. And List is i.m.o. clearer than slice.
Nothing is lost if you are not aware from the get-go that Array is dynamic
You can be equally clear in that nothing is lost if you are aware from the get-go that List is not a linked list, but a dynamically sized array.
Kas Buunk (Jul 04 2022 at 11:59):Is somewhere a 'list' of considerations for various choices, among which naming things? It seems worthy of existing in a living document, rather than the chat history. With for each choice, the alternatives and arguments.
Kas Buunk (Jul 04 2022 at 12:01):Like some sort of meta-documentation that can later feed into a specification. In version control rather than the chat.
Last updated: Jun 16 2026 at 16:19 UTC