3 ms·
I agree about lists being much more expressive in a lot of functional code, and sometimes compilers can optimize away some of the overhead. On the other hand, t
by thirsteh 13y ago
I agree about lists being much more expressive in a lot of functional code, and sometimes compilers can optimize away some of the overhead. On the other hand, take a language like Haskell: It has Data.ByteString and Data.Text, which are array-backed string types that exist (almost) solely because 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 (in which case you might want to use some form of Builder instead, anyway.)
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.
- evincarofautumn 13y agoYeah. 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.
- millstone 13y ago> 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.
- thirsteh 13y agoYeah, it's not very efficient. I mainly use lists as stacks, or when I'm filtering some collection and I just need to traverse it.