[Haskell-cafe] Is the #functional programming paradigm antithetical to efficient strings? #Haskell

Bardur Arantsson spam at scientician.net
Mon Jul 11 17:35:32 UTC 2016

On 07/11/2016 04:28 PM, Stephen Tetley wrote:
> On 11 July 2016 at 13:54, David Fox <dsf at seereason.com> wrote:
>> When I mentioned some of this, I was told "different data structures for
>> different purposes", which sort of makes sense, but honestly if Haskell is a
>> language where you have to sit down and choose a representation every time
>> you want to build some text, I get a bit discouraged.
> Don't C# and Java have StringBuilder classes (different to their
> regular String types) for this as well?

Yes, they do.

If you just naively do

   String s = "";
   for (int i = 0; i < 1000000; i++) {
       s = s + "hello";

in Java you'll also get terrible performance (O(n^2)) as opposed to the
equivalent code using StringBuilder which would be O(n). This does not
change if you use e.g. Text/ByteString/Vector in Haskell.

In Haskell, I could certainly imagine List[Char] being more performant
than copying huge chunks of memory over and over... even though List
traversal *is* generally slow.

(Of course the actual performance depends on lots and lots of specifics.)

> Maybe imperative OO is also antithetical to efficient strings...

Bad algorithms and data structures are antithetical to efficient strings :).


More information about the Haskell-Cafe mailing list