{"action":"closed","issue":{"url":"https://api.github.com/repos/elm-lang/elm-plans/issues/13","labels_url":"https://api.github.com/repos/elm-lang/elm-plans/issues/13/labels{/name}","comments_url":"https://api.github.com/repos/elm-lang/elm-plans/issues/13/comments","events_url":"https://api.github.com/repos/elm-lang/elm-plans/issues/13/events","html_url":"https://github.com/elm-lang/elm-plans/issues/13","id":96482976,"number":13,"title":"Proposal: Default to Arrays over Lists","user":{"login":"rtfeldman","id":1094080,"avatar_url":"https://avatars.githubusercontent.com/u/1094080?v=3","gravatar_id":"","url":"https://api.github.com/users/rtfeldman","html_url":"https://github.com/rtfeldman","followers_url":"https://api.github.com/users/rtfeldman/followers","following_url":"https://api.github.com/users/rtfeldman/following{/other_user}","gists_url":"https://api.github.com/users/rtfeldman/gists{/gist_id}","starred_url":"https://api.github.com/users/rtfeldman/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rtfeldman/subscriptions","organizations_url":"https://api.github.com/users/rtfeldman/orgs","repos_url":"https://api.github.com/users/rtfeldman/repos","events_url":"https://api.github.com/users/rtfeldman/events{/privacy}","received_events_url":"https://api.github.com/users/rtfeldman/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/elm-lang/elm-plans/labels/proposal","name":"proposal","color":"5319e7"}],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":13,"created_at":"2015-07-22T06:11:15Z","updated_at":"2015-08-25T01:19:38Z","closed_at":"2015-08-25T01:19:38Z","body":"A quick note to guide discussion: a clear prerequisite for a change of this magnitude would be benchmarking before and after to make sure it actually makes sense from a performance perspective. There's no way to tell what the results of those benchmarks will be without running them, so let's discuss assuming that this won't happen if the benchmarks say it shouldn't—and instead discuss what the *other* pros and cons would be assuming the benchmarks check out.\r\n\r\n## Proposed Changes\r\n\r\n**1.** Square brackets are now literals for `Array` values, not `List` values. In other words:\r\n\r\n```elm\r\nstuff : Array String\r\nstuff = [ \"foo\", \"bar\", \"baz\" ]\r\n```\r\n\r\nThis would be a breaking change.\r\n\r\n**2.** The default data structure for libraries (in Core, etc.) becomes `Array` instead of `List`.\r\n\r\nFor example, this would mean the following changes for [`Dict`](http://package.elm-lang.org/packages/elm-lang/core/2.1.0/Dict):\r\n\r\n* [`Dict.keys`](http://package.elm-lang.org/packages/elm-lang/core/2.1.0/Dict#keys) returns an `Array`\r\n* [`Dict.values`](http://package.elm-lang.org/packages/elm-lang/core/2.1.0/Dict#values) returns an `Array`\r\n* [`Dict.toList`](http://package.elm-lang.org/packages/elm-lang/core/2.1.0/Dict#toList) becomes `Dict.toArray`\r\n* [`Dict.fromList`](http://package.elm-lang.org/packages/elm-lang/core/2.1.0/Dict#fromList) becomes `Dict.fromArray`\r\n\r\nThis would also be a breaking change.\r\n\r\n## Motivation\r\n\r\n[A comment in another thread](https://github.com/elm-lang/elm-plans/issues/12#issuecomment-123507281) by @TheSeaMau5 got me thinking about this and discussing some things with @evancz.\r\n\r\nThere are several reasons to do this:\r\n\r\n#### 1. Performance\r\n\r\nWe have already seen, in WebGL cases, specific examples of Elm programs that run noticeably faster when using `Array` instead of `List` on otherwise equivalent code. We have yet to seen the reverse, although granted that is harder to reproduce because literals produce `List` values and libraries tend to prefer `List`.\r\n\r\nBecause [Elm's Arrays are implemented using Relaxed Radix Balanced Trees](http://elm-lang.org/blog/announce/0.12.1), the performance characteristics associated with (for example) recursively pattern matching should be substantially better here than they are with large vanilla JS arrays. For pattern matching on small lists, the extra overhead of instantiating N extra arrays may be comparable (and perhaps even less) to the extra overhead of instantiating N `Cons` cell objects, which is required to instantiate even a `List` that does not use pattern matching.\r\n\r\nBenchmarks should be able to shed better light on this.\r\n\r\n#### 2. Familiarity to JS Programmers\r\n\r\nAs @TheSeaMau5 [said](https://github.com/elm-lang/elm-plans/issues/12#issuecomment-123507281):\r\n\r\n> JS users are a big part of Elm's target. JS people are accustomed to having efficient indexing in collections and never really deal with linked lists. (I don't remember ever using a linked list in JS to be honest)\r\n\r\n> [Redefining] the square bracket syntax to mean array instead of list...would break with the ML family. But like @evancz pointed out in his [talk](https://www.youtube.com/watch?v=oYk8CKH7OhE), the goal is not to make Haskell or Standard ML more usable and more maintainable. The goal is to make Javascript more usable and more maintainable. Javascript has Arrays. JS people know arrays, not linked lists. We can cater to JS people by having square brackets mean Arrays.\r\n\r\nI have encountered a significant number of capable JS programmers who did not study Computer Science in school, and as such have never even had occasion to use a linked list. Linked lists are not terribly hard to explain, of course, but their use by default does add fuel to the \"Elm seems alien\" fire.\r\n\r\n#### 3. Future Compilation Targets\r\n\r\nAlthough this is not happening any time in the near future, it is worth thinking about how this proposal would affect Elm's long-term compilation target prospects.\r\n\r\nOne of the compilation targets with the most potential is machine code (or WebAssembly). There's no way to benchmark that yet, since Elm does not currently compile to these targets, but we do know that mandatory JS Object overhead will disappear, and that [arrays enjoy significant performance benefits from locality over linked lists](http://stackoverflow.com/questions/19064384/arrays-vs-linked-lists-in-terms-of-locality). Of course, we would need to run (future) benchmarks to ascertain the real impact."}}