Re: [Tutor] recursivity and lists

[sina sareth via Tutor]

Hi ThereI have those projects and I would like to get some directions the way 
to tackle them.
Thanks
1)  XML parsing into database. 
2) Do the same thing but this time, get ALL the quotes and save them as 
separate database entries (you will have to do a for loop for this). 
3) Use Django to build a view where you can download all Quotes in CSV form. 
4. Use Django to build a view where you can update quote values based on a call 
to the API (they change every day) 

On Friday, March 4, 2016 11:14 AM, Alan Gauld  
wrote:
 

 On 04/03/16 15:00, Gaston wrote:

> Both work but I am not satisfied. Is there not a method that could do 
> the job of '+' operator (namely concatenate in a copy)?

Why would you want a method? An operator is a perfectly legitimate
feature and is at least as readable as a method. It is certainly no less
"functional". And of course, in Python + usually translates
to the __add__() method anyway.


As to how your initial function works can I suggest you sit down
with a pen and paper and work through the code iteration by
iteration. Start with 2 element lists and then try 3 elements.
By the time you've done that it should become clear.
Keep track of the contents of list1 and list2 and the
output for each call of the function.

Recursive can be a seductive technique but it can be a real
brain twister to work out and debug when things don;t go
as expected! The pen/paper manual approach is the most
reliable technique I've found.

Here is what I mean for a 2 element list pair:

list1        list2        f(list1,list2)
---
[1]        [2]        f([1],[]).append(2) # first call of f()
[1]        []        [1].append(2) -> list1 becomes [1,2]
[1,2]          []              f([1,2],[])  # 2nd call of f() -> [1.2]

Now try that for 2 elements per list, then 3.
In effect you move elements from list 2 to list 1, or vice versa.
And you iterate over the list multiple times.
It's very inefficient as well as non intuitive.

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos


___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor


  
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] recursivity and lists

[Danny Yoo]

> As we can see, we have to do a lot more consideration of what state
> our values are in, due to all the mutation happening.  It also shows
> that the second recursive call to the linear_merge() is not really
> using it to merge: it's really trying to select the list that was used
> to accumulate results.  We'd get the same results with:
>
> ##
> def linear_merge1(list1, list2):
>   if list1==[]: return list2
>   elif list2==[]: return list1
>   elif list1[-1]>list2[-1]:
> a=list1.pop()
> linear_merge(list1,list2).append(a)
> return list1 or list2
>   else:
> a=list2.pop()
> linear_merge(list1,list2).append(a)
> return list1 or list2
> ##


Sorry: I made a mistake when typing out the internal recursive calls.
Substitute 'linear_merge1' in places where it had 'linear_merge'.

#
def linear_merge1(list1, list2):
  if list1==[]: return list2
  elif list2==[]: return list1
  elif list1[-1]>list2[-1]:
a=list1.pop()
linear_merge1(list1,list2).append(a)
return list1 or list2
  else:
a=list2.pop()
linear_merge1(list1,list2).append(a)
return list1 or list2
##



> So, yeah, the code is *much* too clever for it's own good.  :P

Substitute "it's" with "its".
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] recursivity and lists

[Danny Yoo]

> Both work but I am not satisfied. Is there not a method that could do the job 
> of '+' operator (namely concatenate in a copy)?
>

No; unfortunately Python doesn't make functional approaches as
convenient as I would personally like.


The copy operation on lists itself is expensive to do, so that's why I
think the list API encourages a mutational approach. If we were to
define our own data structures, we could make the functional approach
more natural and efficient.



> As for my first code :
>
> def linear_merge1(list1, list2):
>
>   if list1==[]: return list2
>   elif list2==[]: return list1
>   elif list1[-1]>list2[-1]:
> a=list1.pop()
> linear_merge(list1,list2).append(a)
> return linear_merge(list1,list2)
>   else:
> a=list2.pop()
> linear_merge(list1,list2).append(a)
> return linear_merge(list1,list2)
>
>
> I don't get why it works to be fair. It feels like return 
> linear_merge(list1,list2) does not call the function again.


That's because the behavior of this version is weird.  :)


Its contact could be stated as follows:



Given two sorted lists, linear_merge1 does the following three things:

A. Mutates one of the lists to be empty,

B. Mutates the other list have the merge-sorted results, and

C. Returns the reference to the merge-sorted list.



How can we be sure?  We can prove this to ourselves by inductive proof.


We'll do the induction based on the combined number of elements list1
and list2.  Call this combined size 'n'.

Base case: if n = 0, then both list1 and list2 are empty, and all
three conditions A, B, and C hold trivially.  That's easy enough.

Ok, time for the analysis for the n > 0 case.  As our induction
hypothesis, assume that all three conditions A, B, and C are true when
we call linear_merge1 for input with a combined size < n.  We want to
show that, if we're assuming that the induction hypothesis is true for
those smaller input sizes, then those three conditions will continue
to hold for the case where the input is of size n.


There are two cases we consider, when considering the case where the
input size n > 0.  We break our case analysis into two situations that
cover the gamut of possibility:

Case 1: either list1 or list2 is empty.  If this is true, then we hit
one of the two initial cases in the code that check for emptiness.
Since one of the lists is already empty, it doesn't need to be
mutated, so condition A holds.  Since both input lists were already
sorted, then case B holds.  Finally, case C holds because it's
returning that list.


Case 2: neither list1 nor list2 is empty.

Let's first consider the case where list1[-1] > list2[-1].  Then when
we perform:

a = list1.pop()

list1 still is a sorted list, though it is smaller.  When we call:

linear_merge(list1,list2).append(a)

then, since the combined size of list1 and list2 is now less than n,
we can apply our induction hypothesis.  Then we can assume that the
following things happen:

* either list1 or list2 empties out, due to condition A being
applied to the smaller input.

* we add the element 'a' to whichever merge-sorted list was
returned by the recursive call.

After that call, either list1 or list2 contain the merge-sorted
results, and the other list is empty.

Finally, the funky second call to:

return linear_merge(list1, list2)

will return either list1 or list2, because we know that, from the
prior call, one of those lists is empty due to the operation of that
first recursive call.  We now know that what gets returned here is the
reference to the list that has the merge-sorted results.

Ok, that closes that chain of reasoning for the case where list1[-1] >
list2[-1].  And since we can make a similar chain of reasoning for the
other case, we can stop here.

---


That's a rough math proof sketch of why linear_merge1 is working for you.


As we can see, we have to do a lot more consideration of what state
our values are in, due to all the mutation happening.  It also shows
that the second recursive call to the linear_merge() is not really
using it to merge: it's really trying to select the list that was used
to accumulate results.  We'd get the same results with:

##
def linear_merge1(list1, list2):
  if list1==[]: return list2
  elif list2==[]: return list1
  elif list1[-1]>list2[-1]:
a=list1.pop()
linear_merge(list1,list2).append(a)
return list1 or list2
  else:
a=list2.pop()
linear_merge(list1,list2).append(a)
return list1 or list2
##

and depend on Python to determine which value is truthy, which in the
case of lists, will prefer the non-empty lists.  That is, the second
recursive calls are red herrings.  That's what initially made me do a
double-take when I saw it, and I had to reason to myself why in the
world it was working: it's all due to the mutational 

Re: [Tutor] recursivity and lists

[Alan Gauld]

On 04/03/16 19:25, sina sareth wrote:
> Hi There

Hi, welcome to tutor. But please do not hijack an existing thread
for a new topic. Post a new message to tutor@python.org.

Otherwise the archive gets very confusing for people searching
for answers. Or even for people using threaded email/news readers.

> I have those projects and I would like to get some directions the way
> to tackle them.
>

Given that you have provided very little information about your
knowledge/skill level
as well as the problem we can only give very sketchy advice.

> Thanks
>
> 1)  XML parsing into database. 
>
For xml parsing use the etree package

For a data base we woyuld need to know what kind of database,
what you want to store from the XML etc.


> 2) Do the same thing but this time, get ALL the quotes and save

What kind of quotes?
> them as separate database entries (you will have to do a for loop for
> this). 
>

> 3) Use Django to build a view where you can download all Quotes in CSV
> form. 
>
Consult the Django tutorial/docs for help with Django. Its outside this
groups remit.

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos

___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] recursivity and lists

[Alan Gauld]

On 04/03/16 15:00, Gaston wrote:

> Both work but I am not satisfied. Is there not a method that could do 
> the job of '+' operator (namely concatenate in a copy)?

Why would you want a method? An operator is a perfectly legitimate
feature and is at least as readable as a method. It is certainly no less
"functional". And of course, in Python + usually translates
to the __add__() method anyway.


As to how your initial function works can I suggest you sit down
with a pen and paper and work through the code iteration by
iteration. Start with 2 element lists and then try 3 elements.
By the time you've done that it should become clear.
Keep track of the contents of list1 and list2 and the
output for each call of the function.

Recursive can be a seductive technique but it can be a real
brain twister to work out and debug when things don;t go
as expected! The pen/paper manual approach is the most
reliable technique I've found.

Here is what I mean for a 2 element list pair:

list1   list2   f(list1,list2)
---
[1] [2] f([1],[]).append(2) # first call of f()
[1] []  [1].append(2) -> list1 becomes [1,2]
[1,2]   []  f([1,2],[])   # 2nd call of f() -> [1.2]

Now try that for 2 elements per list, then 3.
In effect you move elements from list 2 to list 1, or vice versa.
And you iterate over the list multiple times.
It's very inefficient as well as non intuitive.

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos


___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Tutor Digest, Vol 145, Issue 7

[Alan Gauld]

On 04/03/16 16:49, justin walters wrote:
> I personally use pycharm community edition. It has helped me learn a lot.
> It is quite heavy though. I think your best bet would be sublime text(mac,
> windows, and linux) or gedit(linux only I believe).

Thanks for the comments Justin but please in future do not send
the whole digest message with your answer. WE have all received
the messages already, and some people pay by the byte for their
access.

Also please change the subject line to something meaningful.

Thanks

Alan G.
List moderator.



> On Mar 3, 2016 9:00 AM,  wrote:
> 
>> Send Tutor mailing list submissions to
>> tutor@python.org
>>
>> To subscribe or unsubscribe via the World Wide Web, visit
>> https://mail.python.org/mailman/listinfo/tutor
>> or, via email, send a message with subject or body 'help' to
>> tutor-requ...@python.org
>>
>> You can reach the person managing the list at
>> tutor-ow...@python.org
>>
>> When replying, please edit your Subject line so it is more specific
>> than "Re: Contents of Tutor digest..."
>>
>>
>> Today's Topics:
>>
>>1. Re: Recommendations for best tool to write/run Python :p:
>>   (Thomas C. Hicks)
>>2. Re: Recommendations for best tool to write/run Python :p:


___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Tutor Digest, Vol 145, Issue 7

[justin walters]

I personally use pycharm community edition. It has helped me learn a lot.
It is quite heavy though. I think your best bet would be sublime text(mac,
windows, and linux) or gedit(linux only I believe).
On Mar 3, 2016 9:00 AM,  wrote:

> Send Tutor mailing list submissions to
> tutor@python.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
> https://mail.python.org/mailman/listinfo/tutor
> or, via email, send a message with subject or body 'help' to
> tutor-requ...@python.org
>
> You can reach the person managing the list at
> tutor-ow...@python.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Tutor digest..."
>
>
> Today's Topics:
>
>1. Re: Recommendations for best tool to write/run Python :p:
>   (Thomas C. Hicks)
>2. Re: Recommendations for best tool to write/run Python :p:
>   (Thomas C. Hicks)
>3. Re: Recommendations for best tool to write/run Python :p:
>   (Alan Gauld)
>
>
> --
>
> Message: 1
> Date: Thu, 3 Mar 2016 17:28:15 +0800
> From: "Thomas C. Hicks" 
> To: tutor@python.org
> Subject: Re: [Tutor] Recommendations for best tool to write/run Python
> :p:
> Message-ID: <56d803af.6060...@pobox.com>
> Content-Type: text/plain; charset=utf-8; format=flowed
>
> Matt,
>
> As a physician myself just getting into the world of teaching computer
> programming I would be very interested to know what you teach to the
> doctors.  Feel free to reply off list, would love to discuss this!
>
> ===
> Thomas C. Hicks, MD, MPH
> Training Manager
> Gansu Gateway, Lanzhou, Gansu
>
> On 03/03/2016 05:25 AM, Matt Williams wrote:
> > I teach an introductory programming course to medical students (and a few
> > doctors).
> >
> > I would look at Sublime Text 2 if one Windows/ Mac. Has a 'nag' screen to
> > remind you to buy, but feels simple enough when you start it.
> >
> > M
> >
> > On Wed, 2 Mar 2016 19:50 Ben Finney,  wrote:
> >
> >> Lisa Hasler Waters  writes:
> >>
> >>> Ben, in terms of time for learning curve, I suppose we do have some
> >>> limitations as we are up against school schedules. However, if it is
> >>> something I could learn in a reasonable time that I could then more
> >>> quickly walk my students through then I'd be up for the challenge!
> >> In that case, my recommendation is to learn a good programmer's editor,
> >> and let your students gain exposure to that.
> >>
> >> Emacs and Vim are the unchallenged masters here; community-owned,
> >> free-software, cross-platform, mature and highly flexible with support
> >> for a huge range of editing tasks. Learning either of those will reward
> >> the student with a tool they can use broadly throughout whatever
> >> computing career they choose.
> >>
> >> They aren't a small investment, though. That ?mature? comes at the cost
> >> of an entire ecosystem that evolved in decades past; concepts and
> >> commands are idiosynratic in each of them. It is highly profitable for
> >> any programmer to learn at least one of Emacs or Vim to competence, but
> >> it may be too much to confront a middle-school student in limited class
> >> time. Maybe let the class know they exist, at least.
> >>
> >> Short of those, I'd still recommend a community-owned, free-software,
> >> highly flexible programmer's editor. If you're on GNU+Linux, use the
> >> Kate or GEdit editors; they integrate very nicely with the default
> >> desktop environment and are well-maintained broadly applicable text
> >> editors. GEdit in particular has good Python support.
> >>
> >> I would recommend staying away from any language-specific IDE. Teaching
> >> its idiosyncracies will still be a large time investment, but will not
> >> be worth it IMO because the tool is so limited in scope. Better to teach
> >> a powerfuly general-purpose programmer's editor, and use the operating
> >> system's facilities for managing files and processes.
> >>
> >> --
> >>   \?Humanity has advanced, when it has advanced, not because it
> |
> >>`\ has been sober, responsible, and cautious, but because it has
> |
> >> _o__)been playful, rebellious, and immature.? ?Tom Robbins |
> >> Ben Finney
> >>
> >> ___
> >> Tutor maillist  -  Tutor@python.org
> >> To unsubscribe or change subscription options:
> >> https://mail.python.org/mailman/listinfo/tutor
> >>
> > ___
> > Tutor maillist  -  Tutor@python.org
> > To unsubscribe or change subscription options:
> > https://mail.python.org/mailman/listinfo/tutor
>
>
>
> --
>
> Message: 2
> Date: Thu, 3 Mar 2016 17:31:12 +0800
> From: "Thomas C. Hicks" 
> To: tutor@python.org
> Subject: Re: [Tutor] Recommendations for best 

Re: [Tutor] recursivity and lists

[Gaston]

Thank you for these comments. Made me realize that I do not fully 
understand my code, and need to think about it a bit more.


I totally understand the huge side effects, and it is true that it would 
be dangerous if the function was to actually be used. I would like to 
find a fully functional version, using slices then. I propose this :


def linear_merge(list1, list2):
  if list1==[]: return list2
  elif list2==[]: return list1
  elif list1[-1]>list2[-1]:
return linear_merge(list1[:-1],list2)+[list1[-1]]
  else:
return linear_merge(list1,list2[:-1])+[list2[-1]]

Or alternatively:

elif list1[-1]>list2[-1]:
b=linear_merge(list1[:-1],list2)
b.append(list1[-1])
return b

Both work but I am not satisfied. Is there not a method that could do 
the job of '+' operator (namely concatenate in a copy)?


As for my first code :

def linear_merge1(list1, list2):
  if list1==[]: return list2
  elif list2==[]: return list1
  elif list1[-1]>list2[-1]:
a=list1.pop()
linear_merge(list1,list2).append(a)
return linear_merge(list1,list2)
  else:
a=list2.pop()
linear_merge(list1,list2).append(a)
return linear_merge(list1,list2)

I don't get why it works to be fair. It feels like return 
linear_merge(list1,list2) does not call the function again. If return 
linear_merge(list1,list2) actually returned linear_merged of the lists, 
with one of them missing an element, I don't see where this element is 
actually added.


I know find it very weird. I would appreciate if you had an explanation 
(and if you understood my point)


Thank you for your help,

Gaston

On 03/03/2016 10:29 PM, Danny Yoo wrote:


Some code comments:  The solution you have depends very much on 
mutation and side effects: I recommend you try to stay as functional 
as you can in this situation.


By mixing mutation into the solution, there are certain things that 
the program is doing that isn't part of the traditional behavior of a 
merge sort.


For example, it is actively mutating the input lists.  That's both 
surprising and error prone.


Also, the purpose for the second internal calls to the merge sort in 
your current solution have nothing to do with merging, but rather to 
pick which nonempty list to return as the result.  A reader of the 
code who doesn't look at this code *very* carefully would wonder why 
the function wasn't infinite-looping.  It's a bit too clever for its 
own good.


Hope that makes sense!



___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Recommendations for best tool to write/run Python :p:

[Albert-Jan Roskam]

> Date: Thu, 3 Mar 2016 15:54:56 -0600
> From: da...@graniteweb.com
> To: tutor@python.org
> Subject: Re: [Tutor] Recommendations for best tool to write/run Python :p:
> 
> * Alan Gauld  [2016-03-03 11:02]:
> > On 03/03/16 09:31, Thomas C. Hicks wrote:
> > > On 03/03/2016 02:26 AM, Lisa Hasler Waters wrote:
> > >> Could you please recommend the best Python tools for writing and running
> > >> our code for the long term? Also, we are hoping to find free tools!
> > >>
> > > Most people on this list are a lot smarter than me so there are probably 
> > > good reasons for it but I have used Ipython (now Jupyter) for teaching 
> > > my kids programming in middle and high school.
> > 
> > IPython is great as an interactive environment but the OP
> > specifically mentioned writing longer programs and editing
> > files which is not what IPython does best. I suspect that's
> > why it didn't get a mention earlier.
> 
> Very likely, but it's definitely worth mentioning as a runtime environment.
> It's a big step above the basic built-in CLI

Yes, IPython is extremely useful, even if only for testing code snippets. 
IPython Notebook is worth mentioning as well.
My favourite IDE currently is Spyder (free). PyScripter is nice (and free) too, 
but I don't like the way it behaves with pdb (with a little menu). Both come 
with Python(x, y). PyCharm is great too (maybe even nicer than Spyder), but 
it's only free for open source projects. It is Java-based, but only Sun Java 
and not Open JDK (it occasionally frooze with Open JDK so I stoped using it).

Albert-Jan
  
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor