Error trying to append items to list

[strong granite]

Hello everyone, when working on some exercises on exercism I got this error:

error: Syntax error
   ┌─ src/tracks_on_tracks_on_tracks.gleam:12:4
   │
12 │   [..languages, language]
   │    ^^^^^^^^^^^ I wasn't expecting elements after this
Lists are immutable and singly-linked, so to append items to them
all the elements of a list would need to be copied into a new list.
This would be slow, so there is no built-in syntax for it.
Hint: prepend items to the list and then reverse it once you are done.

Considering lists are immutable, wouldn't prepending items to the list also mean copying all elements into a new list? Moreso, wouldn't reversing a list also mean copying all elements into a new list? Is the compiler just optimizing those operations behind the scenes?

[dapper phoenix]

prepending doesn't need to copy because they're linked lists

reversing does make a copy

[left trellis]

You've got it backwards, prepending doesn't need to copy, appending does

[dapper phoenix]

The reason linked lists let you skip copying for prepending is kind of cool to think about.

type List(a) {
  Prepend(item: a, rest: List(a))
  EmptyList
}

fn prepend_hello_to_list(mylist) {
    Prepend("hello", mylist) // technically only constructs one "Prepend" object and reuses the previous list
}

this isn't the actual list type, but its the same idea

[strong granite]

Okay something just clicked in my brain, tell me if this is correct. I'm gonna say this about linked-lists in generic terms because I'm 1 day into Gleam here.

When appending to a linked-list, we have to modify the last element to reference the appending element. That would mean a cascading effect up the chain, because each element would have to update its reference to the next element. Prepending an element doesn't affect any of the references in the prepending list, so nothing needs to be copied.

[dapper phoenix]

yes!

[strong granite]

Wow! I get it now. Thats actually really cool

[dapper phoenix]

these were kind of common in old languages

in newer languages, you see an array-list data structure much more often

that like uses mutation, and reallocates arrays at different capacities as they grow

the linked lists are slower, but much simpler to implement

[strong granite]

Yeah that make's sense. As I understand it linked-lists don't need a continuous area of memory to exist. Since each element points to the next they can be scattered about which is more efficient to grow them, but that also makes you have to iterate through them one-by-one to find specific values hence why its slower

I read somewhere today (can't remember if it was the docs or exercism) that the language author basically feels that it's stupid to try and pull things from the middle of a list anyway, so you shouldn't really be iterating through the whole list often

[dapper phoenix]

also, reversing at the end does make a copy, but usually you only reverse it once you're done making the list, which only happens once. So (constructing a list + reversing it) is still O(n)

[strong granite]

yeah as opposed to making a new list on every append

[dapper phoenix]

Iterating is fine, but avoid doing it with an index counter variable

instead you want to iterate by destructuring it recursively

fn print_all_the_items(list) {
  case list {
    [item, ..rest] -> { // rest isn't copied; it already existed as part of the input list
      io.debug(item)
      print_all_the_items(rest)
   }
   [] -> Nil
}

basically, you want to iterate like this, where there is no "counter" variable counting up, and no places where you explicitly ask to traverse to get the ith element