Proposal: add a list.rotate/2 function

[rbobillot]

Recently, I was working on KRYTOS, and while creating the Vigenère table,
I implemented my own circular shift function.

Upon exploring Gleam's standard library, I noticed that a list.rotate or list.shift function isn’t available yet,
unlike in languages such as Rust, Julia, C++, Java, or Ruby.

This led me to think it could be a valuable addition to Gleam's stdlib !

/// ```gleam
/// fn(List(a), Int) -> List(a)
/// ```
///
/// Performs a circular shift on a list:
/// - a negative number of rotations shifts the list to the left
/// - a positive number shifts it to the right
///
/// ```gleam
/// rotate([1,2,3,4,5], -3)
/// // -> [4,5,1,2,3]
///
/// rotate([1,2,3,4,5], 3)
/// // -> [3,4,5,1,2]
/// ```
///
fn rotate(list: List(a), rotations n: Int) -> List(a) {
  let len = list.length(list)
  let idx = case n < 0 {
    False -> len - n
    True -> n
  }

  let #(h, t) = list.split(list, int.absolute_value(idx) % len)

  list.append(t, h)
}

[lpil]

This is an very expensive operation on linked lists, so it would not be suitable for the standard library. If you want to rotate a sequence then list may be the wrong data structure for you.

[lpil]

That's true in a mutable language if you already have the pointers. If you don't have the pointers it's a full traversal to get them. If you're in an immutable language it's a full traversal and allocating a new cell for each element in the list.

[Olian04]

Even though Gleam is immutable, both Erlang and JS have mutability. So this kind of issue could be made a non-issue if the lists were implemented with mutability in mind. However I dont know erlang even nearly enough to say if this would result in a huge performance hit or not.

[lpil]

Erlang does not have mutability, and while JavaScript has mutability it does not have the ability to identify unique references so it could not be done there either.

[Olian04]

In erlang I was thinking of ETS. As for JS, objects are passed by reference and equality checks between objects are done via reference equality.

[lpil]

Yes, which isn't enough to implement the optimisation you're proposing because it can only be applied when the current scope is the only one that references any of the list cells.