On 10/16/07, <b class="gmail_sendername">Matt McCredie</b> <<a href="mailto:mccredie@gmail.com">mccredie@gmail.com</a>> wrote:<br><div><span class="gmail_quote">[quote]<br></span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

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

</blockquote><div>[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.

<br>The cost of reverse1() is proportional to:<br>(N - 1) + (N -2) + ...+1 = N(N - 1) /2, which in turn is ~ square(N),<br>where N is the number of elements in the list.<br><br>For example, reverse2() demonstrates a better algorithm, with cost proportional to N:

<br><br>def head(xs) :<br>    if xs == []:<br>        return []<br>    else:<br>        return xs[0]<br>    <br>def tail(xs) :<br>    if xs == []:<br>        return []<br>    else:<br>        return xs[1:]<br><br>def addHead (acc, xs):

<br>    if xs == []:<br>        return acc<br>    else:<br>        return addHead ([head(xs)] + acc, tail(xs))<br><br>def reverse2 (xs):<br>    if xs == []:<br>        return []<br>    else:<br>        return addHead([], xs)

<br><br></div> <span class="gmail_quote">[quote]</span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">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.</blockquote><div>[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.

<br></div><br><span class="gmail_quote">[quote]</span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">What is the purpose if immutability? It allows a value to be hashed. I

<br>don't want to get into a discussion about methods for hashing mutable<br>types, if you are interested just do a search on the list archives.<br>Hashing allows for quick comparisons of values, but more importantly<br>

it allows for values to be used as keys for the dict type. This is<br>very important because, as you will soon find out if you keep learning<br>the language, all namespaces in python are implemented as dicts.</blockquote>

<div><span class="gmail_quote">[end-quote]<br><br>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 

</span><span class="gmail_quote">follows that</span><span class="gmail_quote"> it should have mutable lists along with immutable strings. So answer to my question "</span>What is a rational for strings not being lists in Python?" is quite trivial, as 

<span class="sg">Simon B.<a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:simon@brunningonline.net"> (simon@brunningonline.net)  </a></span>wrote: "Lists are mutable, strings are not, so so strings can't support all a list's methods." 

<br>Sorry again for trivial question :(worked too much with Haskell recently and mostly forgot about mutable types , I guess ) ...<br><br><span class="gmail_quote">[quote]</span> <br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

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.

<br><br>>>> s = "I am a string"<br>>>> x = list(s)<br>>>> x<br>['I', ' ', 'a', 'm', ' ', 'a', ' ', 's', 't', 'r', 'i', 'n', 'g']

<br>>>> "".join(x)<br>'I am a string'<br><br><br>Matt<br></blockquote></div><br><span class="gmail_quote">[end-quote]</span><br clear="all"><br>-- <br>Dmitri O. Kondratiev<br><a href="mailto:dokondr@gmail.com">

dokondr@gmail.com</a><br><a href="http://www.geocities.com/dkondr">http://www.geocities.com/dkondr</a>