data structures - List manipulation performance in Haskell -

i learning haskell , curious following:

if add element list in haskell, haskell returns (completely?) new list, , doesn't manipulate original one.

now let's have list of million elements , append 1 element @ end. haskell "copy" whole list (1 million elements) , adds element copy? or there neat "trick" going on behind scenes avoid copying whole list?

and if there isn't "trick", process of copying large lists not expensive think is?

it depends on data structure you're using. if you're using normal haskell lists, these analogous typical linked list implementation in c or c++. structure, appends o(n) complexity, while prepends o(1) complexity. if try append million elements, take o(500000500000) time (o(1) + o(2) + o(3) + ... + o(1000000)) approximately 500000500000 operations. regardless of language you're using, haskell, c, c++, python, java, c#, or assembler.

however, if use structure data.sequence.seq, uses proper structure internally provide o(1) prepends , appends, cost can take bit more ram. data structures have tradeoffs, though, it's 1 want use.

alternatively, can use data.vector.vector or data.array.array, both provide fixed-length, contiguous memory arrays, appending , prepending expensive because have copy entire array new location in ram. indexing o(1), though, , mapping or folding on 1 of these structures faster because chunks of array can fit cpu cache @ time, opposed linked lists or sequences have elements scattered on ram.

does haskell "copy" whole list (1 million elements) , adds element copy?

not necessarily, compiler can determine if it's safe have last value's next pointer change point @ new value instead of empty list, or if it's unsafe may necessary copy entire list. these problems inherent data structure, not language, though. in general, haskell's lists better c linked lists because compiler more capable of analyzing when safe programmer is, , c compiler won't sort of analysis, they're told.