Если под добавлением вы подразумеваете «добавить один элемент в конец списка», и вы реализуете это с помощью xs ++ [x], то да, это ужасно медленно для огромных списков, потому что каждый ++ равен O (n), что делаетвсего O (n ^ 2).
В этом случае вы можете ускорить это, просто используя cons, чтобы добавить элемент в начало списка вместо конца.Это делает весь процесс построения списка O (n).Затем вы можете использовать reverse, чтобы изменить его, что также является O (n), но вы должны сделать это только один раз, так что вы все равно O (n).
Если ваша обработка либо не является 'В зависимости от порядка или может быть сделано в обратном порядке с небольшими изменениями, вы можете в любом случае исключить reverse.И в этом случае вы также можете использовать лень для создания элементов только по мере их обработки, что означает, что вам не нужен весь список в памяти, что потенциально может также немного ускорить ваш код в зависимости от поведения памяти вашего кода;если каждый элемент списка помещается в кэш-память ЦП, вы можете получить большую скорость таким образом.
Если вы добавляете, вы имеете в виду «объединить список в конец другого списка», вы можете сделать то же самое, используякакая-то операция «обратного препендинга», когда вы помещаете элементы из нового списка в начало списка целей по одному элементу за раз;это дает вам конкатенацию списков, которая является линейной по размеру каждого нового списка, а не списка, который вы строите, так что в общем количестве обрабатываемых элементов она составляет O (n), а не O (n ^ 2).
В качестве альтернативы вы можете создать список списков в обратном порядке, используя cons, а затем обработать его с помощью некоторой операции обратного выравнивания, которая также должна быть O (n).
Это все ещеТруднее понять, как полностью избежать реверсирования в этом случае (многоэлементное добавление), если только ваша окончательная обработка полностью не зависит от порядка.
Конечно, если ваша потребность в высокой производительности выходит за рамки простого избеганиялинейные операции, тогда вам, возможно, придется взглянуть на разные структуры данных, чем на список.