With the naive representation of a string as a list of characters [Char], it is. The only way to get to the end of the list is to recursively take the tail of the string (see the source at http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC...).
There's alternative representations with different trade offs, such as Data.Text
Heh... but I was referring to the example seliopou gave, which appears to be in JavaScript, and strings is [String] rather than [Char]. I think the analogy might cause more confusion than clarification.
Comments
How is the original (the for loop that you mentioned) O(n^2)? Isn't that O(n)? Isn't acc += strings[i] a O(1) operation?
Each time strings[i] is added to acc, it may require reallocating entire acc to new memory location with more memory for the concatenated string.
`acc` is assumed immutable, so it has to be copied entirely on each concatenation. Copying a string is an O(n) operation.
But strings.length is O(n), and you have to run it n times.
No, it is not.
With the naive representation of a string as a list of characters [Char], it is. The only way to get to the end of the list is to recursively take the tail of the string (see the source at http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC...).
There's alternative representations with different trade offs, such as Data.Text
Heh... but I was referring to the example seliopou gave, which appears to be in JavaScript, and strings is [String] rather than [Char]. I think the analogy might cause more confusion than clarification.
not if you have to reallocate space for storing acc on each iteration