On 10/16/07, Matt McCredie <[EMAIL PROTECTED]> wrote: [quote] > 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) > [end-quote]
I agree, my first example: def reverse1(xs): if xs == []: return xs else: 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 [] else: return xs[0] def tail(xs) : if xs == []: return [] else: return xs[1:] def addHead (acc, xs): if xs == []: return acc else: return addHead ([head(xs)] + acc, tail(xs)) def reverse2 (xs): if xs == []: return [] else: return addHead([], xs) [quote] > 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. [end-quote] 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. [quote] > 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. [end-quote] 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. ([EMAIL PROTECTED]) <[EMAIL PROTECTED]>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 ) ... [quote] 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 > [end-quote] -- Dmitri O. Kondratiev [EMAIL PROTECTED] http://www.geocities.com/dkondr
-- http://mail.python.org/mailman/listinfo/python-list