Re:Stop Using Linked Lists
by evincarofautumn on Wednesday May 22, 2013 @03:10PM
(#5753067)
Yeah. There’s a finer point too: in Haskell, linked lists are useful less as data structures but more as iterators, because of their relatively large size overhead per element. A large proportion of list-based algorithms can be made streaming thanks to laziness and the immense cleverness of GHC, in which case only a constant number of allocations actually occur—often zero.
> String (i.e. [Char]) is inefficient unless you're doing a lot of manipulation such as insertions and deletions in the middle of the string
Is String actually efficient for this use case? If you insert in the middle of a String, wouldn't it have to copy all of the preceding characters? Only the tail could be shared, I would think.
The advice should probably be "use the right tool for the job." I wouldn't dream of writing functional programs without lists, but I also don't use e.g. the String type if I don't actually need it to be a list. Lists and arrays have very different algorithmic complexities for different operations. Figure out which operations you need, and pick the data structure that best suits what you intend to do.