Вообще, вопрос интересный, и, как обычно, всё сильно зависит от задачи.
Во-первых, в Хаскелле функция concat склеивает подсписки в списке, содержащем списки, т.е. concat :: [[a]] -> [a]
Операция (++) (append) склеивает два списка, т.е. (++) :: [a] -> [a] -> [a]
Если так подумать, то даже в строгом языке типа OCaml нет совершенно никакой нужды выделять под список zs память, такую же, как у обоих списков xs и ys. В худшем случае -- столько же памяти, как у xs, в неё копируется содержимое списка xs, но в последнем элементе записывается не NULL, а указатель на начало списка ys...
В ленивых языка всё не так просто. Вот такой простейший пример:
Код:
xs = [1..500000]
ys = [500001..1000000]
zs = xs ++ ys
main = do
print $ length zs
Несмотря на то, что тут три списка, два из которых по полмиллиона элементов и занимают в памяти примерно 4 МБт каждый, в памяти программа занимает стандартные 2 МБт, а профилировщик говорит, что реально в памяти сидело полезных данных этой задачи 2 кБт. Т.е. тут компилятор соптимизировал и вообще не создавал никаких списков.
Стоит усложнить задачу:
Код:
xs = [1..500000]
ys = [500001..1000000]
zs = xs ++ ys
main = do
print $ length xs
print $ length ys
print $ length zs
print $ last xs
print $ last ys
print $ last zs
Потребление памяти резко подскакивает (списки вынуждены остаться в памяти), но эксперименты показывают, что на список zs дополнительной памяти не тратится...
Тут как получается: список zs на самом деле является не списком, а функцией, которая вычисляется по необходимости:
Код:
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
Понадобились элементы, которые попали в zs из первого списка -- используются элементы первого списка, т.е. xs. Кончился xs -- начались использоваться элементы второго списка, ys.
Если по каким-то причинам список xs является бесконечным, то до ys дело так и не дойдёт:
Код:
xs = [1..]
ys = [500001..1000000]
zs = xs ++ ys
main = do
print $ head $ drop 1000000 zs
Память на списки опять не выделяется.
В таком варианте
Код:
xs = [1..]
ys = [500001..1000000]
zs = xs ++ ys
main = do
print $ head $ drop 1000000 zs
print $ head $ tail $ drop 1000000 zs
выделяется память под первые 1000001 элементов списка xs, дополнительных затрат нет...
Вход
FAQ
Поиск
)