Newbi Q: What is a rational for strings not being lists in Python?

Dmitri O.Kondratiev dokondr at
Tue Oct 16 13:20:47 CEST 2007

On 10/16/07, Matt McCredie <mccredie at> wrote:

> The example you posted won't work with tuples either because they,
> like strings, are also immutable. So, the best way to get the posted
> code to work (which is a bad way to go about reversing a string, but I
> digress)

I agree, my first example:

def reverse1(xs):
    if xs == []:
        return xs
        return (reverse1 (xs[1:])) + [xs[0]]

is very inefficient. I posted it just to illustrate my question about
strings and lists in Python.
The cost of reverse1() is proportional to:
(N - 1) + (N -2) + ...+1 = N(N - 1) /2, which in turn is ~ square(N),
where N is the number of elements in the list.

For example, reverse2() demonstrates a better algorithm, with cost
proportional to N:

def head(xs) :
    if xs == []:
        return []
        return xs[0]

def tail(xs) :
    if xs == []:
        return []
        return xs[1:]

def addHead (acc, xs):
    if xs == []:
        return acc
        return addHead ([head(xs)] + acc, tail(xs))

def reverse2 (xs):
    if xs == []:
        return []
        return addHead([], xs)


> is to cast the input parameter to a list first. The returned
> value will always be a list, but you will simply have to convert it
> back to the appropriate type when you are done.


Casting and writing wrapper classes is not interesting. Life becomes much
easier when  String is a subtype of List, and when you have polymorphic
functions making no difference between String and List.


> What is the purpose if immutability? It allows a value to be hashed. I
> don't want to get into a discussion about methods for hashing mutable
> types, if you are interested just do a search on the list archives.
> Hashing allows for quick comparisons of values, but more importantly
> it allows for values to be used as keys for the dict type. This is
> very important because, as you will soon find out if you keep learning
> the language, all namespaces in python are implemented as dicts.


As for me, I am perfectly happy with immutable types, I would rather do
without mutable ones. And thanks, everybody, for reminding me that Python is
a 'side effect' language, from which  by definition follows that it should
have mutable lists along with immutable strings. So answer to my question "What
is a rational for strings not being lists in Python?" is quite
trivial, as Simon
B. (simon at  <simon at>wrote: "Lists are
mutable, strings are not, so so strings can't support all a list's methods."

Sorry again for trivial question :(worked too much with Haskell recently and
mostly forgot about mutable types , I guess ) ...


So... if you want a mutable string, just cast it to a list, do your
> operations and cast it back to a string.
> Incidentally, the proper method for converting a list of characters to
> a string is by using the join method on an empty string.
> >>> s = "I am a string"
> >>> x = list(s)
> >>> x
> ['I', ' ', 'a', 'm', ' ', 'a', ' ', 's', 't', 'r', 'i', 'n', 'g']
> >>> "".join(x)
> 'I am a string'
> Matt


Dmitri O. Kondratiev
dokondr at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Python-list mailing list