Закиров Марат
My hypothesis is that somehow compiler reduces creating of a new list to just adding or removing one element. If it is not so. Then even ':' which is just adding to list head would be an O(n) operation just because it should return brand new list with one elem added. Or maybe functional approach uses pretty much different complexity metric, there copying of some structure "list" for example is just O(1)? If so then Q about compiler is still exists.
There is no magic in the compiler. It's a nice side-effect of having immutable data. If we copied the whole list, that would would be O(n), but we don't need to. We just make references to the old data. In a language like C++ that would be dangerous, since modifying the old list would affect the new one. It's safe in Haskell since data is immutable, so nobody can affect our code by mutating the data we're referencing. Finger trees are complicated, so I'll demonstrate it with a simple implementation of lists. These will work the same way as Haskell's built in lists, except for the types: l1 = (20, (10, ())) This works just like "20 : 10 : []". Now, internally this is not represented as one big array in memory. Instead, each part is stored separately and joined together like this (ie. it's a singly-linked list): l1 = (20, l2) l2 = (10, ()) Since l2 and "()" are immutable, there's no point copying their values around, so the runtime will just use pointers to a single copy. Prepending an element works in the same way, ie. there's no need to copy l1: l3 = (30, l1) Appending to the end is a different story. We can't reference any existing value, since their pointers will be wrong. For example "(30, (20, (10, (40, ()))))" would become: l4 = (30, l5) l5 = (20, l6) l6 = (10, l7) l7 = (40, ()) The only new part here is l7, which is the "40" we've added, but we couldn't re-use l2 for the "10" since its pointer goes to "()" and we need it to go to l7. We're forced to make a new value l6 which has the pointer we need. Of course, the problem has just been shifted since we now can't use l1 for our "20" because it's pointing to l2 and we need one which points to l6. That forces us to define the new value l5, and so on all the way along the list, which is why it takes O(n) time. Datastructures like Finger Trees use references to existing values in much the same way, but they manage these references in clever ways so that operations have small effects (like prepending to a list) rather than expensive chain-reactions (like appending to a list). Cheers, Chris PS : DLists work very differently, since they're created out of functions!