imprive list.flatten speed in most cases

1 files changed, 11 insertions, 4 deletions

diff --git a/src/gleam/list.gleam b/src/gleam/list.gleam
index b4c24c3..ddb062a 100644
--- a/src/gleam/list.gleam
+++ b/src/gleam/list.gleam
@@ -530,17 +530,24 @@ pub fn prepend(to list: List(a), item: a) -> List(a) {
   [item, ..list]
 }
 
+fn prepend_list_reverse(list prefix: List(a), to suffix: List(a)) -> List(a) {
+  case prefix {
+    [] -> suffix
+    [head, ..tail] -> prepend_list_reverse(tail, [head, ..suffix])
+  }
+}
+
 fn do_flatten(lists: List(List(a)), acc: List(a)) -> List(a) {
   case lists {
-    [] -> acc
-    [l, ..rest] -> do_flatten(rest, append(acc, l))
+    [] -> reverse(acc)
+    [a_list, ..rest_lists] ->
+      do_flatten(rest_lists, prepend_list_reverse(a_list, acc))
   }
 }
 
 /// Flattens a list of lists into a single list.
 ///
-/// This function runs in linear time, and it traverses and copies all the
-/// inner lists.
+/// This function traverses all elements twice.
 ///
 /// ## Examples
 ///