Why are strings linked lists?

Donald Bruce Stewart dons at cse.unsw.edu.au
Fri Nov 28 15:04:54 EST 2003


ajb:
> G'day all.
> 
> Quoting Ben Escoto <bescoto at stanford.edu>:
> 
> > Hi, can someone tell me why Haskell strings are linked lists?
> 
> Because that's the way it was done in Miranda, almost 20 years ago.
> 
> OK, to be fair, it does make string-to-string operations a bit more
> convenient.  Apart from undergraduate homework exercises and some
> specific domains, though, this isn't exactly the "common case" of
> all situations where people want strings.
> 
> As a matter of pure speculation, how big an impact would it have if, in
> the next "version" of Haskell, Strings were represented as opaque types
> with appropriate functions to convert to and from [Char]?  Would there be
> rioting in the streets?

You could look at GHC's FastString representation (used internally).
It is in $fptools/ghc/compiler/utils/FastString.lhs

    data FastString
      = FastString   -- packed repr. on the heap.
          Int#       -- unique id
          Int#       -- length
          ByteArray# -- stuff

Now that is pretty compact.

-- Don


More information about the Haskell mailing list