From 4b75aba3006f752fbaa1f810d703379e776be1dd Mon Sep 17 00:00:00 2001
From: inoas <mail@inoas.com>
Date: Thu, 27 Oct 2022 01:56:47 +0200
Subject: imprive list.flatten speed in most cases

---
 src/gleam/list.gleam | 15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)

(limited to 'src')

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
 ///
-- 
cgit v1.2.3